12571 - Brother & Sisters!

All about problems in Volume 125. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12571 - Brother & Sisters!

Post by brianfry713 » Mon Dec 10, 2012 2:31 am

Input:

Code: Select all

5
1 192
451894078
201
38
62
142
164
168
139
83
215
77
54
123
24
12
178
214
20
46
75
9
94
44
19
176
8
221
159
151
122
227
200
78
159
16
17
186
206
48
51
146
161
123
96
217
59
186
71
196
64
133
166
20
197
136
195
76
214
16
215
146
123
146
221
189
35
196
112
218
146
38
219
187
7
138
161
140
149
207
113
110
156
28
111
34
48
24
67
61
175
83
74
142
99
149
36
36
15
27
56
205
172
220
190
229
170
141
190
10
108
2
218
13
167
181
217
114
5
159
191
82
125
223
191
76
212
222
135
165
130
144
173
91
71
26
84
93
118
164
52
201
116
189
21
163
189
147
23
178
93
23
179
217
164
111
147
57
27
126
215
224
108
75
144
187
77
9
52
174
42
101
148
93
55
183
167
130
7
96
101
35
194
196
108
163
151
180
92
87
152
175
40
114
136 52
483575571 183163531 950590376 845088065 765156491 102619167 386336062 343737412 83179673 256751110 86238339 537068295 148420344 115240884 658353420 765562918 81207647 425887388 924322224 331684670 139352338 179981504 768805469 32136197 16310467 306941552 94598183 606067545 803474671 781441919 926447057 746169099 798245490 25055816 118019741 234603392 527470595 1709500 751609334 667207028 848778385 992566602 906036413 603495798 705982132 156459774 290838469 247635645 618706269 71381565 22484101 551983139 943960676 59518691 839919355 453436875 131124035 539565528 956001172 248933431 590239725 498212491 655404499 180402153 97675329 863795272 818147283 809861375 873287217 471038622 143047569 11489304 358618412 709816047 391307463 188095326 579970101 404679241 292085 137763056 977686794 253593089 78318717 414135683 21112824 17236545 529422201 295294505 90218675 109349002 236331228 677695691 572196062 339308978 390743023 67842437 804499560 102937604 657350605 422022646 633068671 15203738 698653413 615045537 363875587 887878512 4331139 305535630 666726955 39064567 536336107 135781886 446079491 808386238 947876818 19017001 175625054 699344602 886773913 635875897 522416003 67656158 510661484 326262001 813563665 935883817 989614064 921091399 466306286 795459008 282385248 23493519 510105492 503198144 712576631 964101167
225
190
198
61
182
30
2
200
168
226
125
172
192
85
195
219
80
227
209
134
75
186
66
14
139
32
62
114
73
30
44
145
73
147
48
80
36
33
65
42
92
215
214
169
48
119
62
194
36
188
134
98
101 66
136870477 110205109 168656568 598021552 100312878 300910823 804965071 227107972 607773450 967391572 379769298 41324833 746973521 425043935 714609379 262989104 84563941 638306138 894464472 460235510 147338351 194536449 110192991 829811360 715289134 172551622 486583973 753644303 565414189 73112894 650564716 743152289 909934362 399422421 285448303 196247272 65106584 127250053 325760505 840009532 894114894 533600186 556022644 125918217 873679357 44797109 707887536 172264044 328692782 991144661 974113639 458001436 202672067 841783498 55802552 422469902 644044739 711228816 679803301 905110033 514665714 902034861 668719420 382778860 809342954 22543761 574362890 486518937 884258547 796078800 10310475 900635774 393588501 859322831 321039851 57925335 598633155 863126383 341982879 14523300 46282443 616144593 250388106 751295254 353197714 685715246 881421926 519084422 993217983 300125212 115075598 29394912 237059735 468711783 36730871 673333856 46014231 498234008 337000394 396157637 613415822
13
191
29
225
55
130
87
66
191
31
181
87
145
179
109
164
163
73
197
94
120
4
133
104
109
214
93
41
172
191
153
39
98
151
96
115
185
80
161
122
128
157
148
70
178
225
44
103
191
182
186
128
194
175
126
175
62
3
189
216
111
191
75
25
117
150
99 186
516813960 88116399 138121814 321870195 626719339 19270797 719549623 394946378 565308161 724165807 424529343 822688080 645051077 971501568 246538407 115015399 959028098 213099208 10985851 861503182 655330006 228619539 36359487 916935430 979922445 115098768 657039547 642657767 282927385 180519576 640284589 5104309 62847458 748341299 768857827 218239663 419454611 51227007 270351478 628687133 841409407 786956743 145112175 898206444 941040351 712380772 22213303 426201852 732298276 938657278 506699167 792974014 522813255 426665215 409420717 414516542 709507764 646122515 934428205 34899669 558110498 67021072 515724085 745012476 910154860 834931316 59406848 375297647 570771036 891546169 334490237 12634388 676389561 448402810 649963398 342089500 549465022 20461562 689613576 230189876 557771322 93195074 689450300 579085839 113166197 841078454 636811492 29918183 8945580 202343276 109685392 430988399 383939816 136505460 888851353 447795482 455827014 307080534 646342418
109
199
69
25
226
212
73
1
93
165
158
45
162
53
54
23
124
94
192
134
177
107
64
57
200
65
126
141
214
188
112
35
209
173
100
218
5
151
164
91
91
7
188
158
12
140
13
100
72
104
57
13
95
110
63
45
70
188
157
207
2
3
227
178
91
187
21
65
174
177
68
124
107
177
39
123
91
101
195
182
219
83
188
101
101
73
4
200
191
125
103
188
174
87
55
160
165
82
82
142
94
197
158
122
48
40
169
226
29
51
182
128
51
146
186
212
209
18
81
52
223
58
195
200
106
67
64
44
15
5
137
87
180
155
183
162
155
160
70
40
221
172
92
173
59
59
155
22
144
166
217
21
118
2
35
23
165
206
70
135
196
83
165
84
63
179
76
40
228
145
175
150
209
137
72
215
82
159
205
86
177
16
35
138
97
99
151 84
481560329 450954752 259283609 456599213 5921891 341814094 939865491 584469018 85874224 19080030 875311386 871923121 43324003 649551515 155963109 173445668 248751705 587523562 702374155 93963683 976776287 502811370 486268204 410555473 277807090 335224252 508884630 658811174 580869081 41845693 386302250 513580423 953487264 605137808 244891544 2383149 404171638 371180429 13512493 891951353 542951395 405673230 442634006 788142267 277789107 919674363 481698466 41924346 536497129 124091142 457361303 675427986 482920672 11982557 138378881 348080048 822158643 533174863 181350175 931391228 382376928 67863409 284211236 24546120 749907809 112854236 580049258 275058847 817409261 456016266 827285522 2371590 246665031 309653834 321032871 864105509 108163929 563327837 101191127 739306298 294503469 297798120 895301329 133156633 99328780 267290975 98719208 995625715 172076498 718293777 537225573 657404221 680672841 551923274 258180658 3208468 460951955 832927036 644468487 109355590 351953375 370563132 790332363 507940620 47390932 30680625 978684014 336093885 548236252 11064470 929289717 286928471 323410566 731902279 367815058 142546803 643592310 972887284 22114903 977304211 500263791 485284742 254267903 919137219 21848737 819848309 283991075 270917325 615849095 34597671 91898574 103154067 929651108 133450535 135509909 142725703 373843096 944664256 444617358 217260756 960102542 522095188 63764212 662890470 737558506 437571359 842548030 991374052 574637676 305058042 592307724
167
129
223
126
221
214
18
9
207
135
128
102
165
31
112
10
169
28
40
129
219
99
84
161
129
67
11
210
227
126
77
37
210
168
164
79
77
227
44
189
34
25
78
131
226
211
207
48
195
1
224
81
124
191
183
176
223
38
122
19
40
127
2
153
194
78
136
173
2
9
225
66
185
162
112
109
10
126
66
209
50
148
59
39
AC output:

