rsj's blog

By rsj, history, 2 months ago,

1787A - Exponential Equation

Idea & Solution: rsj

Tutorial

1787B - Number Factorization

Idea & Solution: rsj

Tutorial
Solution

1787C - Remove the Bracket

Idea & Solution: rsj

Fact
Tutorial
Solution

1787D - Game on Axis

Idea & Solution: jiangtaizhe001

Tutorial
Solution

1787E - The Harmonization of XOR

Idea & Solution: jiangtaizhe001, rsj

Tutorial
Bonus Problem

1787F - Inverse Transformation

Idea & Solution: qzhwlzy, rsj

Tutorial
Solution

1787G - Colorful Tree Again

Idea & Solution: rsj, 275307894a

Tutorial

1787H - Codeforces Scoreboard

Idea & Solution: jiangtaizhe001, rsj

Something To Say
Tutorial

1787I - Treasure Hunt

Idea & Solution: 275307894a

Tutorial

I'm really sorry for the unsatisfactory problems and the tough 3 hours ;)

However, I still hope you can enjoy the problems after the contest. The editorial hasn't been fully checked, so feel free to comment if there're errors, typos or you have questions about them. We'll check them out tomorrow. Thanks!

• +216

 » 2 months ago, # |   +23 the system test has finished, but my solution on C did not judge, what happened?
•  » » 2 months ago, # ^ |   +1 it's accepted now
•  » » » 2 months ago, # ^ |   +14 congratulations bro
•  » » 2 months ago, # ^ |   0 bro how your ratings is that high ?? Do you have any past experiences with CP ??
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +40 Well, he started in 2012 :D
 » 2 months ago, # |   0 Very difficult A. The problems in general feel very observational. At least they are interesting.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 i think most who solve it try x=1 and get fun equal 2*y and notice that no sol for odd from test case
