Codeforces and Polygon may be unavailable between Aug. 17, 19:00 (UTC) to Aug. 17, 22:00 (UTC) due to planned power outages. ×

### huangzirui's blog

By huangzirui, history, 2 months ago,

1688A - Cirno's Perfect Bitmasks Classroom

Idea: huangzirui. Solution: huangzirui. Preparation: huangzirui.

Good problem
Average problem
Did not solve

Hint
Solution
Code (C++)
Code (Python)
Apology

1688B - Patchouli's Magical Talisman

Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: SSerxhs.

Good problem
Average problem
Did not solve

Hint1
Hint2
Solution
Code (C++)
Spoiler

1688C - Manipulating History

Idea: Yakumo_Ran. Solution: Yakumo_Ran, SSerxhs. Preparation: SSerxhs.

Good problem
Average problem
Did not solve

Hint1
Hint2
Hint3
Hint4
Hint5
Solution
Code (C++)
Code (Python)

1687A - The Enchanted Forest

Idea: Yakumo_Ran, SSerxhs. Solution: Yakumo_Ran. Preparation: SSerxhs.

Good problem
Average problem
Did not solve

Hint1
Hint2
Hint3
Solution
Code (C++)
Code (Python)

1687B - Railway System

Idea: Yakumo_Ran. Solution: Yakumo_Ran, huangzirui. Preparation: SSerxhs.

Good problem
Average problem
Did not solve

Hint1
Hint2
Hint3
Solution
Code (C++)
Code (Python)

1687C - Sanae and Giant Robot

Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: huangzirui, SSerxhs.

Good problem
Average problem
Did not solve

Hint1
Hint2
Solution
Code (C++)
Spoiler

1687D - Cute number

Idea: Yakumo_Ran. Solution: huangzirui. Preparation: SSerxhs, huangzirui.

Good problem
Average problem
Did not solve

Hint1
Hint2
Solution
Code (C++)

1687E - Become Big For Me

Idea: xiaoziyao. Solution: xiaoziyao, SSerxhs. Preparation: SSerxhs, xiaoziyao.

Good problem
Average problem
Did not solve

Hint
Solution
Code (C++)
Spoiler

1687F - Koishi's Unconscious Permutation

Idea: huangzirui. Solution: Elegia. Preparation: huangzirui, SSerxhs.

Good problem
Average problem
Did not solve

Hint
Solution
Code (C++)

• +276

 » 2 months ago, # |   -25 div2 C, terrible!
