SEPT18 - Problem Discussion

general
,
41

send the link of this submission here.

42

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)

43

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

44

I donā€™t think that it is uploadedā€¦ but it will be uploaded soonā€¦

45

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))

46

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
47

Thanks @pshishod2645

48

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
49

@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).

50

Your code fails for this case:

2 2 3 3
51

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

52

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

2 Likes
53

@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?

54

My code prints ā€œpofikā€ for this isnā€™t that right?

55

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

56

@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
57

@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
58

@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
59

@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.

60

oh okay thank you!!