copy paste Hey guys!! Finally after 10 tiring days the A̶u̶g̶u̶s̶t̶ September long concludes. Lets share our approaches for the problems here while editorials for problems come out (at this moment none n̶o̶t̶ ̶a̶l̶l̶ of them are out)? Got any interesting approach which you cant wait to share? The wait is over :) So, which was your favourite problem? I̶ ̶h̶a̶d̶ ̶b̶e̶s̶t̶ ̶t̶i̶m̶e̶ ̶s̶o̶l̶v̶i̶n̶g̶ ̶I̶n̶t̶e̶r̶a̶c̶t̶i̶v̶e̶ ̶M̶a̶t̶r̶i̶x̶ ̶:̶)̶.̶ ̶T̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶g̶a̶v̶e̶ ̶m̶e̶ ̶a̶ ̶r̶u̶n̶ ̶f̶o̶r̶ ̶m̶y̶ ̶s̶c̶o̶r̶e̶ ̶x̶D̶ ̶̶ ̶s̶o̶ ̶I̶ ̶l̶e̶t̶ ̶h̶e̶r̶ ̶s̶t̶a̶y̶ ̶w̶i̶t̶h̶ ̶d̶r̶a̶g̶o̶n̶s̶ ̶a̶n̶d̶ ̶b̶e̶ ̶b̶y̶ ̶h̶e̶r̶s̶e̶l̶f̶ ̶t̶h̶e̶n̶ :p But on a serious note, anyone who was able to ANDSQR s̶a̶v̶e̶ ̶t̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶(̶o̶r̶ ̶p̶r̶i̶n̶c̶e̶.̶.̶.̶? :p). I kept on getting TLE W̶A̶ for larger TCs, so I appreciate any approaches for it :) Let the discussion begin! /copy paste asked 17 Sep, 16:39

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. answered 17 Sep, 23:47

What's wrong with my code for XORIER problem My Submission answered 17 Sep, 16:55
1
Convert to long long int. Your AC.
(17 Sep, 17:03)
1
I was that close XD
(17 Sep, 22:42)

Did any one use sqrtdecompositon for solving answered 17 Sep, 16:57
A good sqrt solution has a reserved spot in hall of fame solutions of this long for ANDSQR. Got any?
(17 Sep, 18:16)
1
I used mo’s algorithm to solve the problem My AC solution: https://www.codechef.com/viewsolution/20007964
(17 Sep, 20:00)
1
@vijju123 the normal sqrt will not pass because of $O((n+ q)\sqrt{n})$, and q is bit large, to get AC you will have to use Gilbert's order
(17 Sep, 21:42)
1
This is it Gilbert's Order, and as I realised it in this long challenge it's pretty much efficient than normal sorting order (especially when queries are large compared to n)
(17 Sep, 22:41)
Thanks @pshishod2645
(17 Sep, 23:53)
showing 5 of 6
show all

Wanna ask on approaches to CHEFLST and FACTORIZE. Did anyone here complete those 2? Please share your solutions, they bugged me for a long time answered 17 Sep, 17:04
Same here XDDDDDDD
(17 Sep, 18:17)
Factorize boils down to Euler's theorem and some cleverness. my code is somewhat commented, but I'm not sure how easy it is to follow. https://www.codechef.com/viewsolution/20093928 The main idea can be found in https://math.stackexchange.com/questions/191896/doesknowingthetotientofanumberhelpfactoringit but there are some things not caught by that, mainly prime powers.
(17 Sep, 22:23)
@algmyr I got the same link but can't understand anything except the fact that there are some keywords related to maths... :(
(17 Sep, 22:27)
2
I decided to write a small editorial on FCTR: https://discuss.codechef.com/questions/135460/fctrunofficialeditorial
(18 Sep, 04:55)

I like the problem ANDSQR. It helped me learn Segment Trees. Though I could not solve it, I learnt a lot from it. answered 17 Sep, 17:11
I learned MO algorithm but was unable to come up with a soln.
(17 Sep, 17:17)
I first submitted with MO's algorithm but got TLE, I thought of giving Gilbert's order a try but I thought it won't affect the solution much, and did it differently, but after seeing yours (@codebreaker123 's )submisson, I realised that Gilbert's order is indeed very efficient.
(17 Sep, 21:25)
My AC'ed solution for and segments is nothing more than adhoc. there can be atmost LOG A, different numbers starting from some fixed L, Using this I calculate ans for range (0, R) for all R, now ans of a query l, r is ans[r] ans[l1]  intersectingsolutions intersecting solutions can be found out in LOG^2 A,
(17 Sep, 21:29)

I solved both BSHUFFLE and TABGAME after observing patterns in the test cases. I did not get an intuitive explanation for either (maybe for TABGAME). Interested to see the editorial. answered 17 Sep, 17:43

The problem BSHUFFLE finds a mention here. answered 17 Sep, 20:46
3
Just because it exists on OEIS does not mean it was "copied".
(17 Sep, 21:02)
1
@meooow agreed. Oesis contains lot of things which we don't know about and setters obviously can't check each webpage on oesis to know that if it's there
(17 Sep, 21:31)
3
It's interesting that the bad permutations mentioned are called "empirical". I expected there to be some motivation as to why the permutations were minimum/maximum.
(17 Sep, 22:27)
2
I actually remembered this was a question in CLRS (5.3.3). I researched for a bit in that direction. The Wikipedia link for FisherYates 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.
(18 Sep, 00:24)
@rashomon: The FisherYates shuffle is a bit different from BSHUFFLE. In FisherYates, $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).
(18 Sep, 01:15)
Because a research paper on this exists => possibility of existence on OEIS.
(18 Sep, 02:54)
@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?
(18 Sep, 05:14)
1
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
(18 Sep, 10:58)
Well, I'm sorry for using the word 'copied'. I should have written that it finds a mention.
(20 Sep, 19:35)
But at the same time, it seems to me that it is not a coincidence, because the problem name "bad shuffle" is the same as the title of the page I have given the link to.
(20 Sep, 19:38)
showing 5 of 12
show all

I used Mo's algo too... answered 17 Sep, 21:46

Can someone help with the Factors problem, please? answered 17 Sep, 22:38

Hello, Is there any editorial for BSHUFFLE ? Thanks. answered 17 Sep, 22:41

answered 17 Sep, 22:42
Your code fails for this case:
(18 Sep, 01:30)
My code prints "pofik" for this isn't that right?
(18 Sep, 09:48)
1
@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.
(18 Sep, 10:20)
oh okay thank you!!
(18 Sep, 18:52)

What is Wrong in my solution of Chef and Adventures September long challenge 2018.Thanks in Advance.
link
This answer is marked "community wiki".
answered 18 Sep, 10:19
1
@nitin21897: Your code fails on for the input
(18 Sep, 10:28)

can anyone explain me how to solve the table game question for 100 points ? answered 20 Sep, 08:43

whats wrong with my xorier [link text][1] [1]: https://www.codechef.com/viewsolution/20218635 answered 20 Sep, 14:46

I have asked @admin to move the editorials, they should be there soon, except for the $4$ problems I mentioned in announcement thread. :)
Still waiting for AUG18 SAFPAR editorial...
@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.