### satyam343's blog

By satyam343, 6 months 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 - Разделяй и властвуй

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762B - Сделайте массив хорошим

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762C - Бинарные строки это весело

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762D - Запросы НОД

Idea:amurto Prepared by:errorgorn

Hint 1
Hint 2
Hint 3
Solution
Code

1762E - Сумма на дереве

Idea:satyam343 Improved by:TheScrasse

Hint 1
Hint 2
Hint 3
Solution
Code

1762F - Хорошие пары

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code

1762G - Неравные соседние элементы

Idea:satyam343

Hint 1
Hint 2
Hint 3
Solution
Code
• +240

 » 6 months ago, # | ← Rev. 2 →   +12 Great Round!! Indeed, problems were quite hard but doable, but overall a v.good experience!
 » 6 months 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://codeforces.com/contest/1762/submission/185393565
•  » » 6 months 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$?
•  » » » 6 months 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.
•  » » » » 6 months 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
•  » » » » » 5 months 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.
•  » » 6 months ago, # ^ |   +7 i did exact same apprroach but got WA on test 5 can u please help https://codeforces.com/contest/1762/submission/185370228
•  » » » 6 months ago, # ^ |   0 even my solution failed on exactly the same test case . if you are able to find the mistake please reply https://codeforces.com/contest/1762/submission/185422415
•  » » » 6 months 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.
•  » » » » 6 months ago, # ^ |   0 mine submissions takes 15 submission which is in range
•  » » 6 months 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
•  » » » 6 months 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 :(
•  » » 6 months ago, # ^ |   0 I also came up with this solution! But sadly i couldn't participate in the contest
 » 6 months ago, # | ← Rev. 4 →   0 Problem A can use __builtin_ctz(x) for even numbers or __builtin_ctz(x+1) for odd numbers. link: https://codeforces.com/contest/1762/submission/185402449
•  » » 6 months ago, # ^ |   0 can you explain it more?
•  » » » 6 months 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.
•  » » » » 6 months ago, # ^ |   0 Damn clever!
•  » » » » 6 months ago, # ^ |   0 Nice solution, thank you
 » 6 months 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!
•  » » 6 months ago, # ^ |   0 Can u explain to me B answer
•  » » » 6 months ago, # ^ |   0 did you understood the question or you facing difficulty in understanding the solution
•  » » » » 6 months ago, # ^ |   0 i didnt understand the solution
•  » » » » » 5 months ago, # ^ |   0 you can try different approach other than this. for eg you can store array elements with their original indexes in a vector and then then sort elements and then simply check if i'th element is divisible by (i-1)'th element, if no then add the remainder to make it divisible . then again sort this vector according to their indexes
 » 6 months ago, # |   +11 Intended solution for D is genious.
 » 6 months 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.
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 can someone explain problem c and why exactly we are using suffix here?thanks in advance:)
 » 6 months ago, # |   0 For problem B, the official code means to change from first digit to the last digit.Why does the third output of the example go from 2 to 5 then to 3 ?
•  » » 6 months ago, # ^ |   0 There are multiple solutions possible for the same query. What the author is trying to say is that it is not necessary to print the answer in sorted order.I also used an approach during contest which did not print answer in sorted order.My earlier approach: 185336818 //Pls go directly to solve() function My approach after editorial: 185413693
 » 6 months 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
•  » » 6 months ago, # ^ |   0 1 2 4 3 0 Try this case
•  » » » 6 months ago, # ^ |   0 Good one, thanks.
 » 6 months ago, # |   0 Fast editorial (wtf about #837)
 » 6 months ago, # |   0 Can anyone tell whats wrong with my Submission in D https://codeforces.com/contest/1762/submission/185370228 it would be great help
•  » » 6 months ago, # ^ |   0 1 2 4 6 8 7 3 5 0 calculate number of queries for this case.
•  » » » 6 months ago, # ^ |   0 15 brother with is less than 2*(9) where 9 is the size of array
•  » » » » 6 months 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.
•  » » » » » 6 months 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
•  » » » » » » 6 months ago, # ^ |   +3 Take a look at Ticket 16571 from CF Stress for a counter example.
•  » » » » » » » 6 months ago, # ^ |   0 thanks a lot got it
 » 6 months ago, # |   0 Video Editorial for problem B: Make Array Good
 » 6 months ago, # |   0 Very nice problems. Loved the B problem. I did with an entirely different approach, but when I saw the solution I was amazed. Keep it up to the authors and the supporters for this wonderful contest.
 » 6 months ago, # |   0 Very beautiful problem F! I stand up and applause!
•  » » 6 months ago, # ^ |   0 Thanks!I am glad that you liked it (:
 » 6 months ago, # |   0 I have started doubting myself after seeing the solutions, I know nothing.... :(
 » 6 months 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
 » 6 months ago, # |   0 can anyone pls explain DP approach of problem C