•  » » » 2 months ago, # ^ |   +8 Yeah, I realized that the equation would always be even so I looked for a way to construct even answers. But originally I thought you could brute force it since n has to be divisible by xy so I tried finding divisors and looking for the other component. Probably should have realized that problem A shouldn’t be that hard.
•  » » » » 2 months ago, # ^ |   +1 you could bruteforce it using binary search 191169657
•  » » » » » 2 months ago, # ^ |   -8 Time complexity? I don’t know how your iterating though all of n.(Java user here)
•  » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 there's a fair amount of boilerplate for checking if values are out of bounds in the binsearch loop and once more after the loop. But other than that I think the code is fairly simple. WLOG let's assume x <= y. Then the outer loop iterates over x up until n (if we find solution or we know we won't find it we just break out of the loop). The inner loop binsearches on y from x to n. If y is the smallest possible (equal to x) but the formula gives an integer bigger than n, we know we are out of options so print -1 and return.As for TC, the solution can't iterate too high in the x, because the value of the formula grows exponentially. Inner loop (binsearch) is O(log n). So a rough upper bound is O(log^2 n)P.S. solve() function would look the same in Java, except for stdin/out (using cin and cout). Maybe bool -> boolean too, and you have Java code, it's all the same as C lol
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Chat gpt is pro in converting code from one language to another. Just 2-3 subtle changes and we are done
 » 2 months ago, # |   +37 My funny solution for G: Basically the same as the editorial, but instead of maintaining paths by their LCA, maintain them by their highest degree node. This means that each node will affect $\sqrt n$ nodes instead of just $1$, yielding an $O(q\sqrt n \lg n)$ solution. Implemented in C++ this takes 453 ms.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +10 And I solved it using centroids, thus adding log factor to the solution and not changing the idea. Couldn't implement it in time, though...
•  » » » 2 months ago, # ^ |   +18 Luckily for me, I had enough time even to convert to C++ after my Kotlin attempt TLEd.
•  » » 2 months ago, # ^ |   +45 Update: I was able to hack (TLE) my solution: https://codeforces.com/contest/1787/hacks/886533 Seems like it was completely unanticipated by the authors >:).
 » 2 months ago, # |   -30 problem A is fun
 » 2 months ago, # | ← Rev. 3 →   +41 For me, it's like:A: acceptable.B: prime factorization is not something that appears in d2B, and the task is quite boring.C: Nothing wrong, but it is too hard for C I guess.D: Easy problem with details, but nothing too wrong.E: Actually the guesses is not quite easy to make, especially for person like me tended to prove all the guesses during the contest. So it's kind of acceptable.F: Huge work. Very, very large work. Is these kinds of problems really suitable for codeforces? We have D and G to let participants do huge works(lolG: Huge work. Not interesting, and it's a little bit tricky to understand the problem correctly. H : Not able to give comments.I : Too similar to some other problems.
•  » » 2 months ago, # ^ |   +29 I don't agree that F was huge work. It was fine for that slot.
•  » » » 2 months ago, # ^ |   0 Well, maybe I'm not good in solving these kind of implement problems:( But I think the implement part is far bigger than the thinking part.
•  » » 2 months ago, # ^ |   +46 If G feels like huge work to you, I don't think you are able to judge that problem
•  » » » 2 months ago, # ^ |   0 Interesting. You are right.
 » 2 months ago, # | ← Rev. 2 →   +30 If F is a div2D problem which only ask the minimal value, this contest would be better.
 » 2 months ago, # |   0 problem B. what am I doing wrong here(https://codeforces.com/contest/1787/submission/191135406). can I see the testcase for which this code fails?
•  » » 2 months ago, # ^ |   +3 click show test details at the bottom
•  » » 2 months ago, # ^ |   0 I think there's precision errors because you have number = number / i instead of number = number // i. I couldn't find a test case that breaks it but 191191379 get's AC. (Seems like a strange behavior since we just checked that the numbers are actually divisible...but I'm not very good at Python so maybe it's expected).
•  » » » 2 months ago, # ^ |   0 Probably because number / i returns a float and number // i returns an int in python, computing floats is probably decently slower
•  » » » » 2 months ago, # ^ |   0 thank you, will keep in mind next time
 » 2 months ago, # |   -11 Thanks for the well written editorial
 » 2 months ago, # |   +8 Seriously, how did the top 1 solve problem H in 14 minutes?
•  » » 2 months ago, # ^ |   0 You spend exactly one minute to solve each problemBy the statement of problem H, he delayed for 6 minutes.
•  » » 2 months ago, # ^ |   +3 See this. Nevertheless, I am really impressed that it has taken only 14 minutes to read enough problems to find H (and notice something familiar) and then code it.
 » 2 months ago, # |   +28
•  » » 2 months ago, # ^ |   +3 Compiled you mean?
 » 2 months ago, # |   0 For problem C, why can we assume that y_(i-1) < x_(i+1) ?
•  » » 2 months ago, # ^ |   0 Because $y_{i-1}>x_{i+1}$ is symmetric with this
 » 2 months ago, # |   +43 Not sure why the editorial says $O(n\log^2n)$ is "not good enough" for I, it seems that many of the solutions that passed have this complexity (191159985, 191159474, 191162667, 191147979).
 » 2 months ago, # |   +10 Bonus F: solve problem but instead of reversing P^(2^k), we reverse P^(k).Did anyone else do that? :P
 » 2 months ago, # |   +3 Real math forces
 » 2 months ago, # |   +26 On E my code only make subsequences like $[a,a\oplus x]$ and overlook $[x]$, but it's accepted, so does it work or it can be hacked?
•  » » 2 months ago, # ^ | ← Rev. 5 →   +34 Oh I know, if the answer is YES and $x\le n$, let $m$ be the number of subsequences $[a,a\oplus x]$, then $m\ge k-1$, $m\equiv (k-1) \pmod 2$.if $m=k-1$, $[x]$ will in the last subsequence, otherwise it with redundant subsequences $[a,a\oplus x]$ will in the last subsequence.So it's unnecessary to consider subsequence $[x]$.
 » 2 months ago, # |   0 Can somebody recommend problems similar to problem C ?
•  » » 2 months ago, # ^ |   0 Click the tag and choose DP which is 1600 to 2000(rating,maybe higher than 2000).
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Thanks but i need more specific recommendations based on personal experience not random problems :)
•  » » » » 2 months ago, # ^ |   0 You could google this:linear dynamic programming in Codeforces.
•  » » » » 2 months ago, # ^ |   0 Then you will find some tutorial that is helpful to you.
 » 2 months ago, # |   0 Can you roll back and give me another 1 rating? It's sad to be stuck at a rating of 1599.
 » 2 months ago, # |   0 I have some questions about problem H's editorial.is $lim_i = c_i$?The sentence " with an additional number $k_i \times j$ in the middle, where $j$ is the maximum number satisfied $g_{i-1,j-1} \leq k_i \times j$ "Shouldn't be: "with an additional number $k_i \times j - lim_i$ in the middle, where $j$ is the maximum number satisfied $g_{i-1,j-1} \leq k_i \times j - lim_i$" ? The way the sentence right now looks like you just ignore the $lim_i$ value in the minimum, which doesn't make sense to me.
 » 2 months ago, # |   0 Thanks for tutorial.
 » 2 months ago, # |   0 How to improve noob to pupil any topics I will study otherwise what should I do? Pls reply
