### AndreyPavlov's blog

By AndreyPavlov, history, 11 days ago, translation,

1780A - Hayato and School

Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: AndreyPavlov

Tutorial
Implementation (Python)
Implementation (C++)

1780B - GCD Partition

Idea: 74TrAkToR
Preparation: qualdoom
Editorialist: qualdoom

Tutorial
Implementation (Python)
Implementation (С++)

1780D - Bit Guessing Game

Idea: AndreyPavlov
Preparation: qualdoom, AndreyPavlov
Editorialist: qualdoom, AndreyPavlov

Tutorial
Implementation (Python)
Implementation (С++)

1780E - Josuke and Complete Graph

Idea: T4M0FEY
Preparation: T4M0FEY
Editorialist: T4M0FEY

Tutorial
Implementation (Python)
Implementation (С++)

1780F - Three Chairs

Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: qualdoom

Tutorial
Implementation (С++)

1780G - Delicious Dessert

Idea: T4M0FEY
Preparation: T4M0FEY, AndreyPavlov
Editorialist: T4M0FEY, AndreyPavlov

Tutorial
Implementation (t4m0fey)
Implementation (AndreyPavlov)

• +348

 » 11 days ago, # |   +46 Can't wait for the solution of C. Show us guys, how to solve NP-hard problems!
•  » » 11 days ago, # ^ |   +184 Hahahahahahahaha you're so funny hahahahhaha
•  » » 11 days ago, # ^ |   +13 Maybe it is P but not O(n^2).
•  » » 7 days ago, # ^ |   0 Prove P=NP to solve it
•  » » » 7 days ago, # ^ |   0 Not my duty, lol
 » 11 days ago, # |   +14 Has no one made a hack for C yet?
•  » » 11 days ago, # ^ |   +37 The tester code probably uses the same faulty algorithm so it would be to no avail.
•  » » 11 days ago, # ^ |   +57 The author's solution is wrong. Therefore, any hack would still get AC, even if the output is incorrect.
 » 11 days ago, # |   +80 Problem D was very interesting :) ,one mistake and whole efforts of problemsetters and testers got ruined.
•  » » 11 days ago, # ^ | ← Rev. 2 →   -14 I thought D was easier than B. Although I kinda over complicated B for no reason.
 » 11 days ago, # |   +11 Weren't the incorrect greedy solutions for C O(n)? Why was the constraint on the problem O(n^2) then?
•  » » 11 days ago, # ^ | ← Rev. 3 →   -46 .
•  » » 11 days ago, # ^ |   +10 I think it was to allow solutions that did not use priority_queue or something similar
 » 11 days ago, # |   +19 On the last row of Tutorial of B:"Let $s$ be the array $a$"should probably be"Let $s$ be the sum of the array $a$"
•  » » 11 days ago, # ^ |   +1 They probably used machine translation. The solution to E is impenetrable.
 » 11 days ago, # |   -21 Is it not possible to remove problem C for everyone?
•  » » 11 days ago, # ^ |   +19 It's a bad idea because some poor people like me spent ~30min trying to solve it and ~20min trying to understand why so many people solved such a hard problem xd
•  » » » 11 days ago, # ^ |   -60 The conditions were all the same and a good time was also announced. so in my opinion, it is fair to remove it
•  » » » » 11 days ago, # ^ |   +18 No
•  » » » » 11 days ago, # ^ |   +33 LOL. Some people solved C with incorrect solutions that they figured out within minutes and moved on. And those who realized that solution is incorrect will be punished. What kind of fairness is that?
 » 11 days ago, # |   +95 My solution failed system tests on C because it got a better result than the author's one, lol Spoiler
