Unofficial editorials December Long challengr Part 2

editorial
,
21

I went into shock for some seconds on seeing the solution at first :stuck_out_tongue:

22

For the CHEFHAM I used a slightly different approach but got only 60pts because of one test case going wrong. Can somebody figure out where might I go wrong?

Here is my


[1]

I handled palindromes and non-palindromes separately.


  [1]: https://www.codechef.com/viewsolution/16548324
23

I donā€™t think seg tree solution is possible for this problem.

24

The 20 marks i.e. subtask 1 was meant to pass if we take xor of every subarray starting from 1, i.e. (1-1, 1-2, 1-3, 1-4) by linear traversing, instead of using previous xor value.

25

For CHEFHAM I used the following approach. If n > 3 break the array into two subsequences of length greater than 1, each consisting of unique elements, and cyclically shift each subsequence. Otherwise cyclically shift the longest subsequence consisting of unique elements. All of this can be done in a single pass.

Solution.

26

Thats quite differentā€¦ @eugalt

27

I am also getting TLE with the square root decomposition technique in c++. In Subtask 3, just one test case(the first one) is getting passed and others are TLE. Please Help!

28

hi Taran,
I have done this in O(n) and my code run in less than (0.1)sec for all test cases.
Just see my code.I think my solution is most optimised than the above posts.

https://www.codechef.com/viewsolution/16551893

29

Mate, thereā€™s no limit to efficieny. I have just checked and found that fastest c++ has runtime of 0.03 secondsā€¦

Keep trying till u get the best runtimeā€¦

30

My solution for CHEFHAM: https://www.codechef.com/viewsolution/16511540

I LOLā€™ed hard after this passed.

6 Likes
31

Wowā€¦ Something random it isā€¦

32

Use 2d array instead of map.
Did the same mistake

33

tried but it also failed !

34

Those who are getting TLE for CHEFEXQ, use normal array instead of an map/Hashmap. Map increases the time complexity by additional logn factor per query.

In order to set all index of certain block to zero during an update operation, instead of traversing whole array, first decrement all previous indices stored in block and then update the block( see code for further clarification.).

Here is my code getting TLE using map data structure.

https://www.codechef.com/viewsolution/16555697

Here is my code getting accepted after using array.

https://www.codechef.com/viewsolution/16555808

1 Like
35

Well, sorry it ran in 0.16 seconds - I hadnā€™t used fast I/O methods. Iā€™m a newbie around here, so I didnā€™t know about it at that point

36

Interesting, is there a way to break it? Actually for small Nā€™s your program kind of goes over all permutations, for large Nā€™s, it is very hard to construct a counterexample that can break it.

37

For maximum frequency = 2, i can guarantee that we canā€™t fault this solution, because of very high number of acceptable permutations of given array.

In case we are given maximum frequency X instead of 2, worst case for this solution would be

N = 2*x followed by N elements. N elements shall consist of i values being a, and remaining i being b.

Even in this case, probability of favourable permutations is (i!)^2/(2*i)!.

But this was the probability of getting correct answer in one iteration.

38

So we need to make N upto a limit, for which (MAX_ITER*(i!)^2)/(2*i)! Will be reasonably less, say below 0.5.

After finding a suitable N, Set T, then following test case T times.

N (as found above)

(a a a ā€¦ i times) (b b bā€¦i times)

I believe this test file will fail not only this, but any randomized algorithm.

ONLY IF WE MAXIMUM FREQUENCY WAS GIVEN X UPTO N/2.

Coreect me if i am wrong, as this is my first time developing a test case to hack a randomized solution.

39

thanks taranā€¦

40

taran give me some advice to solve medium hard problems on codechef