CHKPTS - Editorial

editorial
, , ,
13

I did the very same thing, in Java, got TLE: CodeChef: Practical coding for everyone

I guess Java performs poorer, despite that the time threshold is increased for it.

14

thanks bro

15

very nice problem !!
thanks!!

16

Nice problem. Setter’s implementation is clever. I had to group coordinates twice because of not using pair for mapping. And I thought about selecting the median, but I wasn’t sure about this. Luckily I found out that the cost function is uni-modal. So I used ternary search to find the number of moves.

1 Like
17

and for this all kind of modular arithmetic i made some functions so that in contest time , at least these type of error will not happen -

ll modmul(ll a, ll b) {
    return ((a%mod) * (b%mod)) % mod;
}

ll modadd(ll a , ll b){
    return((a%mod)+(b%mod)+mod)%mod;
}

ll modsub(ll a , ll b){
    return((a%mod) - (b%mod) + mod)%mod;
}
2 Likes
18

I knew how to deal with mod on negative numbers but still got WA.I didn’t read the constraints that the co-ordinates could be negative.

Code which got WA on 47th minute of the contest
AC code
Both of them differ only in line 62.
Goodbye, 5 stars dream!

19

Goodbye, 5 stars dream!

Why?! Come on, just see how fluctuating my rating is! That’s because I never guard it as a treasure, and always participate, so that I can learn new things. And that’s why I have been destroying it dozens of times. I used to be 5 stars once.
Of course your dream is not gone. One day it will happen. Believe in yourself! :slight_smile: Come here any time a contest takes place, and learn new stuff.

Also, see my Java code, it does exactly what the editorial says, but it gets TLE. What should I say? :slight_smile: It is not fair to get advantage only because your language of choice is C/C++. But this is life. It is hard-to-impossible to say simply that JavaLimit = 2*CLimit.

1 Like
22

I think the problem statement states that c > 0. Hence the answer should be no.

23

Ahh yeah …even I did same mistake :persevere:

1 Like
24

Can someone help me find the bug in my solution? Here it is. I am doing exactly like the editorial states.

26

Yeah, you get so used to positive-only questions that you don’t even notice when they can be negative. Anyway, don’t you think it is nice to know that you knew everything you needed to solve the problem. I think that’s far more important than handing in an AC solution in time.

3 Likes
27

can you explain more about mistake @priyansh19077
here is my solution…please look at this too
https://www.codechef.com/viewsolution/34624892

28

Nice Idea, I have added a new snippet with this to sublime text

I have also added modpow and modinv for the modular power function and the modular inverse. On top of that I have added some inline variants.

I might actually turn it into a class with operator+, operator-, operator*, operator/ to allow calculations as normal and handle modular arithmetic in the background. And then of course turn that class into a snippet.

1 Like
31

nvm, figured it out. I was calculating mod 2c instead of just c. Still gives errors. Here is the updated code

33

@taran_1407 Why can’t we use average instead of median? Please provide some example.

1 Like
34

Hi guys checkout this video solution :raised_hands::raised_hands:

3 Likes
35

I agree, it’s great to see that I got all the right ideas in my head, 100%. Much more important than the AC.

36

try out the case when you have the numbers 1, 5, 17. If you find out the average for this it will be (1+5+17)/3 which will not be an integer. Now, if you talk about the average element that can be integer, then you can consider it like this. suppose 1 is the 1st term in the AP, then 17 will be the 5th term in this AP. So by this if you take the 3rd term as the average it will be 9. The number of moves for 9 will be (9-1)/4 + (9-5)/4 + (17-9)/4 = 5
Now, if you take the median element which is 5, the answer will be (5-1)/4 + (5-5)/4 + (17-5)/4 = 4
So, clearly taking the median element and not the average in any way can get you the right answer. I was doing the same mistake during the contest but realized it only after reading the editorial.

1 Like
37

Sure.

  1. DON’T use set or unordered set anytime in this problem as the points given in the input can also be same. I had used set to keep the numbers and also the pairs sorted, but this will fail when you want to calculate the exact number of moves.
  2. While calculating the number of moves for each sub-group, take the median of these elements and not the average of these numbers, or the average integer of these numbers.
  3. Check for the case where your code might be taking the mod of any negative numbers, because there can be really weird exceptions in that. For handling this, you can just subtract the value of the first number from each element of the particular group, by this the modulus of these numbers won’t be affected and all the numbers will become positive when you will take the mod.
  4. Make use of C++ STL as much as possible, the code will become easy to understand and debug.
2 Likes
38

can somebody help me find the issue . I coded this after reading the editorial because i could not solve it during the contest. seems like i couldn’t solve even after reading the editorial.
https://www.codechef.com/viewsolution/34633642