### awoo's blog

By awoo, history, 2 years ago, translation,

1671A - String Building

Idea: BledDest

Tutorial
Solution (BledDest)

1671B - Consecutive Points Segment

Idea: vovuh

Tutorial
Solution (vovuh)

1671C - Dolce Vita

Idea: vovuh and BledDest

Tutorial

1671D - Insert a Progression

Idea: vovuh and BledDest

Tutorial
Solution (awoo)

1671E - Preorder

Idea: BledDest

Tutorial
Solution (BledDest)

1671F - Permutation Counting

Idea: BledDest

Tutorial
Solution (BledDest)
• +70

| Write comment?
 » 2 years ago, # |   +7 I've known that F needed precalc,but I didn't solve it.qwq
•  » » 2 years ago, # ^ |   +3 In fact, when $n > k^2$ holds, the answer is a $O(k)$-degree polynomial. So you can use lagrange interpolation to solve this problem without precalc.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I see,probably.Could I see your code to understand further?
•  » » » » 2 years ago, # ^ |   0 You can see A-SOUL_Diana's Code. 154556037
•  » » » » » 2 years ago, # ^ |   0 thanks!
 » 2 years ago, # |   0 An interesting thing about problem b I found, the difference between the first element and the last element cannot exceed $n + 1$. as long as the difference is less than or equal to $n + 1$ the answer is always yes. I'm not the best at proofs, but I think this is because the greatest difference between a series of $n$ consecutive integers is always $n - 1$, and our operations can increase the first element by one and decrease the last element by one, thereby shrinking the maximum difference between elements by two at most. So if the maximum difference is greater than $n - 1 + 2$ then the answer is no. What I can't figure out is why the ones in the middle can always seem to fix themselves if this is true. Still, this solution works in $O(1)$.my code
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 Basically you are describing the same equation as the one in the solution: x[n-1]-x[0]-n+1 <= 2 <=> x[n-1]-x[0] <= n+1I actually solved this like a dumb person by shifting x[0] to the right or keeping it where it is and checking if everyone of the next elements can be shifted to the proper position according to where x[0] is fixed. So my complexity is O(2n) = O(n). Still works since reading the input is also O(n), but my solution is roughly 3 times slower than necessary.From my understanding, the solution described by the creator of the problem refers only to how many gaps there are between the first and last elements. If there are 0 gaps we're done, if there's one we can just shift one side and connect it with the other and if there are 2 gaps we shift 2 "chunks" so that everything is connected. On the other hand, if there are 3 or more gaps (which will make the inequality you referred to become false), then if one thinks about it, he will realize that there is no way to shift those 3 or more "chunks" in a way that they can be consecutive.The O(1) solution blew my mind on how simple it was. This problem caused me to overthink :D
 » 2 years ago, # |   +9 How to come up with alternative solution of F?
•  » » 2 years ago, # ^ | ← Rev. 4 →   -8 [deleted]
•  » » » 2 years ago, # ^ |   0 It's not that contest
 » 2 years ago, # |   +3 Can someone explain the hashing solution for E?
 » 2 years ago, # |   +12 If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.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. 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 years ago, # |   0 Can someone send code for precalculation in 1671F - Permutation Counting ?
 » 2 years ago, # |   0 It seems that problem F can be solves with dp, but without precalc. But how to do that?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I was thinking that as well,and had a original idea.
 » 2 years ago, # |   +3 Can someone help me see where my B problem is going wrong，This caused my crash and lower rate my code
•  » » 2 years ago, # ^ |   +1 This happens because if the answer is NO your code goes to end and doesn't input remaining numbers. So they will be in the next test case and all numeration of the input numbers breaks so your code gots WA. To fix it your need to input ALL numbers even if the answer is NO now.
•  » » » 2 years ago, # ^ |   +3 Thank you very much! ! ！ It was a stupid mistake T_T
•  » » » 2 years ago, # ^ |   +3 I modified it, but it still seems to have a problem code
•  » » » » 2 years ago, # ^ |   +1 This happens because your solution can print two NO instead one. You must append the word continue; after the first check in cycle to not run the second check if the first check is already NO. And you will get AC then.
 » 2 years ago, # |   0 So, I have managed to create a test that hacks the hashes in the model solution for problem E. Now, my curiosity is: when hacking a solution, what does the checker use to find out what the correct answer to that given test is? Since if it would use the model solution, using a test like this, on which the model solution gives a wrong answer, could hack every solution, even the correct ones, and also make the problem impossible to solve if added to the testcases.
•  » » 2 years ago, # ^ |   +22 I've changed the model solution so that it is deterministic now, so the checker will compare the answer to the deterministic solution. Most likely the outcome will be something like "unexpected verdict" on hack since one of presumably correct solutions in Polygon is challenged.By the way, how do you hack the model solution? I thought this way of hashing subtrees worked well.
•  » » » 2 years ago, # ^ |   0 What I have done is: try random trees with n=5 until two give the same first hash (takes about 60k tries on average) try trees with n=11 constructed as follows: first 6 layers are all 'A', and each of the subtrees under the 7th layer is a random one between the 2 found in step 1, this guarantees that the first hash will still give the same value to all the trees generated like so. And try until two trees give the same second hash (about 60k tries as well). same as step 2, but this time with n=17, and the subtrees under the 7th layer being a random one out of the 2 found before, until two trees give the same third hash (also around 60k tries)
•  » » » » 2 years ago, # ^ |   +10 Do you mean that you've hacked the hashes with seed $42$? awoo always replaces generator seeds to $42$ when posting randomized solutions in editorials. You can try uphacking the solution, but most likely it won't work since the random generator seed in the actual solution is not $42$. Instead, it's time-dependent.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 oh, yeah, I have hacked the one with seed 42, it makes sense for the actual solution to be time dependent.
 » 2 years ago, # |   0 Can someone explain why https://codeforces.com/contest/1671/submission/155171162 is failing on test case 5? Cannot find the bug...
 » 2 years ago, # |   0 Can someone explain the part of editorial on problem D which says "you can insert 1 somewhere, then insert x somewhere. The rest of insertions will be free." Why will be the rest of the insertions be free?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 If you have 1, x somewhere or x, 1 somewhere than you can insert arbitrarily any element between 1 to x in between them for 0 cost , I will discuss 1, x case you can do x, 1 similarly , Now suppose you insert 1
 » 2 years ago, # |   +3 In problem E, can anyone explain how are we checking the equality of equivalence classes using just the lexicographically smallest string in preorder?
 » 2 years ago, # |   0 we can get the best insertion of 1 and x in o(1) by doing this: (ans) variable is the sum of the differences of the initial value, and (mn) refers to min element of the initial array and (mx) refer to max element of initial array if(mn>1) ans+=min(2*(mn-1), min(v[0]-1, v[n-1]-1)); if(mx
 » 10 months ago, # | ← Rev. 4 →   +7 here's the solution to E (without hashing)