### satyam343's blog

By satyam343, 21 month(s) ago,

Thank you for participation! I hope you liked atleast one problem from the set (:

We tried hard to have an interesting problemset.

It is sad to see people disliking the round only because some problems were hard. Please read the intended solutions to know why we decided to put the problems(especially D) at current positions.

1762A - Divide and Conquer

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762B - Make Array Good

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762C - Binary Strings are Fun

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762D - GCD Queries

Idea:amurto Prepared by:errorgorn

Hint 1
Hint 2
Hint 3
Solution
Code

1762E - Tree Sum

Idea:satyam343 Improved by:TheScrasse

Hint 1
Hint 2
Hint 3
Solution
Code

1762F - Good Pairs

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code
• +240

| Write comment?
 » 21 month(s) ago, # | ← Rev. 2 →   +12 Great Round!! Indeed, problems were quite hard but doable, but overall a v.good experience!
 » 21 month(s) ago, # |   +38 So I solved the problem D a little differently, I tried to make use of the fact that we can always take multible of some number x > 1 and dump all the other elements in the array and zero will always be multiple, this give n + n / 2 + n / 4 — = 2n queries in total. There is a lot of case handling but You can look at my code to understand it a little better for e.g. if x == 2, than we can just dump all elements except 0 — 4 — 6 — 8 — 10now the next smallest multiple we can take is 4 than we have 0 — 8 — 12 -16 If we take zero, than all the elements in gcd(pi, 0) will be different hence we can just use zero or pi that gives largest valueLINK FOR THE SOLUTION : https://mirror.codeforces.com/contest/1762/submission/185393565
•  » » 21 month(s) ago, # ^ |   +17 The first step to find a not-1 position costs $\lfloor \frac{n}{2} \rfloor$ querys. The second step cost about $n(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots)$ querys. Why the total cost can be limited to $2n$?
•  » » » 21 month(s) ago, # ^ |   +7 I think we can use a simple idea to deal with the first not-1 position, that is to eliminate not-0 positions as well. You can query (i,i+1), (i,i+2), (i+1,i+2). If they are all ones, you can be sure they are not 0, so remove them from the possible answers, otherwise, you found your first not-1 position. Lmk if I missed anth.
•  » » » » 21 month(s) ago, # ^ |   +3 Yeah, as I have done that using vector p2, for each i, if gcd(i, i — 1) and gcd(i, i + 1) is 1 than this number can not be 1, reason being, x, 0, y, now if zero was in the middle, gcd(x. 0) = x and gcd(0, y) = y so max(x, y) > 1 because distinct elements in permutaion, there is this case where 0 was first or last element and you never find any element in middle just use that as edge case and print 1 n
•  » » » » » 21 month(s) ago, # ^ |   0 Also the idea that half of numbers are even can be employed. One can query pairs (1, 2), (3, 4), ... until gcd is 1. If there's no such index encountered we can also query (1, 4) and (1, 3) to finally find the index of a number that is not 1 or that is even. Then we put it at first place and find all gcds of it and with all the other numbers, collect stat and leave only those indices that have the greatest gcd encountered. Repeat until we have two numbers left.
•  » » 21 month(s) ago, # ^ |   +7 i did exact same apprroach but got WA on test 5 can u please help https://mirror.codeforces.com/contest/1762/submission/185370228
•  » » » 21 month(s) ago, # ^ |   0 even my solution failed on exactly the same test case . if you are able to find the mistake please reply https://mirror.codeforces.com/contest/1762/submission/185422415
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 1 2 4 6 8 7 3 5 0 I used same approach and then i found on the above mentioned test case it takes 19 queries.
•  » » » » 21 month(s) ago, # ^ |   0 mine submissions takes 15 submission which is in range
•  » » 21 month(s) ago, # ^ | ← Rev. 4 →   +3 I used a similar approach and stress-tested it on all permutations of size 10, it passed them all. Not sure what the problem is.Here is my approach, I maintain a list of possible indexes which are initially all indexes. In each round, I query the gcd of the first element with all other elements. Now the maximum result I get must be the value of the first element and all of its multiples including 0 must give the same value. I repeat rounds till the number of possible elements becomes 1. If the number of elements giving maximum gcd is 1, then my first element must either be a co-prime to all elements with the maximum gcd element being 0, or the first element must be 0. So I answer with the first element and the element giving maximum gcd.Edit- I found the error thanks to propane. I am exceeding query limit when the first element is 1
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 i had exactly same approach and for the exceeding query limit when the first element is 1 i used the fact that if for an index on the first 2 queries it got gcd 1 it cant be 0 so i terminated the process there and deleted this index and moved forward but still query limit exceeded came :(
•  » » 21 month(s) ago, # ^ |   0 I also came up with this solution! But sadly i couldn't participate in the contest
 » 21 month(s) ago, # | ← Rev. 4 →   0 Problem A can use __builtin_ctz(x) for even numbers or __builtin_ctz(x+1) for odd numbers. link: https://mirror.codeforces.com/contest/1762/submission/185402449
•  » » 21 month(s) ago, # ^ |   0 can you explain it more?
•  » » » 21 month(s) ago, # ^ | ← Rev. 3 →   +3 __builtin_ctz counts the number of trailing zeros of the number in binary form. To change parity is to change the least significant bit (LSB) from 0 to 1 or vice versa. For example, say we have 11100 (with 2 trailing zeros), two divisions/right-shift operations are needed to change the LSB. +1 for odd numbers to convert trailing ones to trailing zeroes.
•  » » » » 21 month(s) ago, # ^ |   0 Damn clever!
 » 21 month(s) ago, # |   +9 I really enjoyed this round. The implementation of the first four problems is quite easy. In this way the problems become purely observational.Keep up with the good rounds!
 » 21 month(s) ago, # |   +11 Intended solution for D is genious.
 » 21 month(s) ago, # |   +5 My solution for problem C was a bit different from the editorial. Did that after processing each character I found the number of spaces or free positions where 0/1 may be put that is we have two options for that position. Now we can every time add the 2^spaces to the answer and take respective modulo as well.
•  » » 5 weeks ago, # ^ |   0 (https://mirror.codeforces.com/contest/1762/submission/275475939) I followed the same logic,can you tell why does mine give wrong ans for TC3?
 » 21 month(s) ago, # |   0 Can't believe I'm doing this , but alright — I have Idea for D: 1) First we ask n — 1 queries of format ? 1 i, 2 <= i <= n . We will remember all the answers we getMaximum of all those gcds = a[1], right? Unless all the answers are distinct and are from 1..n-1 — in this case a[1] == 0, and then we can output ! 1 2Okay, so we know the value of a[1] and we know all the positions j , that gcd(a[1], a[j])==x, for each x2) Let's take all positions where gcd(a[j], a[1])==a[1] ( we could've remembered this from step 1). For example we have 2, 3, 7 9( it means that a[2] = a[1] * k1, a[3] = a[1] * k2, a[7] = a[1] * k3 ... k[i] is obviously from 0 to (n-1) / a[1]Now we can just ask another set of questions: ? 2 3 | ? 2 7 | ? 2 9If any of those gcd(a[2], a[j]) != a[1] then it means either a[2] or a[j] == 0.As always with guys of green profiles , my code is having WA2 lmao, here it is. Tell me if you can spot a mistake
•  » » 21 month(s) ago, # ^ |   0 1 2 4 3 0 Try this case
•  » » » 21 month(s) ago, # ^ |   0 Good one, thanks.
 » 21 month(s) ago, # |   0 Fast editorial (wtf about #837)
 » 21 month(s) ago, # |   0 Can anyone tell whats wrong with my Submission in D https://mirror.codeforces.com/contest/1762/submission/185370228 it would be great help
•  » » 21 month(s) ago, # ^ |   0 1 2 4 6 8 7 3 5 0 calculate number of queries for this case.
•  » » » 21 month(s) ago, # ^ |   0 15 brother with is less than 2*(9) where 9 is the size of array
•  » » » » 21 month(s) ago, # ^ |   0 Actually, in my case, it took 19 queries.  First I queried the first position with every other element, which took 8 queries. Then I updated the array to [2,4,6,8,7,3,5,0]. Then I queried the first element of the current array (which has value 2) with every other element. This took another 7 queries for me. So the total is 15 queries. I took the elements which gave maximum gcd. So updated array looks like [4,6,8,0]. Then following the same procedure I will query again another 3 times. So the total number of queries is 18. The resultant subarray is [8,0]. So I queried last time before giving an answer which totals up to 19. Maybe you can relate to your code. The idea is just to avoid position 1 when querying with other elements.
•  » » » » » 21 month(s) ago, # ^ |   0 ya i avoided the first position actually and moreover I got a wa actually but I checked for many a times but not able to found wa test case
•  » » » » » » 21 month(s) ago, # ^ |   +3 Take a look at Ticket 16571 from CF Stress for a counter example.
•  » » » » » » » 21 month(s) ago, # ^ |   0 thanks a lot got it
 » 21 month(s) ago, # |   0 Very beautiful problem F! I stand up and applause!
•  » » 21 month(s) ago, # ^ |   0 Thanks!I am glad that you liked it (:
 » 21 month(s) ago, # | ← Rev. 3 →   +24 I solved F with a different approach.I made a directed graph such that there is an edge from $i$ and $j$ if $A_i \geq A_j$ and all $A_k$ between $A_i$ and $A_j$ are less greater than $A_i$. Similarly, I add an edge between $A_i$ and $A_i$ such that $A_i \leq A_j$ and all $A_k$ between $A_i$ and $A_j$ are greater than $A_i$. So, there are atmost $2$ outgoing edges from each $i$. Now, $DP_i$ = $DP_j$ + $DP_k$ — $DP_l$ where there is a directed edge from $i$ to $j$ and $i$ to $k$. But to avoid double calculations, we need to subtract $DP_l$ where $l$ is the smallest position that can be reached by both $i$ and $j$ using some directed edges. Now, to find this position $l$, we use binary lifting technique with binary search. Since $l$ is the smallest position, you have $2$ nodes $u$ and $v$ such that $A_u \leq A_v$ and $A_u \leq A_l \leq A_v$. Hence it is always optimal for $A_u$ to take the edge such that $A_{p_u} \geq A_u$ and for $A_v$ to take $A_{p_v} \leq A_v$.Now, we can binary search and find the largest node which is less than or equal to mid and check if - they are same - $A_u > A_v$ - $A_u < A_v$ This maximum node can be found by binary lifting technique.Time complexity — $O(N log^2N)$ and works fine within $3$ seconds. My code
 » 21 month(s) ago, # |   0 What will be the expected rating of the 2nd question?
•  » » 21 month(s) ago, # ^ |   0 i think it would be around 1000
 » 21 month(s) ago, # |   0 Nice editorial , hints are available for every problem.
 » 21 month(s) ago, # |   0 Can someone explain C? Why suffix though?
•  » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 Example:s = 1_0_1_0_0_0f(s) = 8how? try to find what binary digits can occupy empty places.1st empty space : 02nd empty space : 13rd empty space : 0/14th empty space : 0/15th empty space : 0/1 So the longest suffix with the same digits in the original string only accounts for the number of ways to fill the binary digits in empty places.Also, try to work out for this case:s = 1_0_1_0_0_0_1You will observe that, because of the last one in the string, all the 2 possibilities (0 / 1) in previous empty places change to 1.
•  » » » 21 month(s) ago, # ^ |   0 Wow! Good Explanation. Thanks man
•  » » » 19 months ago, # ^ |   0 but why longest suffix and not any other idea
•  » » » » 19 months ago, # ^ |   0 try working out the examples , you will get an idea
 » 21 month(s) ago, # |   0 I am not getting Problem C solution can someone explain it.
 » 21 month(s) ago, # |   +10 Satyam_343 is legend!
•  » » 21 month(s) ago, # ^ |   +5 Certainly, least we can do is : satyam343 orz.
•  » » 21 month(s) ago, # ^ |   +5 Not not not $\ldots \ldots$ untrue
•  » » » 21 month(s) ago, # ^ |   0 I made the above meme
•  » » » » 21 month(s) ago, # ^ |   0 Not not not $\ldots \ldots$ untrue
 » 18 months ago, # | ← Rev. 2 →   0 for C, a little optimization: say that current suffix has length l. then in the summation we will be summing 2^(k-1) from k=1 to l, but this is just 2^(l)-1. thus we only need to sum (2^length)-1 over all consecutive strings of 1s and all consecutive strings of 0s. example: 101101111 1 — length 1; 0 — length 1; 11 — length 2; 0 — length 1; 1111 — length 4; summing 2^(length)-1 gives 1+1+3+1+15=21, as desired.
»
10 months ago, # |
Rev. 3   0

#### Explanation for the observation about suffixes for C

• forget about prefixes of s. Lets see how many good-extensions exist for a string $x$.
• For any extension (say) $x'$ of $x$ to be good, every odd-length-prefix of $x'$ must also be good.
• Any odd length prefix, will have the frequency of median character = $1/3/5/7/ \dots$ more than the frequency of the other charcter. I mean, frequency difference has to be odd. (because, again, odd-length-prefix and a binary string).
• Noticed that if the odd-length prefix $x'$ is "good" and the last character of the next odd-length prefix is the same as this "good" one, then there are $two$ options to fill that intervening position between them. (There's a single intervening position between two consecutive odd-lengthed-prefixes.)
• Most imp: one way of filling this intervening position will end up increasing the frequency-difference by 2 and the other way will not alter the frequency-difference at all.
• If the relative frequency gets altered, the absolute frequency of the median character will become atleast $3$ more than the other character's absolute frequency.
• Notice the situation once there is a absolute frequency difference of $3/5/7/\ldots$ and the next odd-lengthed prefix ends at an "unlike" character.
The "single-intervening-element" between the current and next odd-lengthed prefix will not be able to salvage the situation and cover-up a gap of $3/5/7..\dots$. It can only cover frequency gap of $1$.

Finally: This means you can use both two options of filling the intervening position only when you can trust that you don't have any upcoming odd-lengthed prefix that ends at an unlike character. In all other cases, there is actually only one way of filling up the intervening position.
Only when, you know that the entire suffix of $s$ from this point on contains "like" characters, can you start using the other "second" way of filling up the intervening position.

•  » » 3 months ago, # ^ |   0 can u explain why they are setting curr to 1, if the characters are not equal?
 » 5 weeks ago, # |   0 GOOOOD round!
 » 5 weeks ago, # |   0 cool