•  » » 2 months ago, # ^ |   0 Try to do CSES problem set Introductry and sorting and searching problem will help you in improving
 » 2 months ago, # |   0 I'm curious as to what the intuition behind problem E is supposed to be. It seems hard to figure out the ideal strategy.
•  » » 2 months ago, # ^ |   0 Let's take some correct pair ${a, x \oplus a }$, and suppose the numbers go into different sets $A$ and $B$ respectively. Then it's easy to see, that we can retrieve those numbers to form a pair set. So we convert $A$ and $B$ into ${a, x \oplus a}$ and $A \cup B \setminus {a, x \oplus a}$ with both xor still equal to $x$. Now the pair is in its own set and the answer isn't smaller.
•  » » » 2 months ago, # ^ |   +8 MikeMirzayanov, somehow the curly braces do not render correctly (or at all), please take a look.
 » 2 months ago, # |   0 Many people solved E in the end but I didn't :V. I should have prac more problem like this
 » 2 months ago, # |   +6 I think the "reasom" in "Fact" of 1787C should be "reason".
 » 2 months ago, # |   0 I upsolved D and E on my own, should have skipped C :/. Didn’t know how to do dp. E was pretty interesting to prove.
 » 2 months ago, # |   0 i dont understand the solution of Dwhen the game cannot end at first, we can only change the numbers on the circleso why we should addans += (n + s[n + 1])to the answer?s[n + 1] is the nodes that can end the game, but i dont understand why we add n here.
•  » » 2 months ago, # ^ |   0 i understand it now :)
 » 2 months ago, # | ← Rev. 2 →   0 The proof part of problem E:"These $B$-th-bit-on numbers XOR $x$ must be smaller than themselves, so we can always obtain $M$ subsequences."I suppose we can not know whether the $B$-th-bit-on numbers is smaller than $x$ since the highest digit of $x$ may not be the highest of these numbers.(for instance, $x=2$, while $a_i=4$, and $x \oplus a_i$ is $6$)
•  » » 2 months ago, # ^ |   +3 $B$ is the highest bit which $x$'s is on. We only consider $a_i$ when $B$-th bit of $a_i$ is on, when $x=2=(10)_2$, $B=1$, $a_i=4=(100)_2$ so the $B$-th bit isn't on.When $a_i$'s $B$-th bit is on, $a_i\oplus x$'s $B$-th bit is off, and their higher bits are equal, so we have $a_i\oplus x< a_i\le n$.
•  » » » 2 months ago, # ^ |   0 Thanks for your kind reply. get it.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 Can you help me in problem E what about the case that number of subsequence parity from input is differ from the maximum subsequence that we found , we always can't construct it ?
•  » » » » 2 months ago, # ^ |   +3 In that case just consider the xor of all elements; the total xor value of the desired number of segments (each has an xor value of $x$) is different from the give array's xor value so there is no way to construct it.
•  » » » » » 2 months ago, # ^ |   0 Oh I got it thanks <3
 » 2 months ago, # |   0 can someone explain how C can be done by DP? (I'm new to this)
