CHKPTS - Editorial

editorial
, , ,
49

@priyansh19077 Thank you:) I also got it after some time. I took this example:

c=3
numbers: 0,9,9

average = 6
number of moves=2+1+1=4

median = 9
number of moves=3+0+0=3 which is lesser.

50

Use Python. Brief and concise.

1 Like
51

Correct me if I’m wrong. Let’s say one point gives a = 2, b = 3, and another point give a = 3, b = 2. Now won’t you be storing them under the same group, when they are clearly a part of two different groups?

52

My approach was a little different than the ones I am seeing here. Still got accepted . Just sharing my approach. For any point (X,Y) , I found the point (A,B) such that B is either 0 or B is closest possible positive value it can take for the given C , i.e the point just above the X axis.
Now , it is clear that if 2 points gives same (A,B) , they can be converged into same points. So, simply the number of distinct checkpoints. Hence , number of Checkpoints needed is number of distinct (A,B).
Now, for number of Opeartions. Say (X1,Y1) ,(X2,Y2) … (Xk , Yk) have same (A,B). Then I can simply sort these K points and the checkpoint will have to me the (k/2)th point in the sorted list.
I simply found the sum of distance (either X or Y) of (K/2)th point from all points and number of operations = (Distance/C).
I did this for all possible (A,B) that was generated.
Proof : - If you have N points on a Line, then the sum of distance of a point from all other points is a decreasing function till (N/2) points and then an increasing fucntion. So, N/2 is the minima.

53

I also tried this
n = a+b
Key = (n*(n+1)) /2 + a
Can you provide me a case where this will fail

54

That is some brilliant hashing. I don’t think there will be collisions. Are you sure the rest of your algorithm is solid?

[UPD]: I tried the hash that you have specified with my (AC) algorithm and it gives a WA. The problem has to be the hash function. I was able to find a case with -ve b. I know b cannot be negative, but I’m sure we’ll be able to find a collision for a,b > 0.
Pair 1: a = 3, b = -2
Pair 2: a = 1, b = 1

In general, it’s always better to use the std hash to hash the pairs. This can be easily done by initializing your hashmap as unordered_map<pair<int, int>, typename>. This is always better than coming up with a custom hash for pairs :stuck_out_tongue: (especially in a short contest).

55

Select any. It wont matter.

57

Thanks a lot! I was facing the BUG1 really helped me debug really fast.

58

Can someone tell mistake in my code, it is almost same as in editorial

Please find my solution here:- My solution

PS: I even tried ((x % c) + c) % c) in map from editorial but still WA.

59

You need to find the minimum number of times that so that you move the checkpoints.

Consider this example in 1D plane 1 3 8 and let c be 1, here mean is 4 and the median is 3. If you move them to mean you will move all 3 to 4 and that gives me 3 + 1 + 4 but in case of median we have 2 + 0 + 5.

60

Yeah, I understood there must be some collision. Actually i write code in java so i have to write custom pair class to go to. I tried with custom pair class by manipulating hash and equals function and it got AC. Didn’t work out during contest. It’s good that i atleast learned something. Would be great if i could able to find the collision.

61

Oh! To tackle that maybe you can use a 2D map? Map<Integer, Map<Integer, ArrayList>> . I don’t know java, i’m just guessing.

1 Like
62

Yeah, but that will increase a lot lines of code. I will also be a solution in this case.

1 Like
63

CodeChef: Practical coding for everyone.
I am not getting why my code is throwing a TLE, any help would be appreciated.

64

Thanks mate …i got it!

66

Thanks a ton man, you saved my time for Bug1.

67

I just forgot to divide my answer by c. Btw thanks for your help and suggestions @priyansh19077

68

can you plzz help me.
i am getting WA
can u tell me what i am doing wrong
https://www.codechef.com/viewsolution/35763007

69

After finding the groups on basis of (x-y), for each of the group_i, again form group_{ij} on basis of x mod c. Also, take care for negative values of the remainder.
The number of checkpoint is count(group_{ij}) and no. of moves needed should be summed over all such groups.
You need to start by creating groups from the vector on line 60 in your linked submission.

1 Like
70

why do we need to make another group for x mod c.
only using (x-y) group is also giving the same value for the test case.

can u explain me the reason … :relaxed: :relaxed:

1 Like