SEPT18 - Problem Discussion

general
,
1

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
2

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

3

Did any one use sqrt-decompositon for solving ANDSQR?

4

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

Convert to long long int. Your AC.

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

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

7

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

8

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

9

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
10

I have asked @admin to move the editorials, they should be there soon, except for the 4 problems I mentioned in announcement thread. :slight_smile:

11

A good sqrt solution has a reserved spot in hall of fame solutions of this long for ANDSQR. Got any?

12

You will love TABGAME :smiley:

13

Same here XDDDDDDD

14

“We can see for a specific L, there are at most 30 different ranges that will produce different values.”

can you explain this line??

15

How to solve BSHUFFLE?

1 Like
16

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

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

1 Like
18

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

My solution using Mo’s algorithm.

2 Likes
19

The problem BSHUFFLE finds a mention here.

2 Likes
20

@admin @vijju123 Please look into this matter