SEPT18 - Problem Discussion

send the link of this submission here.

Also the formula used should be

ans = (pairs having even values ) - (pairs having XOR =0 ) - (pairs having XOR= 2)

(pairs having even values ) = (n*(n-1)/2) - (pairs having odd sum)

Observe your answers for n=1 to 7 and rewrite program to make it O(n) just print pattern accordingly (yes it forms a pattern)
HERE is my solution

I don’t think that it is uploaded… but it will be uploaded soon…

Yes Pairs having even values = (total pairs i.e.(n*(n-1)/2))-(pairs having odd XOR (i.e. count of even no X count of odd numbers))

I don’t understand why good problems do not get editorials. Waiting for the editorial of SAFEPAR(AUG18) till now and again for this contest too :(. I think many people dislike this part about the challenge.

3 Likes

Thanks @pshishod2645

I actually remembered this was a question in CLRS (5.3.3). I researched for a bit in that direction. The Wikipedia link for Fisher-Yates mentions this incorrect shuffle and states that the most likely position for a digit to end up in is one position back, which turns out to not be the right answer. Had to brute force small cases to find the pattern. The OEIS link did not turn up in my search.

2 Likes

@rashomon: The Fisher-Yates shuffle is a bit different from BSHUFFLE. In Fisher-Yates, j can be chosen only between i and n - 1 (0 - indexing), whereas in BSHUFFLE, j can be chosen between 0 and n - 1 (when 0 - indexing).

Your code fails for this case:

2 2 3 3

Because a research paper on this exists => possibility of existence on OEIS.

I decided to write a small editorial on FCTR: https://discuss.codechef.com/questions/135460/fctr-unofficial-editorial

2 Likes

@code_blast True. CLRS asks us to prove that this is a biased shuffle, which is fairly easy. However, finding the permutations which are most and least biased was much more difficult. I’m interested to know if there’s a theoretical proof as to why the target permutations follow the pattern that they do.

@aryanc403 Could you link to that research paper?

My code prints “pofik” for this isn’t that right?

What is Wrong in my solution of Chef and Adventures September long challenge 2018.Thanks in Advance.

@kunnu120: No, your code should print “Chefirnemo” because from initial state of (1, 1), Chef can just install ShareChat app once to make it (2, 2) which, as you can see, is reached irrespective of what the values x and y are.

1 Like

@nitin21897: Your code fails on for the input 1 4 3 3. It prints Pofik while the answer is Chefirnemo because from an initial state of (1, 1), Chef can do a push-up increasing his power by 3 and hence reaching the state (1, 4). Note that adding X to N and Y to M are independent of each other. You may add any of them any number of times (even 0 times if needed). Hope this helps. :slight_smile:

1 Like

@rashomon

It is present there the editorial which was uploaded but then taken back. So it will be available when the editorial will be back again.

Edit - Anyways I found it in my browsing history. Paper

1 Like

@admin is having difficulty moving editorials of remaining 3 problems of div2. I will see if I can post them directly here myself. Sorry for the delay, i didnt check their status yesterday assuming that they’d be moved.

oh okay thank you!!

//