You are not logged in. Please login at www.codechef.com to post your questions!

×

SEPT18 - Problem Discussion

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

aryanc403's gravatar image

5★aryanc403
2.2k515
accept rate: 11%

edited 22 Oct, 00:23

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) vijju123 ♦♦5★
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) vijju123 ♦♦5★

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.

link

answered 17 Sep, 23:47

apptica's gravatar image

5★apptica
939210
accept rate: 17%

What's wrong with my code for XORIER problem My Submission

link

answered 17 Sep, 16:55

harrypotter0's gravatar image

4★harrypotter0
318110
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) aryanc4035★
1

I was that close XD

(17 Sep, 22:42) harrypotter04★

Did any one use sqrt-decompositon for solving ANDSQR?

link

answered 17 Sep, 16:57

devilhector's gravatar image

2★devilhector
384
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) vijju123 ♦♦5★
1

I used mo’s algorithm to solve the problem My AC solution: https://www.codechef.com/viewsolution/20007964

(17 Sep, 20:00) codebreaker1234★
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) pshishod26454★
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) pshishod26454★
(17 Sep, 23:53) droy05284★
showing 5 of 6 show all

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.

link

answered 17 Sep, 16:59

ducpro's gravatar image

6★ducpro
24017
accept rate: 0%

edited 17 Sep, 17:00

"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) ankit00384★

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★

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

link

answered 17 Sep, 17:04

ducpro's gravatar image

6★ducpro
24017
accept rate: 0%

Same here XDDDDDDD

(17 Sep, 18:17) vijju123 ♦♦5★

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) l_returns4★
2
(18 Sep, 04:55) algmyr7★

I like the problem ANDSQR. It helped me learn Segment Trees. Though I could not solve it, I learnt a lot from it.

link

answered 17 Sep, 17:11

ruddradev's gravatar image

3★ruddradev
1245
accept rate: 7%

I learned MO algorithm but was unable to come up with a soln.

(17 Sep, 17:17) aryanc4035★
2

https://www.codechef.com/viewsolution/20007964

My solution using Mo's algorithm.

(17 Sep, 20:36) codebreaker1234★

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

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

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.

link

answered 17 Sep, 17:43

rashomon's gravatar image

4★rashomon
813
accept rate: 22%

You will love TABGAME :D

(17 Sep, 18:16) vijju123 ♦♦5★

How to solve BSHUFFLE?

link

answered 17 Sep, 19:12

snehal_kr's gravatar image

3★snehal_kr
111
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) l_returns4★

The problem BSHUFFLE finds a mention here.

link

answered 17 Sep, 20:46

ankit_btech's gravatar image

3★ankit_btech
194
accept rate: 0%

edited 20 Sep, 19:39

@admin @vijju123 Please look into this matter

(17 Sep, 20:51) jagreetdg4★
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) pshishod26454★
1

As told above by @meooow and @pshishod2645 , I feel its a coincidence.

(17 Sep, 21:50) vijju123 ♦♦5★
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) code_blast4★

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

(18 Sep, 02:54) aryanc4035★

@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

@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

(18 Sep, 10:58) aryanc4035★

Well, I'm sorry for using the word 'copied'. I should have written that it finds a mention.

(20 Sep, 19:35) ankit_btech3★

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) ankit_btech3★
showing 5 of 12 show all
link

answered 17 Sep, 21:46

vatsal1998's gravatar image

4★vatsal1998
112
accept rate: 0%

Early bird catches the worm :p

(17 Sep, 22:12) vijju123 ♦♦5★

Can someone help with the Factors problem, please?

link

answered 17 Sep, 22:38

hideintree's gravatar image

4★hideintree
16718
accept rate: 0%

include<iostream>

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)

link

answered 17 Sep, 22:39

coldfire8549's gravatar image

2★coldfire8549
02
accept rate: 0%

send the link of this submission here.

(17 Sep, 22:57) harrypotter04★

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

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

Hello,

Is there any editorial for BSHUFFLE ?

Thanks.

link

answered 17 Sep, 22:41

semantycs's gravatar image

2★semantycs
284
accept rate: 20%

I don't think that it is uploaded... but it will be uploaded soon...

(17 Sep, 23:37) l_returns4★

Can anyone please tell me what test case I'm failing for this problem

My solution

Thank you

link

answered 17 Sep, 22:42

kunnu120's gravatar image

2★kunnu120
5189
accept rate: 5%

Your code fails for this case:
2 2 3 3

(18 Sep, 01:30) the_extractor4★

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

oh okay thank you!!

(18 Sep, 18:52) kunnu1202★

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

nitin21897's gravatar image

2★nitin21897
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) code_blast4★

How to solve CHEFZERO problem?

link

answered 19 Sep, 12:17

xxxxxx312c's gravatar image

3★xxxxxx312c
1
accept rate: 0%

can anyone explain me how to solve the table game question for 100 points ?

link

answered 20 Sep, 08:43

shubh_1998's gravatar image

3★shubh_1998
1
accept rate: 0%

whats wrong with my xorier [link text][1] [1]: https://www.codechef.com/viewsolution/20218635

link

answered 20 Sep, 14:46

shvenktesh9's gravatar image

2★shvenktesh9
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 17 Sep, 16:39

question was seen: 2,310 times

last updated: 22 Oct, 00:26