### awoo's blog

By awoo, history, 23 months ago, translation,

1622A - Construct a Rectangle

Idea: BledDest

Tutorial
Solution (Neon)

1622B - Berland Music

Tutorial
Solution (awoo)

1622C - Set or Decrease

Tutorial

1622D - Shuffle

Idea: BledDest

Tutorial
Solution (BledDest)

1622E - Math Test

Idea: BledDest

Tutorial
Solution (Neon)

Idea: Neon

Tutorial
Solution (Neon)
• +80

| Write comment?
 » 23 months ago, # |   0 How can we solve Problem D in O(n)?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +14 Compute the location of each “1” in the string and for each of them, count the number of strings where it is the first “1” that is moved. This is just the difference of two binomial coefficients.EDIT: here is a relatively clean example solution
•  » » » 23 months ago, # ^ |   +1 I had same solution, but I precompute all binomials in O(n^2). Thanks for your code! I think I learned something!
 » 23 months ago, # | ← Rev. 2 →   0 Is someone solved C using the ternary search on final value of minimum element and cost of comparison equals no of moves required for that final value?
•  » » 23 months ago, # ^ | ← Rev. 3 →   0 I had, but unfortunately it failed on system tests. I got accepted after system tests ( https://codeforces.com/contest/1622/submission/140871019 ). However, my solution is very strange.....
•  » » 9 months ago, # ^ |   0 I know it's late, but here's my solution https://codeforces.com/contest/1622/submission/198335525 . It fell on the 12th test due to the fact that we do not know where to shift the boundaries of the ternary search if the values in m1 and m2 are equal, but I moved.
 » 23 months ago, # |   0 Why do we need random numbers for primes in problem F?
•  » » 23 months ago, # ^ |   0 For hashing. Xor have this property that if you xor same value even number of times, then you get 0. We want to check if in 1! 2! ... n! all primes exists even number of times.I know this trick from Zobrist hashing. Not sure how it is call in CP.
 » 23 months ago, # | ← Rev. 2 →   +57 Here I've got a solution to problem F without hashing or any other randomicity. Though I don't know how to prove it, it seems to be correct. Due to the limitation of the space, I'll only put the conclusions here.First if $n = 1$, the answer subset include only $1$. Now we assume $n \not = 1$.If $n \equiv 1 \pmod 2$, we check if $n \cdot (\frac{n - 1}{2} - 1)$ is a square number. If so, the answer subset is all numbers from $1$ to $n$ except $\frac{n - 1}{2} - 2$ and $n - 2$.If $n \cdot (\frac{n - 1}{2} - 1)$ is not a square number, $n$ will not be in the answer subset, and we let $n \leftarrow n - 1$ and continue our discussion.So we now have $n \equiv 0 \pmod 2$. Let $m = \frac{n}{2}$.If $m \equiv 0 \pmod 2$, the answer is $1, \cdots, n$ except $m$.Else we have $m \equiv 1 \pmod 2$. Check if $\frac{m + 1}{2}$ is a square number. If so, answer is $1, \cdots, n$ except $m + 1$.We also check if $m = 9$. If $m = 9$, answer is $1, \cdots, n$ except $7$.In the case that neither $\frac{m + 1}{2}$ is a square number nor $m = 9$, answer is $1, \cdots, n$ except $2$ and $m$.Obviously there must be $\text{answer's size} \geqslant n - 3$, for there will be at most $2$ absent number for even $n$ and one more for odd $n$.Check 140891764 for code. I use this OEIS sequence to reach some of the same conclusion as in the official solution.As you see, this solution is partly based on the official solution, but to construct the subset by just discussing about $n$, instead of using hashing.
•  » » 23 months ago, # ^ |   -10 How to proof this constructed method?
•  » » 18 months ago, # ^ |   0 This solution is actually wrong; if we replace the special $m=9$ with any $m=a^2$ such that $a$ is a solution to the pell equation $a^2-2b^2=1$, then removing only $(m-2)!$ works. Here $m$ is obviously odd.Everything else does look fine though.
 » 23 months ago, # |   0 I don't know why I printed max(result, 1) and ruined my submission in problem D :'(
•  » » 23 months ago, # ^ |   0 Same mistake :)
•  » » » 23 months ago, # ^ |   0 +1;
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 can anyone give me O(n) solution
•  » » » » » 23 months ago, # ^ |   0 140865670 here you go
 » 23 months ago, # |   0 In problem C i'm facing overflow issue. Can someone please help to find out where is my code overflowing i have verified the calculations and data type multiple times. 140977108
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 Use "ll reduce_operations" in place of "int reduce_operations" code
 » 23 months ago, # |   0 Problem B: "The general way to prove it is to show that if the order has any inversions, we can always fix the leftmost of them (swap two adjacent values), and the cost doesn't increase." Can anyone give a proof on that?
 » 23 months ago, # |   +3 Can someone please explain D, tutorial explanation is somewhat tough to understand.
 » 23 months ago, # |   0 For problem D test case 23 has answer 0.How is 0 answer possible given we always have the string s?