Code: Select all

8
38
62
14
36
40
10
18
22
12
54
58
24
12
50
22
20
46
10
8
30
44
18
48
8
28
30
22
58
34
8
14
30
16
16
58
14
48
50
18
32
58
32
24
58
58
6
4
0
4
38
20
4
8
2
12
22
16
22
18
58
18
28
60
34
4
48
26
18
38
26
58
6
10
32
12
20
14
48
46
28
28
46
34
48
24
2
60
46
18
10
14
34
20
36
36
14
26
56
12
44
28
62
36
42
12
62
10
44
2
26
12
38
52
24
50
4
30
62
18
60
30
62
12
20
30
6
36
2
16
44
26
6
26
20
28
54
36
52
8
52
60
20
34
60
18
22
50
28
22
50
24
36
46
18
56
26
62
22
32
44
10
16
58
12
8
52
46
42
36
20
28
54
54
38
2
6
32
36
34
2
4
44
34
22
52
28
22
24
46
40
50
225
190
198
61
182
30
2
200
168
226
125
172
192
85
195
219
80
227
209
134
75
186
66
14
139
32
62
114
73
30
44
145
73
147
48
80
36
33
65
42
92
215
214
169
48
119
62
194
36
188
134
98
13
191
29
225
55
130
87
66
191
31
181
87
145
179
109
164
163
73
197
94
120
4
133
104
109
214
93
41
172
191
153
39
98
151
96
115
185
80
161
122
128
157
148
70
178
225
44
103
191
182
186
128
194
175
126
175
62
3
189
216
111
191
75
25
117
150
109
199
69
25
226
212
73
1
93
165
158
45
162
53
54
23
124
94
192
134
177
107
64
57
200
65
126
141
214
188
112
35
209
173
100
218
5
151
164
91
91
7
188
158
12
140
13
100
72
104
57
13
95
110
63
45
70
188
157
207
2
3
227
178
91
187
21
65
174
177
68
124
107
177
39
123
91
101
195
182
219
83
188
101
101
73
4
200
191
125
103
188
174
87
55
160
165
82
82
142
94
197
158
122
48
40
169
226
29
51
182
128
51
146
186
212
209
18
81
52
223
58
195
200
106
67
64
44
15
5
137
87
180
155
183
162
155
160
70
40
221
172
92
173
59
59
155
22
144
166
217
21
118
2
35
23
165
206
70
135
196
83
165
84
63
179
76
40
228
145
175
150
209
137
72
215
82
159
205
86
177
16
35
138
97
99
167
129
223
126
221
214
18
9
207
135
128
102
165
31
112
10
169
28
40
129
219
99
84
161
129
67
11
210
227
126
77
37
210
168
164
79
77
227
44
189
34
25
78
131
226
211
207
48
195
1
224
81
124
191
183
176
223
38
122
19
40
127
2
153
194
78
136
173
2
9
225
66
185
162
112
109
10
126
66
209
50
148
59
39
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 12571 - Brother & Sisters!