•  » » 2 months ago, # ^ | ← Rev. 3 →   +1 Since we can get unique $p_i$ and $q_i$ (assuming $p_i \le q_i$ ) satisfying $p_i+q_i=a_i$ to make $F$ as small as possible, where $x_i=p_i, y_i=q_i$ or $x_i=q_i, y_i=p_i$. Assuming we let all $x_i=p_i$ and $y_i=q_i$, we still have the possibility to swap some values of $x_i$ and $y_i$ to make the value of $F$ is smaller.Taking $n=5$ as an example, $F = a_1*x_2+y_2*x_3+y_3*x_4+y_4*a_5$.We can let $x_2 = p_2$, so that we can determine $y_2 = q_2$, and similarly if we let $x_2 = q_2$ we can determine $y_2 = p_2$. Then we can let $a_1*x_2 + y_2*x_3$ take the minimum value if $x_2$ takes the value of $p_2$ or $q_2$ by deciding the value of $x_3=$ ($p_3$ or $q_3$), and at the same time the value of $y_3$ is determined. Next, the value of $x_4$ can be chosen as $p_4$ or $q_4$ so that $a_1*x_2+y_2*x_3+y_3*x_4$ takes the minimum value if the value of $x_3$ is $p_3$ or $q_3$. Finally we can use the minimum value of $a_1*x_2+y_2*x_3+y_3*x_4$ and the $x_4$ corresponding to its minimum value, and then $y_4$ is determined, and after calculating $y_4*a_5$ we get $F$. in other words to find the minimum value of $F$ in the cases $x_4=p_4$ and $x_4=q_4$, and this process can be done by DP.It should be emphasized that we have been considering the minimum value of a part of equation $F$ in the case $x_i=p_i$ or $x_i=q_i$, and the current worse choice may be better later, so the greedy algorithm cannot be used.191171920 The state in this code preserves the specific values of $x_i$ and $y_i$, which may be easier to understand compared to using 0/1.
•  » » » 2 months ago, # ^ |   0 In problem C, can you explain what difference it makes logically (in dp transition) if we replace the original transition,F[i][0] = min( F[i-1][0]+y[i-1]*x[i],F[i-1][1]+x[i-1]*x[i] ); F[i][1] = min( F[i-1][0]+y[i-1]*y[i],F[i-1][1]+x[i-1]*y[i] ); to this transition,F[i][0] = min( F[i-1][0]+x[i-1]*x[i],F[i-1][1]+y[i-1]*x[i] ); F[i][1] = min( F[i-1][0]+x[i-1]*y[i],F[i-1][1]+y[i-1]*y[i] ); The answer for the second transition is coming different from the original answer but both of the transitions seem correct to me logically.
•  » » » » 2 months ago, # ^ |   0 To avoid confusion, I still use $p_i$ and $q_i$ to explain. f[i][0] can be considered as choosing $p_i$ to compute, and f[i][1] can be considered as choosing $q_i$ to compute. Then, as you can see from the process shown earlier, assuming that you currently choose $p_i$, then the next product will already have a number determined to be $q_i$. So for $F[i-1][0]+x[i-1]*x[i]$, F[i-1][0] has already determined one of the numbers in the next product to be y[i-1] instead of x[i-1].
•  » » » 2 months ago, # ^ |   0 thank you! I understand it now.
 » 2 months ago, # |   +8 Can someone please explain me the proof of E and why this solution works?
 » 2 months ago, # | ← Rev. 3 →   0 In problem D WA although my idea is the same as the editorial and I cant find the bug can anyone help? here is it 191163552edit:bug found
 » 2 months ago, # |   0 In problem C, for s = 3 and a[i] = 5. What can be the values of x and y? If I take (x,y) as (2,3) or (1,4) or (0,5) then the product (x-s)(y-s) becomes <0.