•  » » 6 months ago, # ^ |   0 I couldn't solve this problem using dp bcz in my idea there is 2d and every d is 1e5.And i don't think there is no approach using only 1d.
 » 6 months ago, # |   0 What will be the expected rating of the 2nd question?
•  » » 6 months ago, # ^ |   0 i think it would be around 1000
 » 6 months ago, # |   0 Nice editorial , hints are available for every problem.
 » 6 months ago, # |   0 Can someone explain C? Why suffix though?
•  » » 6 months 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.
•  » » » 5 months ago, # ^ |   0 Wow! Good Explanation. Thanks man
•  » » » 3 months ago, # ^ |   0 but why longest suffix and not any other idea
•  » » » » 3 months ago, # ^ |   0 try working out the examples , you will get an idea
 » 6 months ago, # |   0 Hello! Can anyone help me? How many problems do I need to practice per day so that I can improve my performance during the contest?
•  » » 6 months ago, # ^ |   0 The quality not the quantity .Hint 1 : Upsolve div 4 till the last problem or maybe the previous one.Hint 2 : Upsolve div 3 till E problem or maybe the previous one.Hint 3 and this is the most important one: always upsolve atleast c at div 2.This is for now till be Cyan.Always try to upsolve more one harder, do virtual contests and read the tutorials after getting AC or stuck for not short while. Actually this will improve your performance during contests .Best wishes.
•  » » » 6 months ago, # ^ |   0 Hi Nour-Aldeen Thank you for the suggestion! :)
•  » » » 6 months ago, # ^ |   0 Thankyou for that!!!
 » 6 months ago, # |   0 I am not getting Problem C solution can someone explain it.
•  » » 6 months ago, # ^ |   0 X is the number of 0s and Y is the number of 1s must be in our good strings with length n.[1] Like 001, for i = 3 we must have Y = 3 ones and X = 2 zeros.So there is X + Y index we can't change If you have 2 empty places then you can have 2^2 to fill them by 0, 1.General case : z empty places give you 2^z case.Now every good string which has length equal to 2n — 1 must have X zero and Y one. [1] i == 3 and good string len = 5 and X + Y = 5 so there is 2^(len — (X+Y)) good string.Another ex : i == 2 and s == "00" : now every good string (its len must be 2n — 1 so here 3) must have X = 2 zero and Y = 0 one, now we have one empty index to fill 0**_**0 .You can fill it with 0 or 1 --> 010 , 000. So the answer will be 2^empty indexes .
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 but why is it 2^len-1 of the longest prefix of the string . btw thanks
 » 6 months ago, # |   +10 Satyam_343 is legend!
•  » » 6 months ago, # ^ |   +5 Certainly, least we can do is : satyam343 orz.
•  » » 6 months ago, # ^ |   +5 Not not not $\ldots \ldots$ untrue
•  » » » 6 months ago, # ^ |   0 I made the above meme
•  » » » » 6 months ago, # ^ |   0 Not not not $\ldots \ldots$ untrue
 » 5 months ago, # |   0 in 1762 B if we equalise all the elements then it can also be the answer but why i am getting error?
•  » » 3 months ago, # ^ |   0 @api.request if u try to equalize all element then at some point you will exceed at most n number of operation constrain.consider n = 4 , smallest_num = 3 and largest_num = 1000 then you will need 3 + 6 + 9 + .... which is more then 'n' so you r getting errorHope this helps!!
 » 3 months ago, # | ← Rev. 2 →   0 For who didn't understood proof for problem C if string is s = 1010111 sz = 7 sexy = 1_0_1_0_1_1_1 sz = 13 (good string btw i could think of good name for it) till idx 9(of string sexy)everything is forced to fill only one element why? because the elements before and after are fixed by different elements i.e — for idx 1 majority is 1 for idx 3 majority SHOULD BE 0 cause idx 3 is 0 so string till 3 will be 100 for idx 5 majority should be 1 so idx is forced to be 1 cause it will make 1's more than 0's so string till 5 will be 10011 this will go till idx 9. also NOTE |odd — odd = even| and we are checking for odd idx so after 9 there will be even no idx left i.e form idx 10-13 string till idx 9 will look like 100110011_1_1 here @ idx 10 it doesn't matter what you put since the 11 idx will cancel it out and you dont have to worry about next odd idx i.e 13 which is same as 11 so it doesn't matter what you put at 12 also since 13 will cancel it out. so for idx 10,12 has 2 choices and out ans is 2^len-1 where len is longest suffix of the string and len-1 because the first idx of the long suffix — 1 is forced and then we are left with one less option and hence thats the reason we did len-1 because we can fill all idx however we want after first idx of longest suffix
 » 3 months ago, # |   0 Can someone please explain why my this solution is incorrect?? Question B I have basically tried to increase every largest number such that it becomes divisible by smallest number
 » 3 months ago, # |   0 In B why can't we do like this : add the absolute difference of each element from the maximum element to each element. This approach gives wrong solution on test case 1 ???
 » 3 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.
 » 2 months ago, # |   0 Problem B solution is so nice!