Post by uvasarker » Thu Dec 13, 2012 3:15 pm

Guru,
I am getting TLE.......Why?
give me some tricks...for this problem.....
My code generates same output as yours within 0.047 seconds:

Code: Select all

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    int T;
    //freopen("in.txt","r",stdin);
    //freopen("b.txt","w",stdout);
    scanf("%d",&T);
    while(T--){
        int n, q, an[100001], aq[30000], in, ans, maxx=0;
        scanf("%d %d",&n,&q);
        for(int i=0 ; i<n ; i++){
            scanf("%d",&an[i]);
        }
        for(int i=0 ; i<q ; i++){
            scanf("%d",&in);
            for(int j=n-1 ; j>=0 ; j--){
                ans = in&an[j];
                if(ans>maxx){
                    maxx = ans;
                }
            }
            printf("%d\n",maxx);
            maxx=0;
        }
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12571 - Brother & Sisters!

Post by brianfry713 » Thu Dec 13, 2012 11:00 pm

Precompute the answer for all 230 possible queries so that each query runs in O(1).
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 12571 - Brother & Sisters!

Post by Shahidul.CSE » Thu Aug 07, 2014 9:07 pm

Since the input sequence is different each time, so how to precompute for all a=1 to 230 ? Ok, value of a will be among 1 to 230, but x1,x2,x3,............ is unknown, so with whom to compute a&xi, for a=1 to 230 ?
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12571 - Brother & Sisters!

Post by brianfry713 » Sat Aug 09, 2014 12:24 am

Here's one way to solve it:
Keep track of previous results using int dp[230];
At the start of a test case, clear the dp array by setting it to all -1.
After you read in each a value, if you have already answered a query for that a value then you can just print it from the dp array.
Otherwise calculate the answer for that a and store it into the dp array.
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 12571 - Brother & Sisters!

Post by Shahidul.CSE » Sat Aug 09, 2014 6:35 am

Oh, I was wrong ! I said,
Input sequence is different each time.
But there is only one sequence, I forgot that :P
By the way by precalculating, got AC ! :D :D
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 12571 - Brother & Sisters!

Post by lighted » Sun Sep 07, 2014 9:35 pm

Got accepted without precalculating in 0.202. :)

I took into account only lower bytes of given n (<= 100000) numbers. There are only 0..255 types of them. For each query make & operation with existing lower bytes
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 125 (12500-12599)”