•  » » 11 days ago, # ^ |   0 Did you found any counter-test for your solution?
•  » » » 11 days ago, # ^ |   +9 Yeah Spoiler1 13 4 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 5 
•  » » 11 days ago, # ^ | ← Rev. 2 →   +9 They should have asked for the exact assignment instead of just the maximum value, so that they can check for a FAIL verdict correctly. (FYI, FAIL is the verdict when the submission found a better solution than the jury's) They might have found the issue before the contest if this was the case.
•  » » 11 days ago, # ^ |   0 lol
•  » » 11 days ago, # ^ |   0 how it should be 11 can u explain it bit more clearer...
•  » » » 11 days ago, # ^ |   0 There are 6 guests who likes the dish #1, and the remaining 5 likes the #2. So if we split the 6 guests in table #1 and #2, and the 5 who like #2 at table #3, all 11 guests will be happy.
•  » » 10 days ago, # ^ |   0 my code gives output 11 and it was accepted which was incorrect. can you please explain your logic or provide your code.
 » 11 days ago, # |   0 Problem G is quite similar to this problem. I had to modify my solution for the Educational round problem a bit to get AC on this round's G.
 » 11 days ago, # |   0 Problem B Video Editorial Link : https://youtu.be/EmMdN5P0BhI
 » 11 days ago, # |   0 Guys for E, will finding distinct gcd's for pairs of numbers in the range l,r work? If yes what's the optimal way to do it?
 » 11 days ago, # | ← Rev. 10 →   +22 A brief tutorial to problem E, for people like me who cannot follow the official one:Value $x$ will appear in one of the edges iff: $L \leq px < (p+1)x \leq R$, where $p=ceil(\frac{L}{x})$.Now we enumerate every value of $p$ and count the number of possible $x$ for each $p$.For $p=p_0$, the above inequality gives range of x: $\frac{L}{p_0} \leq x \leq \frac{R}{p_0+1}$.Note that there is a hidden constraint of $ceil(\frac{L}{x}) = p_0$. This translates to $\frac{L}{p_0} \leq x < \frac{L}{p_0-1}$.Combine the two ranges above, we get, for $p=p_0$, possible values of $x$ satisfies: $\frac{L}{p_0} \leq x \leq min(\frac{R}{p_0+1}, floor(\frac{L-1}{p_0-1}))$.And we use sqrt decomposition to solve this counting problem: For $p\leq sqrt(L)+1$, we compute the range of $x$. For $p > sqrt(L)+1$, we have $x \leq sqrt(L)$, so we can just iterate through all $x$ values.Complexity is $O(sqrt(L))$.
 » 11 days ago, # | ← Rev. 7 →   +3 In C question greedy solution fail on test case-111 31 1 1 1 1 1 2 2 2 2 25 4 2correct answer for above testcase = 11, but greedy solution gives answer = 10
 » 11 days ago, # |   0 Can anyone explain what was the intended solution for C, which turned out to be incorrect.
•  » » 11 days ago, # ^ |   +28 Group people by what they like, and while there are groups of people and tables left, try to put the largest group on the largest table. If they don't fit, just use as many as you can and subtract that amount before deleting the table. If they do fit, delete the group of people and the table. "Answer" is however many people this process gives a table. The original might've been slightly different, but this is the silly wrong solution I got AC with.
 » 11 days ago, # |   0 In Problem D, in 2nd Tutorial (by qualdoom), for the condition (pt.2) where "$cnt-cnt_{new}\not=1$", can someone kindly explain the part, how this below equation is formed?$m - k - 1 = cnt_{new} - cnt$
•  » » 8 days ago, # ^ | ← Rev. 3 →   +1 Consider the real number is 24 its binary representation is 11000, and you need to guess this number. also, you can't subtract a number greater than the real number so if we subtracted 1 from real number which was 24, we will have 23 which its binary representation is 10111 so the number of unit bits has been changed and become 4-unit bits instead of 2 how this happened? hence, we now have 23 which has 4-unit bits and previous has 2 so the LSB at index (4-2+1) 0-based we add 1<
 » 11 days ago, # |   0 Who can explain me, how to use mobius function in problem F?