•  » » 23 months ago, # ^ |   +11 The answer is not 0, but 0 mod P, which means that the actual integer answer is a multiple of P = 998244353.
•  » » » 23 months ago, # ^ |   0 I see.Thank you!
 » 23 months ago, # |   0 For problem F, solution part: Why do we have to include rf[x]!=x in if (rf.count(x) && rf[x] != x) return {rf[x], i};?
 » 23 months ago, # |   0 Is there any efficient ternary search algorithm???? I have used ternary search on 1622C - Set or Decrease. It passed the pretest but give a wrong verdict on system test case. Though, I have also checked +-2 range from the expected range manually. Here is my solution 140786085Please help me.
 » 23 months ago, # |   0 I tried using binary search for C. But the solution gets TLE. I can't find the reason for my mistake. Can somebody help? Here's the link to my submission 141226085
•  » » 23 months ago, # ^ |   0 at some point lo and hi becomes equal and ur loop becomes infinite loop. try lo
 » 23 months ago, # |   0 How sometimes answer for D can be 0. Could you please explain?
 » 23 months ago, # |   0 Can someone explain the accurateFloor function in problem C? why can't we simply write c/d — 1 when c<0?
•  » » 23 months ago, # ^ |   0 for exmple ： -3 / 1 ， you can't c/d — 1
 » 23 months ago, # |   0 For problem D, can't we use the inclusion/exclusion principle to count duplicate occurrences? Here is my solution, but it's giving WA in test 10. These are the steps of my solution: 1. Compute all the intervals [i,j] such that the number of 1 in the interval is k. Let s1, s2, s3,...sk be the intervals. 2. Number of common combinations between s1, s2, s3,...si is the arrangement of one and zero that are present in the intersection of these. Then use inclusion and exclusion principle to get union of these.
•  » » 23 months ago, # ^ |   0 Consider this testcase 6 3 111011 We need to permute substrings containing exactly three $1s$. Since the entire string contains a single $0$, the uniqueness can be identified by the position of $0$. Since $[1110]$ contains exactly three $1s$, we can place a $0$ at any of the first four spots. Since $[1011]$ also contains exactly three $1s$, we can place a $0$ at the last two spots too. Hence, there are 6 possible configurations.However, your code outputs 7.
•  » » » 23 months ago, # ^ |   0 Thanks for providing a test case. Can you explain to me why my logic is wrong?
•  » » » » 23 months ago, # ^ |   +5 The problem involves substrings instead of subsequences. You can prove by drawing or otherwise, that only adding contributions from k-one substrings and removing those of (k-1)-one substrings is optimal, rather than c(k) - c(k-1) + c(k-2) - c(k-3).... You would also have to make sure that all the intervals must follow (l == 0 || v[l - 1] == 1) && (r == n - 1 || v[r + 1] == 1), as its only feasible to stop moving left or right when we come across a 1 or else we will be recounting things.code for above approach
•  » » » » » 23 months ago, # ^ |   0 Understood it. Thanks for providing the explanation.
 » 23 months ago, # |   0 For Problem D, I think there's a pretty manageable way of iterating over the substrings of interest and keeping track of how shuffling different substrings may result in the same string.Iterating from left to right, say we have processed the substring $[l_1, r_1]$ and we're now processing $[l_2, r_2]$. $[l_2, r_2]$ has a part that overlaps with $[l_1, r_1]$ and a part that doesn't. Shuffling $[l_2, r_2]$ will result in a duplicate string if the part that doesn't overlap remains the same as the original. If there are $c$ ones in the overlapping interval, then there are ${{r_1 - l_2 + 1} \choose c}$ duplicate strings that result from shuffling $[l_2, r_2]$.This approach can reach $O(n)$.
 » 10 months ago, # |   0 In problem C, I don't understand how the testcase: 10 1 1 2 3 1 2 6 1 6 8 10 gives 7.Could someone explain a possible sequence of moves?
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 testcase: 10 1 1 2 3 1 2 6 1 6 8 10 possible sequence of moves: 1 2 3 1 2 6 0 6 8 10 (decrease a7) 1 2 3 1 2 6 -1 6 8 10 (decrease a7) 1 2 3 1 2 6 -2 6 8 10 (decrease a7) 1 2 3 1 2 6 -2 6 8 -2 (set a10 equal to a7) 1 2 3 1 2 6 -2 6 -2 -2 (set a9 equal to a7) 1 2 3 1 2 6 -2 -2 -2 -2 (set a8 equal to a7) 1 2 3 1 2 -2 -2 -2 -2 -2 (set a6 equal to a7) hope this helps
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Hey, I know its late but can you help me in this submission 209184101 I am getting wrong answer on test case 165 but I don't know how to move forward.variety-jones can you help in this?
•  » » » » 6 months ago, # ^ |   +1 Take a look at Ticket 16869 from CF Stress for a counter example.
•  » » » » » 6 months ago, # ^ |   0 CF stress is just amazing. Helps to find the mistakes and learn from them instead of seeing the solution. Definitely boosts confidence. Big thumbs up for such a tool!!!
•  » » » » » » 6 months ago, # ^ |   +1 Thanks. Glad you found it useful. Debugging one's own solution instead of implementing editorial's approach was one of the major motivation for building the tool.
 » 2 months ago, # |   0 I tried binary search in problem 1622C ,but I am getting wrong answer on test case 2 on 2300 case. please can anyone help where I am wrong. solution--https://codeforces.com/contest/1622/submission/225005289
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 My code gives wa on case 2700 something , can't figure out what i am doing wrong. if anyone could please look at my code submissionthanks
•  » » » 2 weeks ago, # ^ |   0 Take a look at Ticket 17149 from CF Stress for a counter example.
•  » » » » 13 days ago, # ^ |   0 Thanks a ton!!