Unofficial editorials December Long challengr Part 2

editorial
,
2

Hi taran,

I have solved CHEFHAM using sorting. Make one copy of given array and sort it. Iterate the sorted and array put the element x at index having value ceiling(x) in original array. if ceiling(x) is null put it at the at the index having vacant space as well as lowest value.

my solution

3

I think my solution is the same as what chef_keshav is saying (in C++ though). I believe I had nlogn complexity and my solution ran in 0.33 seconds.

here

4

CodeChef: Practical coding for everyone

How even in the world can this solution pass all the test cases? Or am in not seeing something? :frowning:

5

CHEFEXQ problem had weak test cases, a lot of O(NQ) solutions managed to pass all test cases and get AC which is really disappointing.

6

Is there no other method of solving CHEFEXQ problem? If there is can somebody please explain it to me. Thank You

7

@taran_1407 I attempted the problem CHEFEXQ as you explained above

My Code:- Link to my code

Where am I getting it wrong? Please have a look at my code.

8

CHEFHAM can be solved in so many ways . The test cases were weak enough for hit and trial for obtaining the solutuion .
CHEFEXQ scoring was bit weird too . The most basic brute force solution of CHEFEXQ was able to fetch 50 points. THere was no need for three different scoring brackets .

Anyways thanks for the editorials . Keep up the good work Taran :slight_smile:

9

Thanks for the editorial.
Can we do CHEFEXQ with segment trees in any way?

10

Hey @taran_1407, used same method for CHEFEXQ but getting TLE. Doing Square_Root_Decomposition, storing frequencies in unordered_map, used lazy technique for update task, still getting TLE.

Here is MY CODE .

11

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
12

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.

13

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!

14

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.

CodeChef: Practical coding for everyone

15

My solution for CHEFHAM: CodeChef: Practical coding for everyone

I LOL’ed hard after this passed.

6 Likes
16

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
17

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

18

What’s wrong in my code…can anybody help me out, plz…

Here is my


[1]
  [1]: https://www.codechef.com/viewsolution/16560604

Thanks...
19

For CHEFHAM, I tried a different approach, I broke the array in subarrays of length two, now there can be two cases:

  1. Both the elements in a subarray are different, then just swap the elements
  2. If both the elements in a subarray are same, swap the position of this subarray with the nearby subarray.

Take care of the last element left for odd n.
Here is the link to my solution :


[1]


  [1]: https://www.codechef.com/viewsolution/16516552
1 Like
20

@taran_1407 can u post a link to your segment tree solution for chefexq

21

@taran_1407 thanks for the editorial. For the problem CHEFHAM, shouldn’t there a break after swapping the two positions in your code?