MATDYS - Editorial

editorial
, , , ,
16

reading the editorial, and realizing i was so close ,seriously hurts .already solved k-char problem during the LOC, but when u fail to solve the similar problems just by some distance simple hurts , this teaches me that try till the last minute.

17

Edit: Fixed by Vijju123 Corrected code CodeChef: Practical coding for everyone

Original:

What’s wrong with my code/logic It fails on subtask 3 and runs on 1&2 (Lang Python 3) CodeChef: Practical coding for everyone

My logic:
Let N1=2^(N-1){length of subarrays}

If the K is even then it will go in the left part of the array and its position in the left array will be K/2
If the K is odd then it will go in the right part of array and its position in the right subarray will still be K/2 but it will have whole left subarray before it, hence add length of left subarray in it(store length of left subarray in variable pre)
Now in both the cases divide k by 2 (k/=2) and in odd case add N1 in the pre variable, divide N1=N1/2 because length of subarray will decrease by 2 in each run. Repeat this N times and final answer is pre+K

1 Like
18

Whats wrong with my code? Getting wrong answer on test 3 subtask 3.

https://www.codechef.com/viewsolution/15133990
19

Is n’t the Pseudo Code given wrong?

20

Subtask - 2, 3 (Author’s Solution)

Let us try to find the binary representation of K
and the final answer and try to spot some observations based on it. (Assume below that all binary representations are N

bit long).

Let N=3

Below is the table :

    K               ANS
    000             000
    001             100
    010             010
    011             110
    100             001
    101             101
    110             011
    111             111

Do you spot the relationship between the two of them? Yes, the answer is simply the reverse of K

in binary representation.

Thus, we can simply find the binary representation of K
. Then try to construct the answer from the reverse of the binary representation found.

Can someone provide me an implementation of this approach ?? Thanks in advance :slight_smile:

Is this the implementation of the above approach ??

21

Can someone explain the author’s solution in details ?How he arrived at it.

Thanks in Advance

22

The idea was to give a small advantage to careful contestants and Python coders.

23

That was graceful. The concept was thoroughly tested. I like it now…although it made me pull my hair during contest cause i JUST couldnt get it right in c++ hahahahah. Should had been careful :slight_smile:

24

I am sorry this was the case for you!

25

Thanks for such a great problem! Such problems are the cause I give priority to contests over dinner

1 Like
26

Thank you for your feedback!

2 Likes
27

You only needed till 2^63, no? And even after summing, its 2^64-1. 2^64 is out of limits, but 2^64-1 is in limit

28

My point is the solution should’ve been AC then !! But it threw a RE (SIGFPE) error. WHY ??

29

It means you are doing infinite loop somewhere. And getting a RE due to this. Like when an array gets involved in a infinite loop.

30

Try this test case

1

64 18446744073709551615

Second number is 2^64-1.

Actually problem is value of total become 2^64 which cannot fit in unsigned long long.

2 Likes
31

With that attitude of yours, I’d rather not :slight_smile: . Go debug yourself, your code is none of my concern.

1 Like
32

BTW idk why nobody said this, but this is seriously a great editorial @likecs !!

4 Likes
33

THANKS @dushsingh1995

34

why we need to move the number to the left if it is on right?

35

My code was a simply while loop :stuck_out_tongue: , but our ideas are same . First time solved a Q in less than 15 lines XD