•  » » 11 days ago, # ^ | ← Rev. 27 →   +9 When you want to get $f(d) = \#func(a, b)$ where $gcd(a, b) = d$. You can count $g(d) = \#func(a, b)$ where $d | a$ and $d | b$.Then $f(d) = \sum_{i=1}^n g(i * d) * \mu(i)$Where $\mu(x)$ is the mobius function.Then you need to count for each number $k$ from 1 to max $a_i$, the number of triplets $(a_i, a_j, a_k)$ with $k | min(a_i, a_j, a_k)$ and $k | max(a_i, a_j, a_k)$.
•  » » » 10 days ago, # ^ | ← Rev. 4 →   +4 Mobius, more like Morbius
•  » » » 9 days ago, # ^ |   0 Can you share some resources where I can study this?
•  » » » » 9 days ago, # ^ |   +3 these blogs are very useful:https://codeforces.com/blog/entry/54090https://codeforces.com/blog/entry/53925but I got the main idea from this pdf
 » 11 days ago, # |   0 took nearly an hour for B because I thought you had to split it into k equal parts lol
 » 11 days ago, # |   +12 I don't know why. I want to comfort the author. qnq
 » 11 days ago, # | ← Rev. 2 →   +18
 » 11 days ago, # | ← Rev. 4 →   +8 Can someone give a test case where this approach gives a wrong answer to C? Calculate how many meals of each type and how many tables of each size there are. Go through the meals, if there is a table with the same size as the count of that meal, then put those people to that table. Put remaining meal and table counts to two priority queues. While there are still some empty tables or not all people has a spot: take the top of meals and put them at the biggest empty table, if some people who like that meal are still left, check if there is empty table with that amount of spots, if there is put them there, otherwise put that number back to priority queue.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Ok, here's a counterexample: tables are 2 2 3 and people are 1 1 1 1 2 2 2. The second step goes as no-op, so you will take ones into the third table (which has 3 seats) and then twos are placed in the remaining first/second table, which is not a correct strategy since you could have placed ones into first and second table and then remaining twos into the third table.
 » 11 days ago, # | ← Rev. 5 →   +3 My approach for D (similar to the second tutorial solution, it seems, but it doesn't explicitly need flags and might be easier to understand for some):To determine whether the last bit is 0 or 1, we can simply subtract 1. If the last bit was a 1, then it becomes 0 and the $cnt$ decreases by exactly 1. Now that the last bit is already 0, we can check the second-to-last bit by subtracting 2. In general, if the last $k$ bits are set to 0 while the rest of the bits are unchanged from the original, we can test bit position $k$ (from the right) by subtracting $2^k$ and seeing if $cnt$ decreases by exactly 1.But what happens when the bit at the position we're testing (let's say position $k$) is actually a 0? In that case, $cnt$ either stays the same or increases, so we know that this position originally has a 0. However, this attempted subtraction of $2^k$ ruins our desired pattern, because the bit at position $k$ changed from 0 to 1 and at least one bit on its left has changed. We would have wanted the bits from up to position $k$ to all be 0 and everything else unchanged in order to test the next bit, at position $k + 1$...We can deal with this by "undoing" the latest undesirable subtraction by instead treating it as part of the next subtraction. Normally, the next subtraction is supposed to be $2^{k + 1}$, but since we already performed an undesirable subtraction of $2^k$, we simply subtract another $2^k$ to result in a overall subtraction of $2^{k + 1}$ as if the undesired subtraction never happened. Note that there could be a sequence of undesirable subtractions, in which case, we just keep track of the total of the undesirable subtractions and treat them all as part of the next subtraction. Eventually, we would have to find a 1, which resolves all these undesirable subtractions. Once we find the MSB, the $cnt$ should become 0, at which point, we are done. My submission: 190561881 ($acc$ is the accumulation of undesired subtractions that we are trying to undo)
•  » » 10 days ago, # ^ |   0 Thank you for the explanation!!
•  » » 10 days ago, # ^ |   0 I did this as well. 190592786
 » 11 days ago, # | ← Rev. 2 →   0 Simple implementation for F 190544353