•  » » 2 months ago, # ^ |   0 equal to 0 is allowed
•  » » » 2 months ago, # ^ |   0 This 191151252 got accepted in which values of (x,y) is (2,3) for Testcase1 3 3 4 5 6 output: 3*4 + 2*6 = 24
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 using 2,3 would give (2-3)*(3-3) which is equal to 0 and it satisfies the given condition (xi−s)⋅(yi−s)≥0
•  » » » » » 2 months ago, # ^ |   0 Thanks
 » 2 months ago, # |   +1 1787C - Remove the Bracket For those who as me struggle to understand tutorial, here is explanation what they want to say. They want to say that optimal selection of x, y might be only on edge cases, by way of contradiction. Suppose some is not on edge case. Then it has $y_{i−1}$ and $x_{i+1}$. Two cases $y_{i−1} < x_{i+1}$ and $y_{i−1} > x_{i+1}$ lead to contradiction based on things from the editorial (look into it). And in the remaining case $y_{i-1} = x_{i+1}$ we can pick edge x, y without any loss.
 » 2 months ago, # |   0 In problem C, can anyone explain what difference it makes logically (in dp transition) if we replace the original transition, F[i][0] = min( F[i-1][0]+y[i-1]*x[i],F[i-1][1]+x[i-1]*x[i] ); F[i][1] = min( F[i-1][0]+y[i-1]*y[i],F[i-1][1]+x[i-1]*y[i] ); to this transition, F[i][0] = min( F[i-1][0]+x[i-1]*x[i],F[i-1][1]+y[i-1]*x[i] ); F[i][1] = min( F[i-1][0]+x[i-1]*y[i],F[i-1][1]+y[i-1]*y[i] ); The answer for the second transition is coming different from the original answer but both of the transition seem correct to me logically.
•  » » 2 months ago, # ^ |   0 They are just different. For each $i$ we have $x_i$ and $y_i$, one of them multiply by last number and another by next one.As an example, for $f_{i-1,0}$ we used $x_{i-1}$, then $y_{i-1}$ is left, so for $f_{i,0}$ we should use $y_{i-1}$ and $x_i$ then the formula is $f_{i,0}=f_{i-1,0}+y_{i-1}*x_i$.
 » 2 months ago, # |   0 Who is the Problem Authors ?
 » 2 months ago, # | ← Rev. 2 →   0 Can anyone give a reason why the following solution to H is wrong or give an example when the following solution fails.We pick the problem we would solve i'th minutes after the contest begins by picking the problem whose value would decrease the most after 1 minute passes. The implementation would be done using a multimap to store the problem whose value would decrease the most. The multimap will be maintained by getting all the values of t'(minutes)s when the a particular problem stops decreasing and by updating the multimap when that time comes.
 » 2 months ago, # | ← Rev. 2 →   0 "Changing edges not on the key path is always legal. If changing the edges on the key path, for node x, we can change its successor to nodes except its precursor or itself."We can also not change it to nodes which lead into cycles right? Its not enough to just subtract paths to predecessors on key path, we also have to subtract paths to nodes which lead into cycles right?
 » 2 months ago, # |   +77 I have a different solution for problem $G$.The idea is to run a BFS and label the edges according to when they were processed by the BFS. Below, I have the tree, with the edge colors and labels.Now, we can turn these edge labels into color labels. Define the label of a color to the minimum label of one of its edges. For instance, the label of the red path is 1, and the label of the yellow path is 18. The label of the purple color is 13.Now, whenever we perform an update (blocking or unblocking a node), we are updating at most two continuous range of labels. Say, for instance, we update the root of the tree. Then, we're blocking "red" and "blue" (label 1 and 2). If we were to update the node from which edges 4,5,6 protrude, then we're blocking "red" and "blue (4 and 5).Now, updating continuous ranges of intervals can be done with a segment tree. Let the index of the segment tree be the label of each color. So segmentTree[label[i]] = sum of weights of path with color i.Each time, we block some "path", we can subtract a big number from that contiguous range of the segment tree. Each time we unblock that path add back that big number. Now, it's just range minima of whole segment tree and range add.
 » 2 months ago, # |   0 can someone give more intuition on how to get to logic in problem C
 » 2 months ago, # |   0 Also, can someone suggest me how to get to specialist quickly. I have been around for a while but been on and off all the time.
 » 2 months ago, # |   +6 When will the plagiarism check run? 1787-C, Remove brackets was leaked on youtube and many cheaters did it disrupting the standings.
 » 2 months ago, # | ← Rev. 2 →   0 D: "If changing the edges on the key path, for node x, we can only change its successor to nodes on the tree with the end node except its precursor or itself."We are counting the opposite so shouldn't it be "to its precursor or itself on the tree with the end node"? Of course we also consider nodes outside the tree.
 » 2 months ago, # |   0 E: "the rest becomes a subsequence".Shouldn't it be "adding the rest to one of the other subsequences"? If there is a solution then the rest must xor to zero (obviously the rest cannot xor to $x$) so we can add the rest to any other subsequence.