•  » » 2 months ago, # ^ |   +7 I don't even feel like upsolving it lol
•  » » 2 months ago, # ^ |   +3 Yes, their solution of C problem in Python is not accept by PyPy3 and PyPy2, but it said that generally it is faster. I have lose many attempts searching in my solution, but it is was correct. But then it was just accepted when I send it by Python2 or Python3 Admins, Please, reconsider solutions, because I solved this problem faster, then it was finally accepted
•  » » 2 months ago, # ^ |   +3 In Div.2: Why was the round unbalanced(D had more AC, then C) ? What was the point of making C so hard ?
•  » » » 2 months ago, # ^ |   +7 Because testers with different rating solve C easily, spending less time than D.We don't mean to make C hard, it's a fault. On the contrary, we add C to fill the gap between B and D (at first, D was C).
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +1 The idea to solve C was so random and guessing, I thought there is a way to construct it by some advance algorithm =((
 » 2 months ago, # |   +17 Thanks for the fast editorial, though there had been nightmares in 2C.
 » 2 months ago, # |   0 Weak pretests in Div2A, seriously ?
 » 2 months ago, # |   0 Can anyone please explain Div 2 B less mathematically? I am having hard time understanding the solution.
•  » » 2 months ago, # ^ |   +6 If you have at least one odd number, you can sum this number with all the evens because even + odd = odd, so in this case ans = amount of even numbers. Otherwise, the optimal strategy is to divide a number until it becomes odd, and then do the strategy for the first case, you can do it iterating over all the numbers and looking for the number that requires less movements to became odd by dividing it by 2.
•  » » » 2 months ago, # ^ |   0 How does this work in this case: n = 2 a = (1024, 2048) Both are even numbers, the correct solution here should be 1: operation 1 yielding 3072 2: operation 2, 5 times solution: 6 if we follow the strategy of searching for the number that requires the least division by 2 to make it odd, then we try to divide 1024 10 times to make it odd, so the solution becomes 11
•  » » » » 2 months ago, # ^ |   0 If you divide 3072 by 2 five times then you end up with 96 which is not odd.
•  » » 2 months ago, # ^ |   0 The optimal solution is to use fusion between an odd and even number as often as possible (this will always get rid of 1 even number per operation whereas reduction can leave you with even number. It's impossible to get rid of more than one even number per operation). The problem is if you don't have any odd numbers to start with, in which case you need to calculate which number can be made odd quickest using reduction and then use that odd number with fusion to get rid of all the remaining evens.
•  » » 2 months ago, # ^ |   0 If there is at-least one odd number in the array, then you can use this number with operation 1 to make all the even number numbers odd (odd + even = odd). The total number of operations would be the number of even numbers. If no odd numbers present, then find the even number that takes minimum number of operations (operation 2 divide by 2) to make it odd, then do step 1.
•  » » » 2 months ago, # ^ |   0 Damn.. How did I missed that!!! Thank you for the nice explanation.
 » 2 months ago, # |   +2 Please Explain D in more detail if anyone can ??. I am not getting for k>=n part ??
•  » » 2 months ago, # ^ |   +30 the optimal strategy is to wait until we have greater than n seconds left and let the mushrooms grow as much as they can. finally when we have n seconds left, we traverse over the array and collect all the mushrooms.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +6 Omg !! Yeah i didn't saw |x-y| <= 1. So just wait for n-k seconds . Then loop through array for n times giving as k*n . and rest part is n*(n-1)/2. so answer will be = sumofarray + (k-n)*n + (n*(n-1)/2). Wrote the same formula and got accepted . Thanks a lot buddy !!
•  » » 2 months ago, # ^ | ← Rev. 4 →   +12 Let me explain how I proved it, The main observation is, if a point is visited at times (t1, t2, t3...tp) Then, the "extra" mushroom gained from this point is tp-1. Why? Because, first I gain t1-1 mushrooms, then t2-t1 mushrooms, then t3-t2 mushrooms and so on. So extra mushrooms gained by point simply equals to last time I visited it minus 1.Lets say, that I visit exactly r points and I have k seconds (I may visit some points multiple times), how to maximize the number of "extra" mushrooms gained given, for a fixed r? Observe that if I have k seconds, than extra mushrooms gained will be sum of r different numbers from [0 , k-1] (Every number denotes extra mushrooms gained from some point. No number will be repeated in sum, because every point's last visited times MUST be different.). An upper bound is sum of last r numbers, i.e [(k-r) + (k-r+1)...+ (k-1)]. This is also possible too! Start from 0th second, keep waiting and collecting mushroom from the first point till, (k-r+1)th second, So that I can get k-r extra mushrooms from it, then jump to remaining r-1 points, giving me (k-r+1) + (k-r+2)...+ (k-1) extra mushrooms!Now, for a fixed r we know the strategy. Observe that increasing r is always profitable. (Its really easy to prove, just compare the total mushroom gained using optimal strategy for r and r+1). So we should try to keep r as large as possible.
•  » » » 2 months ago, # ^ |   0 Yeah. Thanks bro !!
•  » » 2 months ago, # ^ |   +1 Video Solution for Div2D
•  » » 2 months ago, # ^ |   0 You can use binary search as well, i binary searched on the number of mushrooms that can be collected in k minutes, and I just found the maximum such number You have to handle two cases separately, i.e. when number of k <= n and k > n in the former case just find the maximum sum subarray and then add the extra ballons that may have appeared in k seconds. In the latter case you have to make more than one traversals of array (in concept) to collect the mushrooms , its a little maths you can use pen and paper to understand it .Here is my solution:
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Your binary-search is not needed, in fact instead of returning boolean value in your function f, u can directly return the value you calculated, that is the final answer. here is your code I modifiedint f(vectorvec, int k){ int n = vec.size(); if(k> n >> k; vectorv(n); for(auto&x: v)cin >> x; int ans=f(v,k); cout << ans <
 » 2 months ago, # |   +50 Beware of Luogu's problem group invading Codeforces.
•  » » 2 months ago, # ^ |   +9 It should be "Beware of TouhouProject's problem group invading Codeforces."
•  » » 2 months ago, # ^ |   0 Can anybody explain why we should do that? I'm just curious about it.
•  » » » 2 months ago, # ^ |   +13 Because this competition is prepared by one of luogu's (a Chinese cp website) team of problem setters (called WdOI). Of course this comment is just joking, please don't take it seriously.(however for myself Chinese rounds are too terrible I always get negative rating changes :(
 » 2 months ago, # |   +21 C, if some letter is in the intial string, it will appear in the input data exactly once. Why?
•  » » 2 months ago, # ^ |   +1 I made some insights elsewhere: " I guess the answer at the game.Let's consider both operations and results as strings.Consider the character 'x' at the beginning, if there is only one operation, that is, change the 'x' into 'yyy', then the input data is the 'x' 'yyy' of the operation and the 'yyy' of the result. If we go to the operation again, for example, the next operation is 'yy'-'zzz', then each operation is to delete 'yy' from the result string and join in the operations, and then replaces 'zzz', in the result string and adds' zzz' to the operation string. It is found that the 'zzz'' has increased twice, while the location of the 'yy' has only changed, but the number has not changed. That is to say, the parity of their occurrence remains the same. Therefore, only the initial letters appear odd times, and the others appear even times. " So I think the editorial of the problem only says 'appears exactly once' ,means 'x' that I said above appears only once. If there is an operation 'yy'-'zzz',' that contains'x'or equals to'x', we don't regard it as 'x' appear again. The description may not be accurate, but I think my solution should be correct.
 » 2 months ago, # |   -6 those quotes at the starting of question was quite helpful for solving problems ...LOL!
•  » » 2 months ago, # ^ |   0 how?
•  » » » 2 months ago, # ^ |   0 well for that first you have to solve the problem without reading it & then see if it make sense to read the quote first & then solve the problem ;)
 » 2 months ago, # |   +45 I think I cheesed problem D.A "brute force" solution is to iterate over the array, and increase the offset to whatever it has to be to make the current element cute, and repeat until the offset didn't change.This was as I expected too slow, but then I tried shuffling the input list. That was still to slow. Then I tried on-line shuffling the prefix of the array that is looked at until finding something not cute, and breaking when its found. My intuition for doing this is that this way problematic elements probably end up in the start of the array, so they're found faster.
•  » » 2 months ago, # ^ |   +8 Online shuffle is a nice trick here!
 » 2 months ago, # |   +1 Can anybody please tell me what's wrong with my div2D submission? Cf-stress was not able to find anything wrong...
•  » » 2 months ago, # ^ |   0 when k>n, the ans = sum(n)+k*n-(n+1)*n/2. in your code,this part is wrong.
•  » » » 2 months ago, # ^ |   0 This part is correct actually...
•  » » » » 2 months ago, # ^ |   0 sry,i made a mistake...my math is terrible
•  » » 2 months ago, # ^ |   0 and when k
•  » » » 2 months ago, # ^ |   0 Nvm, my stupid ass thought that the positions are cyclically arranged.
•  » » 2 months ago, # ^ |   0 FWIW, here's a tip on how to navigate CF Stress when you don't find a counter example in your first try. The solution is only tested for 60 seconds, so it means that the a counter example on that constraints might've been found if the duration was more.A workaround for this is to set $t\_low = t\_high = \infty$ on the same constraints. If you get "Data too large verdict", it means that you'd be able to get the counter example if you reduced the $t$ parameter. So then, just use $t\_low = t\_high = 10$ or $100$For example, your code fails on Ticket 10310
 » 2 months ago, # | ← Rev. 2 →   +2 I have stopped reading novels & stories since Codeforces has many stories to tell in every question !
 » 2 months ago, # |   +2 div 2 c a nightmare
•  » » 2 months ago, # ^ |   0 Yes, their solution in Python is not accepted by PyPy3 and PyPy2, but it said that generally it is faster. I have lose many attempts searching in my solution, but it is was correct. But then it was just accepted when I send it by Python2 or Python3
•  » » » 2 months ago, # ^ |   0 strings operations are always slow in py so try to submit string related question in python ...
•  » » » » 2 months ago, # ^ |   0 thanks
 » 2 months ago, # |   +53 When I saw Elegia in the writer's list, I immediately knew that Div.1 F won't be solvable.
 » 2 months ago, # |   +31 Harder div1D: You are given $100\,000$ values of $k$; for each one say whether $a_i+k$ is beautiful for all $1\le i\le n$.
•  » » 2 months ago, # ^ |   0 I also reduce problem D to this problem, but then I cannot solve this. How could you solve the problem by this approach?
•  » » » 2 months ago, # ^ |   +5 Solution of the harder div1DGiven $p\ge 0$, $a>0$, $b>0$; let $S(p, x, y) = [p, p+x-1]\cup S(p+x+y, x+1, y+1)$ (and infinite union of disjoint intervals).A subset of the nonnegative integers is nice if it is the union of $k$ disjoint intervals and $S(p, x, y)$ for some $p, x, y$. Nice subsets have the following properties: The intersection of two nice subsets is nice. The translation of a nice set is nice. The set of beautiful integers is nice. We want to compute the set of $k$ such that $a_i+k$ is beautiful for all $i$. Such set is nice thanks to the observation above. What is less clear is that such set has only $O(a_n-a_1)$ disjoint intervals and then $S(p, x, y)$ for some $p, x, y$. Once one is convinced of this, it is easy to conclude with a divide and conquer technique (we compute the answe for $[1, n/2]$ and $[n/2+1, n]$ and then we deduce the answer for $[1,n]$ intersecting).After having computed the set of $k$ such that $a_i+k$ is beautiful for all $i$, answering the queries is straight-forward in $O(\log(a_n-a_1))$.Implementing the intersection of two nice sets is not particularly nice...
•  » » 2 months ago, # ^ |   +16 How is it harder? Just like in the regular solution, enumerate floor of sqrt of $a_1 + k$ and do the jumps, you will find the interval of possible $k$. For $k > a_n^2$ all the numbers should be in one segment, so you can check one such $k$ in $O(1)$. I believe that my submit 159385709 from the contest will solve this harder version if remove return 0, change IO and add this special case for big $k$.
•  » » » 2 months ago, # ^ |   +8 For your solution (and possibly for the official solution ?) they might be the same problem, but the majority of accepted solutions are not good enough to solve the harder version.
 » 2 months ago, # | ← Rev. 3 →   +10 I had an alternate solution for problem D that is hard to analyze but runs quite fast on the given tests (maybe hackable?). The basic idea is to combine the naive approach of repeatedly finding a lower bound for $k$ with grouping elements of the array. The grouping will compress numbers together if we can be certain that $f(x+k)=f(y+k)$ in the final answer. This is helpful because e.g. if we can group together elements that are $10^6$ apart, we can skip to a value of $k$ that will make $f(x+k)\geq 10^6$.
 » 2 months ago, # | ← Rev. 2 →   +18 Div1D: Please hack me, this is a simple randomization (with some optimize)159418821 upd: hacked, thanks
 » 2 months ago, # |   +3 this is how i did Div2D — Case 1 : k<=n we take max sum contiguous subarray of length of size k and then add k*(k+1)/2 to it . Case 2 : k>n at first i thought of taking from left to right then right to left then left to right so on till k becomes 0 but it was not able to maximize the answer , so i took 0th element n-k+1 times (till then other n-1 mushrooms grow and this leads to optimal answer) , then take all elements from index 1 to n single time and add initial height and the extra height it grew when u were picking the mushrooms before it here is my submission — https://codeforces.com/contest/1688/submission/159403438
 » 2 months ago, # |   0 "Worth mentioning, with this conclusion (such small set exists), we can solve it much more easier. Just choose a small set by greedy, and enumerate its subset of size 14.":o
 » 2 months ago, # | ← Rev. 2 →   0 Your solution of C problem in Python is not accept by PyPy3 and PyPy2, but it said that generally it is faster. I have lose many attempts searching in my solution, but it is was correct. But then it was just accepted when I send it by Python2 or Python3 Please, reconsider solutions, because I solved this problem faster, then it was finally accepted
 » 2 months ago, # |   0 A, B and D are nice. C not much. Nice contest though
 » 2 months ago, # |   0 Hey, Please tell why my submission on A failed? My submissionIt says "wrong output format Expected integer, but "2.68435e+008" found" on test 2
•  » » 2 months ago, # ^ |   0 Try (long long) before pow
•  » » 2 months ago, # ^ |   0 "Raw" pow function returns a float or a double value. You have to convert it or write a power function for integers only.
•  » » » 2 months ago, # ^ |   0 @TWNWAKing, @quochung-cyou Thank you so much, though it got accepted, I am not able to understand why the conversion was needed, as he inputs are in int range.. or could you please tell any specific test case where it was failing?
•  » » » » 2 months ago, # ^ |   0 It's just that pow function returns double type, and c++ outputs doubles like this for example 1.531e3, which is not acceptable, so you have to convert it into int or long long so that it outputs in integer form
 » 2 months ago, # |   +9 Div 2 problem C — the statement was very confusing and hard to understand!
 » 2 months ago, # |   0 why it's not possible to hack Div2C?
•  » » 2 months ago, # ^ |   +12 Probably because it's difficult to check whether the input is valid or not.
 » 2 months ago, # |   +3 Can A high rated person give their view on problems like Div 2C and how to get better at them, these always seem to appear in Div 1 + Div 2 rounds where we need to make a claim based on observations and hope that its correct. I think all of us could benefit from it.
•  » » 2 months ago, # ^ |   0 yes.I struggle in such kind of problems.
 » 2 months ago, # |   +1 God I absolutely hate div2C kind of problem where you're just trying to find this tiny obscure property that doesn't even look too relevant but turns out to be literally the whole answer
•  » » 2 months ago, # ^ |   0 I think that is OK, but the real problem that solution of C problem is not accept by PyPy3 and PyPy2, but accepted when I send it by Python2 or Python3
 » 2 months ago, # |   +6 Question C is not correctly explained that things ruined the whole contest
»
2 months ago, # |
+80

Solution: Elegia.

Spoiler
 » 2 months ago, # |   -8 Div 2 C. It got TLE in python 3. But when same code is submitted in pypy3 ,it is accepted. Why does this happen?please look into it and re evaluate it.
•  » » 2 months ago, # ^ |   0 Codeforces always says that if you submit it in pypy, it almost always works faster
 » 2 months ago, # |   -13 I hate yakumo ran
 » 2 months ago, # |   +26 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.Divison 2 Divison 1 If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
•  » » 2 months ago, # ^ |   0 Hey, stop it. Get some help.
 » 2 months ago, # |   0 I have a question and I will be thankful if someone helped out It is about Div 2 C The question says the answer is unique but I found this sequence for the second test case and it seems right but I do not see where I went wrong so can anyone point it out to me?initial is "a" pick substring "a" and replace it with "z" so now it is "z". pick substring "z" and replace it with "aa" so now it is "aa". pick the first substring "a" and replace it with "yakumo" so now it is "yakumoa" pick the last substring "a" and replace it with "ran" so now it is "yakumoran"and then t before shuffled become: t = ["a" , "z" , "aa" , "yakumo" , "a" , "ran"] so can anyone point out where I went wrong and explain the question more for me? Thanks in advance
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 This is not possible. Imagine that the initial string was "a" as you told. and t = ["a" , "z" , "aa" , "yakumo" , "a" , "ran"]. operation 1: s = "a". choose a substring of s that equals to t[1] which is "a" and change it to t[2] which is "z". operation 2: s = "z". choose a substring of s that equals to t[3] which is "aa" and change it to t[4]. but we don't have any substring "aa" in "z".
•  » » » 2 months ago, # ^ |   0 Oh now i get itThanksa lot
 » 2 months ago, # |   +2 Div2 C, Hint2, Why the initial string consists of only one letter?Well, it's obvious, as the authors wrote in the statement: The history of Gensokyo is a string s of length 1 initially.Anyway, Div2 C and D should've been swapped.
•  » » 2 months ago, # ^ |   +1 I remember our math prof sometimes saying: "Hint: Look at the definitions"
 » 2 months ago, # |   +10 I have thought about problem D for 1 hour and I have also implemented a solution different from the official one. Nonetheless, I cannot understand anything from the editorial. Can someone give a vague idea of what is the official solution?
•  » » 2 months ago, # ^ |   +21 This may be slightly different, I also cannot fully parse the editorial but I think it's similar.Good numbers look like this, starting from 1:1 good, 0 bad, 2 good, 1 bad, ..., x good, x - 1 bad, ...Let's fix that after shifting, a[1] will be in the good range of size x. It gives us a range [lo, hi] (the numbers which puts a[1] at the beginning and end of the good range of size x respectively) of candidates.Consider all elements a[1] ... a[n] are shifted to a[1] + lo, ..., a[n] + lo at first. You can see that only the next ~a[n] / (x - 1) ranges can have any numbers in them (since the range sizes are all at least x - 1.For each good relevant range, you need the largest element in this range (this upper bounds hi).For each bad relevant range, you need the smallest element in this range (this lower bounds lo).If lo <= hi after looking at all ranges you have a valid answer. Smallest / largest in any range can be found be precomputing + shifting.Since there are a[n] / (x - 1) relevant ranges for each x, the total cost becomes ~a[n] log(a[n]). (Once you hit the good range of size a[n] you're guaranteed to find an answer).
 » 2 months ago, # |   +26 Yet another randomized approach for Div1D, which I tweaked to being accepted after the contest. It is similar to some approaches already mentioned, but still feels different enough for me to write it up. First, the base solution.The cuteness means that every number has to be from $u^2$ to $u^2 + u$ for some integer $u$. And some $u$ on the order of a few million would make each number cute, so, there are not too much $u$ to check.Thus we iterate over $u$ for the first given number, $a_1$. Inside, we have the answer between two borders, $x$ and $y$, where $x = u^2 - a_1$ and $y = u^2 + u - a_1$.Check all other numbers $a_i$: if $a_i + x$ is between some $v^2$ and $v^2 + v$, the upper bound $y$ should be lowered so that $a_i + y = v^2 + v$; if $a_i + x$ is larger than $v^2 + v$, the lower bound $x$ should be upped so that $a_i + x = (v + 1)^2$; as soon as $x > y$, the whole check fails. Note that, on step 2, we can not possibly go to $(v + 2)^2$ or more, because the initial bounds are for the lowest of our numbers $a_1$.If all the checks pass, we have the lower bound $x$ as our answer. Now, the base solution is slow.But if we shuffle $a_2, \ldots, a_n$ randomly, the intuition is that, when there are $p$ problematic values and they are distributed randomly, we break after $n / p$ steps. And if we had, for example, $n, n - 1, \ldots, 3, 2, 1$ problems in our checks, the sum would be just $n \log n$.This is still slow, for example, when we have many small numbers and one or two large — which are not lucky enough to appear at the front of our shuffled array, but still break most of the checks rather late.A neat solution to this seems to be the following: as soon as $a_i$ broke the check, shuffle it into a random position of $a_2, \ldots, a_i$. This way, the values which are usually problematic tend to go to the front of the array. Much like in a splay tree, useful checks gather at the front. This is still far from a formal proof.
 » 2 months ago, # |   +4 Why didn't I get a rating change after the contest? It shows no ranking in the contests page in my profile. (don't know why but it is listed in unrated contests)
•  » » 2 months ago, # ^ |   0 Something is wrong with the system. I have become pupil and it still shows my name in gray, and in the contests place in profile it says I becamr Newbie
 » 2 months ago, # |   +3 Div. 2 Problem C is really difficult for me to understand. The editorial does not make much sense to me. If someone could explain in better terms it would be much appreciated. I am trying to upsolve it.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I guess the answer at the contest.Let's consider both operations and results as strings.Consider the character 'x' at the beginning, if there is only one operation, that is, change the 'x' into 'yyy', then the input data is the 'x' 'yyy' of the operation and the 'yyy' of the result. If we go to the operation again, for example, the next operation is 'yy'-'zzz', then each operation is to delete 'yy' from the result string and join in the operations, and then replaces 'zzz', in the result string and adds' zzz' to the operation string. It is found that the 'zzz'' has increased twice, while the location of the 'yy' has only changed, but the number has not changed. That is to say, the parity of their occurrence remains the same. Therefore, only the initial letters appear odd times, and the others appear even times.
•  » » » 2 months ago, # ^ |   0 I think I understand it better, thank you so much. A very strange problem indeed.
 » 2 months ago, # |   +49 So, how Elegia's mind works?
 » 2 months ago, # | ← Rev. 2 →   0 in problem B(https://codeforces.com/contest/1688/problem/B) if there are only even numbers in the array why we are not using Fusion(Fusion: Patchouli chooses two tokens, removes them, and creates a new token with magical power equal to the sum of the two chosen tokens.)operation?ex:array[]={26,30,24,50}26+30=56,now array[]={56,24,50}56+24=80,now array[]={80,50}80+50=130,now array={130}applying reduction operation array={65} here also minimum operations=4
•  » » 2 months ago, # ^ |   0 Just like the last case in the sample, it's a special case, but that doesn't mean the best choice is to use Fusion operation. You can find that, if $A = 2^i \times a, B = 2^j \times b$ and $a, b$ is odd, if we add first and then try to devide the sum by $2$, we need at least $\min(i, j) + 1$ operations. But if we make one of them become odd first, then we need exactly $\min(i, j) + 1$ operations. When $n$ becomes larger, the total number of operations required by the second method above seems stable while the first don't.
•  » » » 2 months ago, # ^ |   0 can you please take a example and explain?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 For example, $A = 4, B = 12$, if we use Fusion first then we need to perform $5$ operations, while if we first turn $A$ into $1$, we only need $3$ operations in total.The question is to consider $\texttt{lowbit}(A)$ and $\texttt{lowbit}(B)$, if they are the same, so $A + B$ will have more zeros in the binary representation's end than both $A$ and $B$, so we need to perform more operations to devide them by $2$ until the sum becomes odd.
•  » » » 2 months ago, # ^ |   0 Thankyou,i understood now.
 » 2 months ago, # |   +9 Very weak sample in 1C, as a consequence I had been debugging a fake algorithm for an hour.
 » 2 months ago, # |   0 Does anyone know any error while using map. I wrote a code and it gave me wrong answer and then I edited it to map, It worked and when I switched back to map I was getting correct again. It has happened with me earlier too.
 » 2 months ago, # |   0 please explain 2A in a bit detailed and a simplified way.
•  » » 2 months ago, # ^ |   0 If $x = 2^k$, then the binary representation of $x$ only contains one $1$. To make sure $x \texttt{ and } y \neq 0$, then at that bit $y$ contains $1$ must hold. The same, to make sure $x \texttt{ xor } y \neq 0$, in order to make $y$ smallest, you will se we can just replace one $0$ with $1$ on any other bit of $y$. So this bit must on the leftest un-zero bit. So, if $y = 1$ then $y \leftarrow y + 2$, or else $y \leftarrow y + 1$.If $x \neq 2^k$, then just make $y = \texttt{lowbit}(x)$.
•  » » » 2 months ago, # ^ |   0 got it about about x = 2^k but the please explain the lowbit function logic... how that gives the right answer
•  » » » » 2 months ago, # ^ |   0
 » 2 months ago, # |   0 1688C = https://codeforces.com/contest/1634/problem/B all over again
 » 2 months ago, # | ← Rev. 5 →   0 It's difficult for me.
 » 2 months ago, # | ← Rev. 2 →   +18 I solved E with a simple greedy. Can anyone hack me or prove it?Our goal is to choose a subset that does not change the answer.Let $g$ be the final answer. For each prime factor $p$ of $g$, it suffices to choose two elements $x,y$ that $f_p(x),f_p(y)$ are the smallest and second smallest. (definition of $f_p$ is same as editorial)Now we have a set $S$, but the gcd of pairwise products in $S$ still might not be $g$. Let the reduntant prime factors of $g$ be $[p_i]$. For each $p\in [p_i]$, we need to choose two more elements $x,y$ that $f_p(x),f_p(y)$ are $0$.This directly passes. However I can't prove that it will never take more than $14$ elements. https://codeforces.com/contest/1687/submission/159458664upd: hacked
•  » » 2 months ago, # ^ |   +1 I can not prove it either, but it seems correct.Actually there are many strange but correct ways to select the subset. The method in editorial is not the easiest one, but it is easier to prove its correctness.
 » 2 months ago, # |   +55 Even though many people may not agree with me I think div2 C is one of the best problems I have ever seen. Congrats to the author of it Yakumo_Ran!
 » 2 months ago, # | ← Rev. 2 →   +43 //这回只花了45min就打完了。 （in the code of Div.2 B）
•  » » 2 months ago, # ^ |   +8 To salute Feng Jing Olympic of Imagination.
 » 2 months ago, # |   +3 can someone explain me Div2E problem statement
•  » » 2 months ago, # ^ |   0 They actually used the full spanning forest definition in the problem statement because the graph is not guaranteed to be connected.So we just find the spanning tree (min / max) in the individual connected components. Looking at the samples clears it even more.
 » 2 months ago, # |   +6 Howcome Div2E is only 1700 rated though it has only 700s ACs. I am new to MST ,apart from kruskal what else algorithms are used to make a MST from a graph?
 » 2 months ago, # | ← Rev. 2 →   -7 problem c tutorial is really dedicated to people who already solved it only !!! it's hints is just define the problem and it doesn't make any sense. So the answer is the only letter appearing odd times in the input data.why the above statement is correct ? what is its proof ? what is the explanation of the two situations of letter c ?
 » 2 months ago, # |   0 Thanks for the editorial and the round, div2 C is very interesting
•  » » 2 months ago, # ^ |   -27 thanks for the bad editorial and the round , div2 C is the worst problem ever I seen.
 » 2 months ago, # |   0 Problem C: I get a runtime error on test case 6. Is there anything special about that case? Thanks.
 » 2 months ago, # |   +2 Idk about y'all. But from a practice perspective, doing div2 C was the perfect problem to come by and solve quickly after not making progress on a different problem for an hour.
 » 2 months ago, # |   0 Anyone can explain How to tackle observation-based problem as bits related or Number theory related. In which there are some patterns in the output. I usually tack lots of examples but am not able to come up with a solution..
 » 2 months ago, # |   0 Problem EPlease tell why my solution is failing: My SubmissionMy approach is very similar to that given in the editorial but I have used priority queue instead of sorting the edges by weights. Although it is giving correct output for the sample test case, but giving Wrong Answer verdict on submission.
 » 2 months ago, # |   +15 Perhaps a slightly different solution to Div1D.We know an $y$ is bad iff there exists an $x$ and $i$ where $y \in (x^2 + x - a_i, (x + 1)^2 - a_i) = \mathcal{I}(x, i)$. Fix $x$. If $a_i - a_{i - 1} \leq x$, $\mathcal{I}(x, i) \cup \mathcal{I}(x, i - 1)$ is an intervals. Thus, the number of bad intervals (for a fixed $x$) equals to the number of $i$ where $a_{i} - a_{i - 1} > x$ plus 1.Said another way, for a fixed $i$, it contributes to a $x$ if $x \leq a_{i} - a_{i - 1}$. Therefore, the total number of bad intervals is $\sum_{i} (a_i - a_{i - 1}) = a_n$.After finding all bad intervals, the rest can be solved in any way you like. I note that the solution is different from the official editorial as the harmonic series appears nowhere.
•  » » 2 months ago, # ^ |   0 Brilliant solution! And we can use radix sorting to optimize the time complexity to $O(n+a_n)$ since $l\le a_n^2$ holds for each interval $[l,r]$.
•  » » » 2 months ago, # ^ |   0 However, assuming only the comparison model, I can only achieve $O(a_n \log a_n)$ as I have no way to avoid sorting.If we take a stronger model like the RAM model, sorting $n$ integers of $w$-words still takes $O(n \frac{w}{\log n})$ time. Though there is faster integer sorting algorithm exists, it's not linear after all.
 » 2 months ago, # |   0 Can someone explain for problem B what's the solution for this test case: 2 1 1024 2048
•  » » 2 months ago, # ^ |   0 Answer = 3 you can add 2+1 = 3 and the sequence will be 3 1024 2048 then add 3+1024 = 1027 and the sequence will be 1027 2048 and then add 1027+2048 = 3075 an odd number
 » 2 months ago, # |   0 Can anyone kindly elaborate the solution for 1687C Sanae and Giant robot?
 » 2 months ago, # | ← Rev. 2 →   0 Can somebody explain me why my submission 159609287 to div2 F fails? I tried stress testing it on cfstress.com with a range of constraints but couldn't find any counterexample. My solution idea is based on the editorial's idea of making all elements of s 0 by repeatedly choosing segments with both ends 0 and making that whole segment 0. To implement this, I kept a segment tree for maintaining number of 0's in any segment of the array s. Now, I sorted all the given m segments according to their l value (stored in a vector of pairs,v) and kept 4 sets offl(segments currently traversed whose both ends are non zero,sorted wrt l value),offr(same as offl but sorted wrt r value),onl(segments whose r end has a 0 but not the l end,sorted acc to l value) and onr(whose l value is 0 but not r,sorted wrt r value). Then I iterated through v. If the current segment is non zero at both ends,then I insert it into offl and offr, else if exactly one end is 0 I insert it into onl or onr accordingly depending on the 0 end. Else if both ends are 0, then I update that segment to all zeros and also repeatedly update offl,offr,onl,onr according to the new updation of the array and also update segments which were initially in onl or onr but after the latest updation of array s,became 0 at both ends. This step repeats until I am not able to update any of the 4 sets or any more segments. You can have a look at my code for better understanding of the approach.
•  » » 2 months ago, # ^ |   +1 Sure, take a look at Ticket 10982 on CF Stress.Remember that, in the free plan, you only get 60 seconds of stress testing time on the server. To best utilize it, you should choose the constraints a bit smartly, for example, instead of keeping $t\_low$ and $t\_high$ as 1, you can increase both of them to infinity (while keeping the product less than the limit). This would generate, say, $2000$ test cases per input, which has a higher chance of finding a counter example. If you get "Data too large" verdict, you can gradually decrease the constraints on $t$ using binary search, but now you at least know that a counter example does exist for smaller $n$.But if you don't want to decrease the constraints on $t$, just copy the large testcase, and in your code, print the failing testcase on the error stream. You can get this TC number from the difference highlighter at the bottom.For example, I got this TC Input7 4 2 1 1 2 1 1 2 1 2 1 1 2 2 1 3 6 6 7 4 5 1 4  Expected OutputYES  Your OutputNO `
•  » » » 2 months ago, # ^ |   0 Thanks a lot!! Will keep this in mind,the next time.
 » 2 months ago, # |   0 The problem 1688B — Patchouli's Magical Talisman. Same idea with the answer. I wrote quite a few lines and had to use the queue
 » 2 months ago, # |   0 I like this round! Thanks to the Chinese problem-makers!
 » 2 months ago, # | ← Rev. 4 →   0 I understand the solution now. Deleted my comments.
 » 2 months ago, # |   0 Maybe there is somebody like me unable to understand the official editorial as a g.f. dummy, I would like to share my personal note here.
 » 2 months ago, # |   +1 1687A — The Enchanted Forest. I don't understand, why for k > n additional mushrooms is (2 * k — 1 — n) * n / 2. Please, help me, if you know. Thanks. And, please, don't downvote, because I really don't understand...
•  » » 2 months ago, # ^ |   0 I have done in this way:if(k>n) We know ans= sum(a[i] for all 0 <= i
•  » » » 2 months ago, # ^ |   0 Thank you very much!
 » 7 weeks ago, # | ← Rev. 2 →   0 C is genius!
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by huangzirui (previous revision, new revision, compare).