•  » » 10 days ago, # ^ |   0 Can you explain your solution if it's different from the editorial?
•  » » » 10 days ago, # ^ |   0 I have similar solution. Mine is: calculate $dp[x]$ -- number of ways to choose a triple which value of gcd is $x$. To calculate amount of such triples for every $x$ sort an array then for every $x$ consider only numbers which are divisible by $x$, let their indices be $ind$, we should calculate sum over all $i < j$ of $ind_j - ind_i - 1$, we can calculate it by iterating over these indices storing sum of considered indices and their cnt. Then you have a $dp$ where you should substract from $dp[x]$ $dp[2 * x], dp[3 * x], ...$ to obtain correct answer.
 » 11 days ago, # |   0 What is the correct solution for problem C then, if it exists? In the editorial for problem E, it is mentioned that for g
•  » » 11 days ago, # ^ |   +5 Consider for gsqrt(L) respectively, for the first situation there's at most sqrt(L) values of g, so ceil(L/g) will have at most sqrt(L) values. For the second situation, we have 1<=ceil(L/g)
•  » » » 8 days ago, # ^ |   0 How to generate all values of ceil(L / i) where i belongs to [1, L] in O(sqrt(L))?
•  » » » » 8 days ago, # ^ |   0 First let i = 1 to ceil(sqrt(L))-1. For the remaining values, for m = L/ceil(sqrt(L)) to 1, calculate the range where ceil(L/i)=m.
 » 11 days ago, # |   0 Can anyone explain in first tutorial of problem D, how does the initial algorithm makes 60 requests at worst?
 » 11 days ago, # |   0 I did the same thing in problem B yet kept getting TLE. Can someone point out my mistake. Thankyou! while(test--) { int n; cin >> n; int * arr = new int[n]; int * cuml = new int[n]; //Cuml is for cumalative sum for (int i = 0; i < n; i++) { cin >> arr[i]; if(i==0) { cuml[i] = arr[i]; } else { cuml[i] = arr[i] + cuml[i-1]; } } int ans = 0; for(int i = 0; i < n-1; i++) { if(cuml[n-1]%cuml[i]==0) { ans = max(cuml[i],ans); } else { int temp = gcd(cuml[i],cuml[n-1]); ans = max(temp,ans); cerr << temp << '\n'; } } cout << ans << '\n'; } Please help !
•  » » 11 days ago, # ^ |   +6 cuml may not fit in 32bit integers
•  » » » 10 days ago, # ^ |   -13 Yes Sir but I did use long long once too...still it gave TLE...also overflow gives wrong answer not TLE though...
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 use long long, instead of long int. https://en.cppreference.com/w/cpp/language/types Long int's aren't always 64 bits-width, maybe that's a problem in your case.
•  » » 10 days ago, # ^ |   +1 On 32-bit compilers "long int" is same as "int", both of them are 32 bits. Use "long long" instead.
 » 11 days ago, # |   0 What is the time complexity in F and why is it quick? IMHO we have O(N * 2^(an average number of prime divisors)) so it doesn't seem like a quick solution.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 lets think like this. you know the number of divisors of a number n is O(log(n)). now you are only iterating on SOME of these divisors.
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 Let $preres_x$ be the number of ways of choosing the triplets where the $gcd(a_i,b_j)$ is a multiple of $x$ and $res_x$ be the number of ways of choosing the triplets where $gcd(a_i,b_i)$ is exactly $x$. You can calculate array $res$ from $preres$. If you know the values of $res_y$ for all $y$ (where $y$ is a multiple of $x$) and $preres_x$, then you can calculate the value of $res_x$ and finally, $res_1$ will be the answer. You can do this by iterating from $3*10^5$ to $1$.The time complexity is sum of harmonic sequence $\sum_{x = 1}^{N} \left \lfloor \frac{N}{x} \right \rfloor$ which is equal to $O(nlogn)$.
 » 11 days ago, # |   0 Of all the rounds this had to happen in a round full of Jojo's references
 » 10 days ago, # | ← Rev. 2 →   0 Can someone please tell me what was wrong with C? My approach to solving C was: Group all the guests having the same liking. Now assign the biggest group to the largest table. If some guests are still left, insert them in the priority queue and continue this way.How was C an NP hard problem?
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 I did exactly the same, and I'm quite curious about the issue with it too. (Hope that the editorial will come out soon).
•  » » 10 days ago, # ^ | ← Rev. 2 →   0
•  » » 7 days ago, # ^ |   0 Your approach is incorrect. Consider the following scenario: 6 people like dish 1, and 4 people like dish 2. Three tables, with capacities 3, 3, and 4 respectively. If you assign the biggest group to the largest table, then the 4-table serves dish 1 (all four like it), one of the 3-tables serves dish 2 (all three like it), and the other 3-table serves dish 1 (two out of three like it), with one unsatisfied guest. But if you instead had both 3-tables serve dish 1 while the 4-table serves dish 2, then everyone would be satisfied.
•  » » » 7 days ago, # ^ |   +3 ok Thanks for telling
 » 10 days ago, # |   -10 Why did you delete issue C?
 » 10 days ago, # |   -10 Even though C couldn't be solved with given constraints during the contest I think it's better to lower constraints to make it solvable, write a proper solution and post the updated solution in the editorial, instead of completely removing it from the contest and archive. The problem is not bad at all, tbh.
