SEPT18 - Problem Discussion

copy paste

Hey guys!!

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 :slight_smile:

So, which was your favourite problem? I struggled with Power Tree.

Let the discussion begin!

/copy paste

3 Likes

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

Did any one use sqrt-decompositon for solving ANDSQR?

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.

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

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

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.

1 Like

How to solve BSHUFFLE?

1 Like

The problem BSHUFFLE finds a mention here.

2 Likes

I used Mo’s algo too…

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

Can someone help with the Factors problem, please?

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

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)

Hello,

Is there any editorial for BSHUFFLE ?

Thanks.

Can anyone please tell me what test case I’m failing for this [problem][1]

[My solution][2]

Thank you
[1]: https://www.codechef.com/SEPT18B/problems/CHEFADV/
[2]: https://www.codechef.com/viewsolution/20212619

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

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

How to solve CHEFZERO problem?

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

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

Convert to long long int. Your AC.

return n*(n-1)/2-odd * even; // in range of ~ 1e10.
1 Like