×

# SEPT18 - Problem Discussion

 2 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 2.2k●5●15 accept rate: 11% I have asked @admin to move the editorials, they should be there soon, except for the $4$ problems I mentioned in announcement thread. :) (17 Sep, 18:13) 4 Still waiting for AUG18 SAFPAR editorial... (17 Sep, 20:57) meooow ♦6★ @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. (18 Sep, 11:52)

 3 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 5★apptica 939●2●10 accept rate: 17%
 0 What's wrong with my code for XORIER problem My Submission answered 17 Sep, 16:55 318●1●10 accept rate: 1% 1 Convert to long long int. Your AC. return n*(n-1)/2-odd * even; // in range of ~ 1e10.  (17 Sep, 17:03) 1 I was that close XD (17 Sep, 22:42)
 0 Did any one use sqrt-decompositon for solving ANDSQR? answered 17 Sep, 16:57 38●4 accept rate: 11% 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) 3 What is Gilbert's order can you please tell @pshishod2645 (17 Sep, 22:15) droy05284★ 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) droy05284★ showing 5 of 6 show all
 0 ANDSQR was a pretty simple problem. We can see for a specific L, there are at most 30 different ranges that will produce different values. Only store ranges that produce a square. Now our task is answering for a [L...R]. Simple, sort all queries by their right border. Keep moving and update all the Ls on the way. For a L there are at most 2 cases: - R doesn't lie in any range of it. In this case we can simply add all the found ranges of the L in our answer - R lies in a range. Then we see the answer is R - range_L + 1. This can be found by storing 2 other values in the segment tree: Total of range_L and the number of Rs we need (Number of opening ranges). Then obtain the answer is simply sum_prev_range + cntR * (R + 1) - sum_L. Complexity: Updating for a new R takes O(logA), and answering a query takes O(logN). So the total complexity is O(NlogA + QlogN), which will pass easily. answered 17 Sep, 16:59 6★ducpro 240●1●7 accept rate: 0% "We can see for a specific L, there are at most 30 different ranges that will produce different values." can you explain this line?? (17 Sep, 18:20) So for a fixed L, consider a range [R1...R2] that when ANDing all numbers from L to R in this range, you always get the same value. And since there are at most 30 bits to be lost, there are at most 30 different ranges corresponding to 30 different values for this L (17 Sep, 19:57) ducpro6★ In short: you can start off with at most 30 bits, AND can only change things by removing bits, you can remove at most 30 bits. Hence there can only be a handful of places where the value changes, and between those points the value is constant. (17 Sep, 21:36) algmyr7★
 0 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 6★ducpro 240●1●7 accept rate: 0% 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/does-knowing-the-totient-of-a-number-help-factoring-it but there are some things not caught by that, mainly prime powers. (17 Sep, 22:23) algmyr7★ @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/fctr-unofficial-editorial (18 Sep, 04:55) algmyr7★
 0 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 124●5 accept rate: 7% I learned MO algorithm but was unable to come up with a soln. (17 Sep, 17:17) 2 https://www.codechef.com/viewsolution/20007964 My solution using Mo's algorithm. (17 Sep, 20:36) 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 ad-hoc. 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[l-1] - intersectingsolutions intersecting solutions can be found out in LOG^2 A, (17 Sep, 21:29)
 0 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 4★rashomon 81●3 accept rate: 22% You will love TABGAME :D (17 Sep, 18:16)
 0 How to solve BSHUFFLE? answered 17 Sep, 19:12 11●1 accept rate: 0% 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 (17 Sep, 23:29)
 0 The problem BSHUFFLE finds a mention here. answered 17 Sep, 20:46 19●4 accept rate: 0% @admin @vijju123 Please look into this matter (17 Sep, 20:51) 3 Just because it exists on OEIS does not mean it was "copied". (17 Sep, 21:02) meooow ♦6★ 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) 1 As told above by @meooow and @pshishod2645 , I feel its a coincidence. (17 Sep, 21:50) 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) algmyr7★ 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 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. (18 Sep, 00:24) rashomon4★ @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). (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) rashomon4★ 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
 0 I used Mo's algo too... https://www.codechef.com/viewsolution/20170621 answered 17 Sep, 21:46 11●2 accept rate: 0% Early bird catches the worm :p (17 Sep, 22:12)
 0 Can someone help with the Factors problem, please? answered 17 Sep, 22:38 167●1●8 accept rate: 0%

# include<fstream>

using namespace std; int main() { int t,n,arr[100001]; cin>>t; while(t--) { cin>>n; int count[1000001]={0}; long long int ans=0; long long int ce=0; long long int co=0; long long int max=-1; for(int i=0;i<n;i++) {="" cin="">>arr[i]; count[arr[i]]++; if(max<arr[i]) max="arr[i];" if(arr[i]%2="=0)" ce++;="" else="" co++;="" }="" long="" long="" int="" total_pairs="n*(n-1)/2;" long="" long="" int="" odd_xor="ce*co;" long="" long="" int="" even_xor="total_pairs-odd_xor;" long="" long="" int="" zero_xor="0;" for(int="" i="1;i&lt;=max;i++)" {="" zero_xor+="(count[i]*(count[i]-1))/2;" }="" long="" long="" int="" two_xor="0;" for(int="" i="1;i&lt;=max;i++)" {="" if(count[2^i]="">=1) { two_xor+=(count[i]*count[2^i]); count[i]=0; } } ans=even_xor-zero_xor-two_xor; cout<<ans<<"\n"; } return 0; }

PLEASE HELP,USING LONG LONG INT STILL GETTING 10. APPROACH USED: Total pairs-(Pairs having odd Xor)-(Pairs Having XOR=0)-(Pairs Having Xor=2)

02
accept rate: 0%

send the link of this submission here.

(17 Sep, 22:57)

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)

(17 Sep, 22:59)

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

(17 Sep, 23:38)
 0 Hello, Is there any editorial for BSHUFFLE ? Thanks. answered 17 Sep, 22:41 28●4 accept rate: 20% I don't think that it is uploaded... but it will be uploaded soon... (17 Sep, 23:37)
 0 Can anyone please tell me what test case I'm failing for this problem My solution Thank you answered 17 Sep, 22:42 2★kunnu120 518●9 accept rate: 5% Your code fails for this case: 2 2 3 3 (18 Sep, 01:30) My code prints "pofik" for this isn't that right? (18 Sep, 09:48) kunnu1202★ 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) kunnu1202★
 0 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 accept rate: 0% 1 @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. :) (18 Sep, 10:28)
 0 How to solve CHEFZERO problem? answered 19 Sep, 12:17 1 accept rate: 0%
 0 can anyone explain me how to solve the table game question for 100 points ? answered 20 Sep, 08:43 1 accept rate: 0%
 0 whats wrong with my xorier [link text][1] [1]: https://www.codechef.com/viewsolution/20218635 answered 20 Sep, 14:46 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×238
×150