•  » » 7 days ago, # ^ |   0 It's NP-hard, which means it almost certainly cannot be solved in polynomial time. Constraints would require $n$ to be about $20$, or maybe even less! The brute-force solution would be incredibly dull. There may be heuristics to speed it up and allow a little higher constraints, but this is not suitable for CP.
•  » » » 7 days ago, # ^ |   0 Doesn't mean it can't be solved at all. Better to keep a modified version with extremely low constraints than to remove it completely.
 » 10 days ago, # |   0 Can anybody tell me "correct" solution of C? or at least some ideas
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 Normal greedy method would fail the pretest (before it was deleted of course). My idea was to apply the data structure priority_queue, and for each current type of dish with the maximum number of people, compare it with the current largest table. If there are people left, insert this into the queue and repeat the process until there are no more people or no more tables. The main part of my code was: priority_queue, less > q; sort(alls(c), cmp); for (int i = 0; i < maxn; i++) { if (cnt[i] != 0) { q.push(cnt[i]); } } int ans = 0; for (int i = 0; i < m; i++) { if (q.empty()) break; int t = q.top(); q.pop(); int cap = c[i]; ans += min(t, cap); if (t > cap) { q.push(t - cap); } } cout << ans << endl; `Where $c$ denotes the tables and $cnt$ is used for counting the number of people for each dish.
 » 10 days ago, # |   +1 I would surely become a specialist after this round (rank 16) but...... It's unrated! And problem G is kind of rigid that almost everyone who has learnt sam before can solve it.But anyway,the problems are excellent!
 » 10 days ago, # |   0 can someone explain what's wrong with problem C. Instead of posting correct solution why authors completely removed problem C
•  » » 10 days ago, # ^ |   0 There is no correct solution to that problem. It is a NP-hard problem which cannot be solved in polynomial time
 » 10 days ago, # |   0 D was quite confusing cuz I have never solve interactive problems lol. F was easier than normal :V.
 » 10 days ago, # |   0 I am getting TLE on test case 3 for problem D. Please help, sumbission:190734004
 » 9 days ago, # | ← Rev. 3 →   0 [del]
 » 9 days ago, # |   0 I don't understand the tutorial for problem G. Can anyone explain the idea of it?
 » 4 days ago, # |   0 Does any one know how to calculate the time complexity of G? More detailedly,the time complexity of find the number of x,which is a factor of n, that l<=x<=r? The solution implied that is almost nlog(n) in total , but I can't understand why.