•  » » 2 months ago, # ^ |   0 You find m — 1 subsequences, and the rest becomes the m-th
•  » » » 2 months ago, # ^ |   0 The rest does not xor to $x$ so cannot form a valid subsequence.
•  » » » » 2 months ago, # ^ |   0 But it should. If it doesn't then there's no way to form m valid subsequences. It is provable
 » 2 months ago, # | ← Rev. 2 →   +14 Here am I with my toxic grumblings about the quality of editorials again. Nothing new, I just decided to try reading editorials again and once again I ask myself why the editorial authors hate their readers so much.I'm just opening the solution for D and the first thing I see is int a[N], v[N], s[N]; struct E { int to; E *nex; } *h[N]; The heck is a? the heck is v? the heck is s? Why the list of edges is h?Probably it should be relatively easy for the typical audience of this problem to deduce that E means edge even if you don't care about the others, but a/v/s/h is just too much. I won't even ask why you needed a linked list. As a result, decoding and deobfuscating the heck is written in the "author's solution" easily competes by difficulty with the original problem.I understand that codeforces doesn't enforce the quality of editorials and it is done by putting the minimum effort possible, but put at least the minimum effort into making it readable, this is so below any bar.I find it hard to comprehend that people spend some supposedly huge amount of time on coming up with and polishing those problems, but cannot find some minutes to make the code they just submitted at least a bit readable before attaching to the editorial
•  » » 2 months ago, # ^ |   +3 Agree. Usually I only read the English tutorial and then implement my own solution.
 » 2 months ago, # |   +1 what is approximate difficulty of problem D?
 » 2 months ago, # |   0 When the ratings will get reupdated???????????? I became pupil, please re-add them fast!!!!
 » 2 months ago, # |   0 This contest was unique in that sense, that there were 3 working problems for me (Definition: working problem is a problem with difficulty approximately equal to contestant's rating), while for all contests it was either $0$ or $1$.From my point $D$ and $E$ have equal difficulty, and $C$ is a little more complex. It was foolish, that I didn't give a try for problem $E$, but after I read first sentense in editorial, I thought "damn, it is obvious" and quickly implemented it.
 » 7 weeks ago, # |   0 why in problem c after remove the bracket (xi+yi) it turns to …+yi−1⋅xi+yi⋅xi+1+????
•  » » 7 weeks ago, # ^ |   0 Oh i see
 » 6 weeks ago, # |   0 It's actually quite confusing you can't use python for a tutorial solution of a D problem. Is it true or i just do not know how to set recursion depth limit without getting ML?193974524
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 YesOf course, you may also use stack without recursion.
•  » » » 6 weeks ago, # ^ |   0 Well, yes. But then its not like a given solution for the problem. The question is, how to use recursion in Python properly?
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 So the problem with smt like sys.setrecursionlimit(200005) is, that it apperently reserves a lot of memory
•  » » » » » 6 weeks ago, # ^ |   0 You may follow the link. It works, I think.
•  » » » » » » 5 weeks ago, # ^ |   0 It appears i misunderstood your statement. Thanks:)), it really helped indeed.