Lol, waited the whole year and didn't take part ....

Probably? :)

You nailed it

Hope I'll become a grandmaster I need 65 rating and it is kinda impossible

I don't understand. Why this kind of comments should be downvoted...

Yes,it will.And I think it doesn't matter if you do a great job or win a T-shirt or not,I think the
feeling during the contest is the most exciting thing！ And good luck to all of you!

Nothing is already played! wait for the leaderboard.

There are 8 problems for all participants.
Div1 + Div2 means that everybody can participate. For example above 2100 can't participate in Div2. or the same for above 1600 and Div3.

it mean that the contest for all participants. I think if you can achieved rank 1 in this contest, you will be +800 rating =)) good luck for u ^^

last?

It's combined round (Div. 1 + Div. 2), the high rated coders will be bored if they solved all the problems quickly. you can see that tourist solved all the 8 problems of Good Bye 2018 in less than 2 hours, also few contestants solved all the 8 problems of last year Manthan, Codefest 18 in less than 2 hours.

Wow, it's so InTeReStInG !1!! (No)

let's guess who will win .. tourist ofcourse

Use subsquares 4x4 of numbers 0-15 MOD 16 like (0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15) — it has zero XORs and prefixes are repeated 4 times, thus their XOR is also 0.

0 1 2 3__________16 17 18 19

4 5 6 7__________20 21 22 23

8 9 10 11________24 25 26 27

12 13 14 15______28 29 30 31

32 33 34 35_____48 49 50 51

36 37 38 39_____52 53 54 55

40 41 42 43_____56 57 58 59

44 45 46 47_____60 61 62 63

It also took me 1 and a half hour. I am not even sure whether it is correct or not. Let's see the system testing results.

Fill that array in increments of 4 like 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15

This way xor will always be zero of all rows and columns.

Some one here said that B was harder than C. And you say that C is harder than D and E. It took me more than one and a half hours to get the B pretests correct. I am thinking whether I should I have skipped B.

Oh dear, I got bug at D.

Dunno whether my C is correct. Btw I use the fact that I can construct a grid for numbers 0->15, then I could construct numbers for 16k->16k+15

U can find a pattern that if you break the given nxn matrix into 4x4 matrices with increasing values (For ex: 0 to 15, 16 to 31 etc) , you can make all the rows and columns have xor sum = 0.
Find my submission here :)

This is my approach:

Divide the whole matrix into 4 * 4 matrices. Then fill every matrix with slight modification of a valid answer for a 4 * 4 matrix. I used the result of test case 1 of the problem statement. Keep a variable that tells us the number of matrices that has been processed. Left shift counter variable by 4 and then perform bitwise OR operation with the corresponding number of the initial matrix while assigning.

Will it be correct? Yes, because the XOR of each row and column of every 4 * 4 matrix will be the same. So, if you use test case 1, then the XOR of each row and column of the whole matrix will be 13 or 0.

Will any number repeat? No, because we are using counter variable. Every number has 4 initial bits with 2 ^ 4 possible combinations. These are covered by the initial matrix. We just need to cover the extra bits. The counter gives us new combinations of the extra bits, starting from the lowest. By performing bitwise OR, we are reaching each bitwise combination. So, we will hit each number once.

My submission can be found here.

I did it with a lazy segment tree, but there seems to be a way to do it with just a regular segtree/fenwick tree. In the sequence you get, the last 0 is always the 1 in the original. If you imagine that you remove the 1 you found and subtract 1 from every item after that you would get a similar sequence for 2..N. Then you find the last zero again, which now is the 2 and you subtract 2 from everything after etc. You use a lazy min segment tree to find the last zero (order by value and index) and to do the range subtractions.

My code passes this but fails on system test 50. 59469362

// 1 4 3 2

4

0 1 1 1

//9 5 3 4 1 6 2 8 7

9

0 0 0 3 0 13 1 21 21

You can use fenwick tree with range update and point query.

I only used std::priority_queue.

Keep up to date (hipozhor)

3 miniutes for D and 2 minutes for C is unbelieveable

Guys, I know what happened. tourist obviously cheated. See for yourself:

How can he start coding at 17:33:16 if the contest started at 17:35:00? I knew something wasn't right about him, but now he gave himself away!

I would disqualify everybody whose handle starts with t as a warning.

You can delete either:

1. some prefix
2. some suffix
3. something in the middle

You will be left with (respectively):

1. some suffix
2. some prefix
3. some prefix + some suffix

Basically, (1) and (2) are the same as (3) if you assume that there is an empty prefix/suffix.

So, what you can try to do is for each prefix (empty, too) find the largest suffix satisfying the conditions -- what is left between them is exactly what you delete, take the minimum of all such gaps.

The simplest way, according to the given constraints would be to add each element in the array to a set. Then for every index i starting from 0, we traverse j left to right from i, generating every subarray starting at i, and trying to remove each element from the set and check if size of the set at any point is N- (j-i+1). We stop the first time it happens and we've found the smallest subarray starting at i. Then we increment i again, but before doing that make sure you add back the i'th element to the set. It will be O(N^2 lgN) There's also an O(N) solution by the way, that I used.

you can try two pointers to solve that...i am not sure,but I have passed the pretest

Incredible.

Definitely the best solution here :D.

It is also easy to prove that it is correct — lines have XOR of 0 trivially (split them by 4) and every consecutive even-odd pair in each column have XOR of 1. There is even number of such pairs, so the total XOR is also 0.

you can solve it with xor equals zero, just look at my comment

I got uphacked (59479538) by

3
0 0 1

Because I looped the number to or with up to the last number, instead of to the third-to-last. The tests were definitely pretty weak :P

Yes. I solved it using binary search. Code Search space is the answer range i.e. [0,n]. isValid function checks if it's possible to delete 'mid' number of values such that rest of them are distinct. I used map to store the values and their frequencies in the 'undeleted' array. If the size of map is n-mid for some undeleted part, it means that all the undeleted elements are distinct.

I think you can.If deleting a large portion from a given position gives you a valid sequence then you can check for even smaller portion.

Could anyone explain why this solution 59478005 for F works?

My solution: We want to be able to fix a_i and compute the best (a_j&a_k) for that a_i quickly. To do so, we iterate through i from large to small, and maintain an array cnt[bit] which stores the number of elements among $$$a_{i+1}, a_{i+2}, ..., a_{n}$$$ that have bit as a submask. How to we update cnt? Note that we only need to know if cnt is >= 2 or not. Now, when we have a new element $$$x$$$ to be added, we do something like a dfs, starting by adding 1 to $$$cnt[x]$$$, and then recursing on all submasks of $$$x$$$ that are one bit away from $$$x$$$. If at any point of time we visited the same number or cnt[x]>=2, we can terminate because we know all submasks must also have cnt>=2. Thus, the complexity of updating cnt is amortized $$$O(n\log a_i)$$$. Finally, with the values of cnt you can also find the best answer for a fixed $$$i$$$ in $$$O(\log a_i)$$$ time.

Check this test case: 8 1 2 3 4 1 6 5 4 The correct answer is 2.But your code gives 4 as the output. I guess most of the solutions got failed at system testing in these type of test cases.My solution got failed too.

Try this one:

6
3 2 5 3 1 5

You might have a miscalculation.

4million*log*log is around 400 million, which might not pass because of set constant.

You took the log to the base 10. Base 2 would be more realistic and then it's already $$$5*10^8$$$, also set::insert probably has some additional constant factors.

Same for me mine also getting wrong at testcase 54.

Check out my comment above

Try this one:

6
3 2 5 3 1 5

Контртест к твоему решению: 6 3 3 1 4 3 3 Твоё решение дает ответ 3, правильный — 5

Edit: I found my mistake, Thanks

Maps are not constant complexity. Expected complexity was O(n²log(n)), not O(n²log(n)log(n))

The CF judge is fair to everyone. It's just because your solution is too slow. Having a solution of intended time complexity does not necessarily mean it must pass.

No one cares if you participate or not. This platform is for everyone to learn and improve. If you have done a mistake try to accept it and learn from it, instead of complaining.