### iNNNo's blog

By iNNNo, history, 8 days ago, translation,

Thank you for participating!

Solution
Code

Hint
Solution
Code

Hint
Solution
Code

Solution
Code

Hint
Solution
Code

## 1979F - Kostyanych's Theorem

Solution
Code
• +77

 » 8 days ago, # |   -47 C can be solved with Binary search,in case you have not thought of solution and still solved C using youtube and telegram,then it might help you.
•  » » 8 days ago, # ^ |   -12 U really want to help such cunts ?
•  » » » 8 days ago, # ^ |   -20 i know its useless but still i want them to know their place.
•  » » 8 days ago, # ^ |   +12 I wrote the binary search solution but then I noticed that the for the second test case in the test case 1 there was a valid answer for sum = 4 but not for sum = 3. So I did not submit it. I eventually came up with the solution(without cheating) but I dont think we can use binary search here.
•  » » » 8 days ago, # ^ |   0 check my solution,you will get it
•  » » » » 8 days ago, # ^ |   +5 Nah bro It just worked out cause there are too many values of sum that satisfy the problem.for the test case: n = 2; k1 = 3 and k2 = 3clearly sum = 2 gives a valid answer sum = 3 does not give a valid answer sum = 4 gives a valid answer So the conditions to use binary search are not met
•  » » » » 8 days ago, # ^ |   +3 https://codeforces.com/contest/1979/submission/264505456I just tried submitting my old solution too (binary search) and it got accepted but I still think this is wrong and can be hacked. what do you think?
•  » » » 8 days ago, # ^ | ← Rev. 2 →   0 .
•  » » 8 days ago, # ^ |   0 I don't think binary search is the correct approach. It might have worked due to numerous values of sum satisfying the condition.
•  » » » 8 days ago, # ^ |   0 If you modify the binary search range and pick the lower end to be the sum of all the k values the solution will always work.As per the condition in the official solution we can characterize the 1/k summation as a Harmonic mean, and we always know that arithmatic mean is greater than harmonic mean. Also for any valid solution in the above constraint all the values above any valid solution are also valid as every k is atleast 2 and as we increase the total bet the gain will increase if we just keep adding to the previously found arrangement.
•  » » » 8 days ago, # ^ |   0 actually, if there exists a solution for the given set of numbers then we can use any value as a numerator and distribute accordingly take for example 3, 2, 7 has a solution so any number can be used to generate a valid distribution the catch is that it won't be an integer always, like if you take 1 then 1/3 1/2 and 1/7 are also valid distribution because they give sum as 41/42 and each winning return is 1 but this won't be accepted as a solution because it is not integer so we find a value such that it gives integer for all ki divisions and lcm happens to be the smallest such value. and for the binary search to work after a certain point, the values become big and we can increase mid/ki values by 1 and they give valid distributions
•  » » 8 days ago, # ^ |   0 I really struggle with binary search problems, how to identify it in specific, can you help me some resources
•  » » » 7 days ago, # ^ |   0 Binary Search by Adtiya Verma is a great playlist if you are comfortable with Hindi.
•  » » » 7 days ago, # ^ |   0 I liked this: https://usaco.guide/silver/binary-search
•  » » 8 days ago, # ^ | ← Rev. 3 →   0 check my code: I just checked sum 10^9 and it is AC. 264511010
•  » » 8 days ago, # ^ |   +9 So many downvotes,did I offend the cheater community here.
•  » » » 8 days ago, # ^ |   0 get your concepts clear greenie
•  » » » 8 days ago, # ^ |   0 Surely i did.
•  » » 8 days ago, # ^ | ← Rev. 2 →   +4 actually no need to use binary search (as the upper bound values can always be used as sum of all elements and it will always suffice an answer if solution exists), just use sum = 1e9 and some necessary conditions for the answer to be true. #define neg1 cout<<-1<>n; vii v(n); input(v,n); int mn = INT_MAX, sm = 1e9, tot = 0; vii res(n); forl(i, n){ int curr = (sm / v[i]) + 1; mn = min(mn, curr * v[i]); tot += curr; res[i] = curr; } dbg(mn, sm, tot) if (sm < mn && tot < mn){ print_vec(res); return; } neg1 } 
•  » » » 7 days ago, # ^ |   0 Yeah i wrote the same code
•  » » » 7 days ago, # ^ |   +1 yeah but anyways the optimal choice of sum is LCM(k) — 1 if this does not work nothing will. Also I suggest you to actually solve the problem rather than taking shortcuts.
•  » » » » 7 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } There is no such thing as shortcuts, LOL! AC is AC, and clever AC is even better.
•  » » 7 days ago, # ^ |   0 ya, solved using binary search only
•  » » 6 days ago, # ^ |   0 haven't thought of binary search. simple observation was to find LCM ( it will factor all the elements and sum of all factors are always <=sum of numbers).
 » 8 days ago, # |   +89 An alternate solution for D using hashing: the final string will be of form $s_{p+1}\dots s_n s_p\dots s_1$ and must either start with a block of $k$ 0s or $k$ 1s. Generate the two possible final strings ($111\dots000\dots$ or $000\dots111\dots$), then iterate over $i$ and check if either of the two answer strings match this condition: Prefix of length $n-i$ is equal to $s_{i+1}\dots s_n$ Suffix of length $i$ is equal to $s_i\dots s_1$ Using hashing, each of these checks can be done in $O(1)$ for every position.
•  » » 8 days ago, # ^ |   +4 Thanks! Found it to be more intuitive than the posted solution
•  » » » 6 days ago, # ^ |   0 How to hash string? can you share some resources?
•  » » » » 6 days ago, # ^ |   0
•  » » 8 days ago, # ^ |   0 yes i also thought of same solution, but poor implimentation skills mine
•  » » » 7 days ago, # ^ |   0 Same, Indeed ! Way down we go!!!
•  » » 7 days ago, # ^ |   0 correct me if i am wrong but for problem D, in the examples, i think for the last test case, p=5 is possibly a correct solution but the online judge says its wrong?
•  » » » 7 days ago, # ^ |   0 if you choose p = 5 then final string will be 110011000011 but this aint 2 proper coz there are 4 consecutive 0s at i=6, but the resulting string should be 001100110011
•  » » » » 7 days ago, # ^ |   0 oh i get it, thanks, should have read the problem better
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 Thanks bananasaur for two possible final strings (111…000… or 000…111…).I use this in a previous question of Atcoder, but here, my mind is not thinking in that direction, although it's trivial ; I only do work for finding p.
 » 8 days ago, # |   +2 finally became green
 » 8 days ago, # |   +8 justice for 6k rank for doing 3 problems in div2:(
•  » » 8 days ago, # ^ |   0 what's up was this problem copied from somewhere??
•  » » » 8 days ago, # ^ |   +5 I think the problems are less intense for a div 2.
 » 8 days ago, # | ← Rev. 2 →   +79 Visual for 1979EAnimation showing valid points for pairs of points (in red and blue) that are $d=6$ Manhattan distance away from each other. The black dots are points that are both $d$ Manhattan distance away from both red and blue points. The black line shows how there always exists a pair of points in a triangle such that they are $(d/2,d/2)$ or $(d/2,-d/2)$ off.Here's a Desmos graph with draggable points if you want an interactive version. https://www.desmos.com/calculator/na6auayf25
•  » » 8 days ago, # ^ |   +15 This is very cool! What did you use to make the animation?
•  » » » 8 days ago, # ^ |   +27 I used the processing.js library on Khan Academy's coding environment with the following code. Rendering CodeSorry for the code messiness. function px(x1, x2, t) { return x1 * t + x2 * (1-t); } // parametric form of the diamond centered at (x,y) function tx(x, y, d, t) { var step = Math.floor((1-(t*4)%1) * d) / d; var x2 = 0; var y2 = 0; if (t < 0.25) { x2 = px(x + d, x, step); y2 = px(y, y + d, step); } else if (t < 0.5) { x2 = px(x, x - d, step); y2 = px(y + d, y, step); } else if (t < 0.75) { x2 = px(x - d, x, step); y2 = px(y, y - d, step); } else { x2 = px(x, x + d, step); y2 = px(y - d, y, step); } x2 = Math.round(x2); y2 = Math.round(y2); return [x2, y2]; } function mdist(x1, y1, x2, y2) { return Math.abs(x1 - x2) + Math.abs(y1 - y2); } var N = 16; var w = 400/N; noStroke(); frameRate(5); var d = 6; var draw = function() { background(255); // draw grid stroke(0, 0.2*255); for (var i = 0; i < N; ++i) { line(0, i*w, 400, i*w); line(i*w, 400, i*w, 0); } noStroke(); var t = (frameCount / 5 / 8) % 1; var x = N/2; var y = N/2; // compute 2nd point var xy2 = tx(x, y, d, t); var x2 = xy2[0]; var y2 = xy2[1]; // find 3rd points fill(0); for (var i = 0; i < 40; ++i) { for (var j = 0; j < 40; ++j) { var dgood = mdist(i, j, x, y) === d && mdist(i, j, x2, y2) === d; var overlap = (i === x && j === y) || (i === x2 && j === y2); if (overlap) { if (mdist(i+d/2, j+d/2, x, y) === d && mdist(i+d/2, j+d/2, x2, y2) === d) { stroke(0); line(i*w, j*w, (i+d/2)*w, (j+d/2)*w); noStroke(); } if (mdist(i+d/2, j-d/2, x, y) === d && mdist(i+d/2, j-d/2, x2, y2) === d) { stroke(0); line(i*w, j*w, (i+d/2)*w, (j-d/2)*w); noStroke(); } } if (dgood) { ellipse(i*w, j*w, 5,5); } } } fill(255, 0, 0); ellipse(x*w, y*w, 11, 11); fill(0, 127, 255); ellipse(x2*w, y2*w, 11, 11); }; Then I recorded screen and exported as gif.
 » 8 days ago, # |   0 Any idea how I can improve my logic? some questions just don't click sometimes. I seem to be practicing consistently, but the results are not showing. I don't know why
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 you're either doing practice with too hard or too easy problems, try changing the difficulty and solve problems on multiple platforms other than codeforcesHowever, improvement takes a long time to see and you should not give up
•  » » » 7 days ago, # ^ |   0 if i am bouncing between, 1200-1300,what should be the ideal rating to solve?
 » 8 days ago, # |   0 https://codeforces.com/contest/1979/submission/264505456Hey guys this is a solution for C using binary search but I think this approach is wrong and inconsistent with the problem If you agree Please someone hack the solutions that used this approach. If I am wrong please explain why this works?
•  » » 8 days ago, # ^ | ← Rev. 6 →   0 somehow, the code only checks the sums x/2, 3x/4, 7x/8, so on... (here, x=n*10^9) at most +-32 checks.[as the ki is small enough maybe after a certain range any value matches the condition]
•  » » 8 days ago, # ^ | ← Rev. 4 →   +8 check my code: I just checked sum 10^9 and it is AC. 264511010
 » 8 days ago, # | ← Rev. 2 →   0 simple o(n) solution of D :- https://codeforces.com/contest/1979/submission/264506463 BASIC BRUTEFORCE WITH SOME OPTIMISATION
 » 8 days ago, # |   0 Does anyone have a proof of why the hint for E is true?
•  » » 8 days ago, # ^ |   +3 First, draw the graph from $(x, y)$ to all the points which can be at distance $d$. It will look like a square rotated by $45°$. Now, if one of the point of our answer is one of the diagonal points $(x \pm d / 2, y \pm d / 2)$, then we are done (the condition satisfies). Now, after some observation on the graphs (and drawing pairs on the square which have distance d in them). You can notice that if none of the diagonal points are used then the other $2$ points are on the same side/line (there are $4$ sides of the square). And thus, the condition is again satisfied. (since if we take the square from any one of them, the other would be diagonal point).
 » 8 days ago, # | ← Rev. 3 →   +18 F is just mind blowing, very elegant and very nice : )
 » 8 days ago, # |   +3 Can someone explain the hint of E? Why/How is it true?
•  » » 8 days ago, # ^ |   +3 Assume on $x$ axis sides give projections of $n,m,n+m$. Then on $y$ axis we must have $d-n,d-m,d-n-m$. Two of them sum to the third, so $2d-2n-m=d-m$, so $n=\frac{d}{2}$, which is what we wanted.
•  » » 8 days ago, # ^ |   0 First, draw the graph from $(x, y)$ to all the points which can be at distance $d$. It will look like a square rotated by $45°$. Now, if one of the point of our answer is one of the diagonal points $(x \pm d / 2, y \pm d / 2)$, then we are done (the condition satisfies). Now, after some observation on the graphs (and drawing pairs on the square which have distance d in them). You can notice that if none of the diagonal points are used then the other $2$ points are on the same side/line (there are $4$ sides of the square). And thus, the condition is again satisfied. (since if we take the square from any one of them, the other would be diagonal point).
 » 8 days ago, # | ← Rev. 4 →   +9 Another approach in problem E, which reduces the amount of code to write: 264470284SolutionLet's observe that all the points on the distance d(in Manhattan metrics) from a fixed point make up a square with a diagonal of length 2d. With this knowledge we can rotate the plain by 45° and scale it, so that the sides of those squares are parallel to the axises and have integer lengths. After that the solution is easy: we have to find two points on a vertical or horizontal line, the distance between which is d. Let's call those points A and B. The third point has to lie on CD, where ABCD is a square.
 » 8 days ago, # |   0 Can anyone explain me problem D using bitmask
 » 8 days ago, # |   0 Really shameful, I couldn't solve anything after A
 » 8 days ago, # | ← Rev. 3 →   0 just checking sum=10^9 gives AC in problem C. Check my solution264511010
•  » » 8 days ago, # ^ |   +1 same lol that is what i did as well
 » 8 days ago, # | ← Rev. 2 →   0 Can anyone explain why for D in the following sample case 4 2 1110 the verdict is -1.Can't we take p = 1, the transformation would then be 1101 which is 2-proper as s1 = s2 = '1' and s1 != s3
•  » » 8 days ago, # ^ |   0 it not matching the k
•  » » » 8 days ago, # ^ |   0 Sorry, can you be more specific?
•  » » » » 8 days ago, # ^ |   0 For example, with k=3 , the strings 000, 111000111, and 111000 are k -proper, while the strings 000000, 001100, and 1110000 are not.
•  » » » » » 8 days ago, # ^ | ← Rev. 3 →   0 Do you mean that the second condition ${s_{i+k} \neq s_i}$ should hold for every ${i}$ in the range ${1 \le i \le n - k}$. But in the problem statement, it says the second condition should hold for any i in that range. iNNNo, if that's the case, shouldn't the second condition be ${s_{i+k} \neq s_i}$ for every ${i}$ (${1 \le i \le n - k}$)?
•  » » » » » » 8 days ago, # ^ |   +4 Bro read the problem again
•  » » » » » » » 7 days ago, # ^ |   0 I've read it many times, still I am not able to understand. Can you explain why 1101 is not 2-proper?
•  » » » » » » » » 7 days ago, # ^ | ← Rev. 2 →   0 1011i1=1i2=1i3= i1+k= 0i4= i2+k= 1you can see that i2=i4. so that it is not a k proper.2-proper: 110011, 1100, 0011, 001100.non-2-proper: 1001, 1101, 1011
•  » » » » » » » » » 7 days ago, # ^ | ← Rev. 2 →   0 Thank you Mamun01. I also got confused with the word 'any'.
•  » » » » » » » » » 7 days ago, # ^ | ← Rev. 2 →   0 Welcome, Bro..
 » 8 days ago, # |   0 264505361. My sol to B.
•  » » 7 days ago, # ^ | ← Rev. 3 →   0 What is the logic behind the code? What observation of yours lead to this solution? BTW I was not able to solve the B problem.
•  » » » 7 days ago, # ^ |   0 I just look into the examples and notice that the answer is the last bit of the difference and make sense to me, then I proof it by accepted.
 » 8 days ago, # | ← Rev. 5 →   +43 D can be solved with FFT:(note that polynomials are $0$-indexed while arrays are $1$-indexed and this is a somewhat overengineered solution)first the non-fft part: if a p is "ok", then first_k($a[p + 1; n] + rev(a[1; p])$) (i.e. the first k elements in the new array) must be equal;we can simply count it in an array $e$ with $e_i = \text{maximum number}$ s.t. $a[i; i + e_i]$ are all equalfor every i it must hold that $new_a[i] \ne new_a[i + k]$. this can be precomputed for all indices except for the indices in $[i - k; i)$ with $rev((p - k; p])$ (since $new_a = a_{p+1} a_{p+2} ... a_n a_p a_{p - 1} ...$, we need to check that $a_n \ne a_{p - k}, a_{n - 1} \ne a_{(p - k) - 1}$) Note that while the lhs is decreasing, the rhs is increasing.now we can use fft to check whether that conditions holds for all indices: Let $P_1 = c_1 * x^k + c_2 * x^{k + 1} * ... * c_n * x^{k + n}$ be a polynomial of degree $n + k$ and $P_2 = c_{n - k + 1} * x^0 + c_{n - k + 2} * x^1 + ... + c_n * x^k$ a polynomial of degree $k$.If we multiply both polynomials we get the following polynomial: $P_{res} = ... + (c_1 * c_{n - k + 1}) * x^k + (c_1 * c_{n - k + 2} + c_2 * c_{n - k + 1}) * x^{k + 1}$ $+ ... + (c_1 * c_n + c_2 * c_{n - 1} + c_3 * c_{n - 2} + ... + c_k * c_{n - k + 1}) * x^{2k}$ $+ ... + (c_{n - k + 1} * c_n + c_{n - k + 2} * c_{n - 1} + ... + c_n * c_{n - k + 1}) * x^{n + k} + ...$Each coefficient should represent "how different" $P_1$ and $P_2$ are (at that position), so we can choose $c_i = 1$ if $a_i = 1$, $c_i = -1$ otherwise. If we multiply two equal numbers, i.e. $1 * 1$ or $-1 * -1$, we both get the result $1$, while the result of two different numbers is $-1 * 1 = -1$. So a "more negative" result means a bigger difference in the strings. In the "middle" of the string ($k \le p \le n - k$), it is enough to check whether $[x^{k + i - 1}] P_{res} = -k$ ($[x^{k + i}]$ is the coefficient of $x^{k + i}$), since that means that all values in a are different.If e.g. $k = 2$ and $p = 2$, the resulting bitstring is: $a_3 a_4 a_5 ... a_n a_2 a_1$, i.e. we only need to check whether $a_n \ne a_1$. Luckily $P_1$ "starts with" $x^k$, i.e. $[x^k] P_{res}$ is $c_1 * c_n$, which is the check of "is $a_n \ne a_1$"; exactly what we need! So in that case we only have to check whether $[x^{k + i - 1}] P_{res} == i$But what about $p \in (n - k; n]$? Similar to the case where $p$ is small, we have to consider less than k values; e.g. for $p = n - 1, k = 2: a_n a_{n - 1} a_{n - 2} ....$Here we have to compare $a_n$ and $a_{n - 2}$, but $[x^{k + (n - 2) - 1}] P_{res} = c_{n - 2} * c_n + c_{n - 1} * c_{n - 1}$. Since we are now additionally comparing $a_{n - 1}$ and $a_n$ (and for other $p/k$ the last $k - (n - p)$ values are compared "within the array itself"), we have to "correct" this by "undoing" the fft ops (add $-1/+1$ depending on whether two of these duplicate comparisons match).With this information it is enough to iterate over all possible $p$ and check in $O(1)$ if all conditions hold. (we also have to exit early if we encounter some $a[p] \ne a[p - k]$ since some $p$ is only "ok" if all indices after it in the new sequence still "match" (and reversing $a_1 a_2 ... a_p$ doesn't really change that condition, so $a[p] \ne a[p - k]$ is enough)since fft runs in $O(n \log n)$ and the rest is $O(n)$ the total runtime is $O(n \log n)$Edit: Formatting
 » 8 days ago, # | ← Rev. 2 →   0 For problem C :I used Binary Search. I guessed total number of coins. For every mid, I go through all bets and calculated minimum coins are needed to be bet on i-th position. Then if total number of required coins is less or equal than my mid then it’s okay to bet that amount of coins.If no valid mid found then simply it’s impossible. Using this strategy, I calculated the minimum possible coins that satisfies the conditions. After that I distributed the coins for every i-th bet such a way that if I win i-th bet I get at least tootal coins. If some coins stays unused, then I distributed the remaining coins among all bets almost equilibrium way.Finally I checked wheather any position I bet more than 1e9 or not. If yes, then I said it’s impossible otherwise this is the answer. (I don't know is it required to check, it may not affect the solution but I remained in safety).I think this binary search approach is more easy to understand with less mathmatical calculation .My submission : 264454935
•  » » 8 days ago, # ^ |   0 I also used binary search during contest, but after it I came up with easier solution: https://codeforces.com/contest/1979/submission/264516424The main idea is that if it is solvable, then your overall coins should be maximized
•  » » » 8 days ago, # ^ |   0 Yes, It's more easy and simple solution
•  » » » 7 days ago, # ^ |   0 Can you explain the solution ??
•  » » » » 7 days ago, # ^ |   0 So, the observations I made: If you have x coins, then for each outcome you should bet (x / multiplier[i]) + 1 to have your winnings strictly greater than your initial coins. If the amount of coins you spent to create such an array is greater than your winnings, then it is not possible to win this game. So answer is -1. If it is possible to construct such an array with x coins, then it is also possible to do it with x+1 coins (because the multipliers make the winnings greater, not smaller). That is why binary search comes in handy. But the problem statement does not ask you to minimize the coins you have, so it is always convenient to make x big. So there is. A solution that always uses x as 10^9. Hope it was useful.
•  » » 7 days ago, # ^ |   0 No you are wrong For test case n = 2; k1 = 3 k2 = 3 sum = 2 and sum = 4 give valid answers but sum = 3 does not. Binary search approach may have worked but it wont work for all constraints. The optimal choice of sum is (LCM(k1,k2,k3 .....) — 1) if this is not a valid sum then sum does not exist. True for all constraints!!!
 » 8 days ago, # | ← Rev. 2 →   +3 D: Suppose we split s into a+b where a has p characters. Then, the end result is b+rev(a). I find it helpful to take note that if s is proper where k is a factor of n (in other words the string ends with a block of length k), then so rev(s), so we just need rev(b+rev(a))=a+rev(b) to be proper.
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 But how do you check if a + rev(b) is k proper or not in O(n) for every possible suffix b?
 » 8 days ago, # |   +19 Guessforces on problem B. The fourth test case was a huge giveaway when I saw it was a power of two.
•  » » 8 days ago, # ^ |   0 Samee
 » 8 days ago, # |   0 very good contest,adds me 200 points
 » 8 days ago, # |   0 if i changed "int" into "long long" in C, my solution will be accepted...still lack of experience :(
 » 8 days ago, # |   0 Can someone explain more intuitively why checking for 1e9 and lcm works in problem C?
•  » » 7 days ago, # ^ |   0 1e9 --> simply if this does not work for max number of coins then it will never work, Probability of the condition working increases with increase in number of coins as Multiplication function rises faster than addition.LCM --> just use basic algebra on ki*xi > Sum(xi), you eventually reach 1 > Sum(1/ki). Common thing between 1/ki and LCM is that in both cases you ignore common factors or take their frequency as 1.I can only explain both mathematically because I am used to doing everything this way, maybe writing it out will help you, write the equation down and use a rough graph in 1e9 case if you are comfortable with basic algebra and drawing rough graphs, hope this helps.
•  » » » 7 days ago, # ^ |   +3 Still the 1e9 condition does not guarantee that if there is a sum>=1e9 then there will always be a sum for numbers <1e9(let's consider the number to be x) for whom sum>x. There might be numbers<1e9 for which there exist a solution even though there does not exist a solution for 1e9.For example let's take {2,3,7} as the given array and let's take our value of x as 43. so for 43 the bet array will be{(43/2)+1,(43/3)+1,(43/7)+1}={22,15,7} and their sum is 22+15+7 which is greater than 43. So there exist no solution according to the 1e9 logic it means. But if we take 42 there exist an answer.So I think the testcases are so designed that this logic works but it will not work for more precise testcases I guess.
•  » » » » 6 days ago, # ^ | ← Rev. 3 →   0 but your k1*x1 does not match in case 1, 22*2 != 43, 15*3 != 43 and 7*7 != 43. Main condition of the problem is ki*xi > sum(xi). You assumed ki*xi to be 43 but your calculations show otherwise. The multiplication function increases much faster than addition, using 43 as a sample input is flawed checking, 1e9 is a much larger number than 43 and will be much larger than any xi unless ki == 1 in which case there is no solution. You need to think of a test case where your sum == ki*xi and ki*xi > sum(xi). forgoing one condition to prove another is not the right way. I used LCM btw and not 1e9 but I myself still cannot find anything wrong with 1e9 solution considering the given constraints. It would be great if you could point out the error in the math but as of your comment using sum = 43 is a mathematically incorrect example.
 » 8 days ago, # | ← Rev. 2 →   +6 I have some intuition for E I would like to share including one way you could have proved the hint. ExplanationLet's map our original coordinate system from $(x,y)$ to $(x+y,x-y)=(x',y')$. This makes the manhattan distance between two points $max(|x1'-x2'|,|y1'-y2'|)$. Where this idea comes fromThe idea of rotating coordinates this way is mentioned on page 73 of the competitive programmer's handbook which is where I got the idea from. There isn't an explanation to why it works, so I'll explain that here.One important insight about absolute values like $|x1-x2|$ is how you can decompose it into only two different possibilities $(x1-x2)$ or $(x2-x1)$. When determining the absolute value, all you simply need to do is take the maximum of the two possibilities. There are many problems where decomposing absolute values into their possibilities can help solve the problem. Using this insight you can try to solve 1859E - Maximum Monogonosity if you also know some dp.The Manhattan distance between any two points is $|x1-x2|+|y1-y2|$. Using the above statement, we can decompose $|x1-x2|$ and rewrite the statement as $max(x1-x2+|y1-y2|,x2-x1+|y1-y2|)$. If we do the same for $y$, we can see that to find the Manhattan distance we only need to choose the maximum of one of four options:$max(max(x1-x2+y1-y2,x1-x2+y2-y1),max(x2-x1+y1-y2,x2-x1+y2-y1))$If we rearrange the terms:$max(max((x1+y1)-(x2+y2),(x1-y1)-(x2-y2)),max((x2-y2)-(x1-y1),(x2+y2)-(x1+y1)))$And then swap which values get maxed together:$max(max((x1+y1)-(x2+y2),(x2+y2)-(x1+y1)),max((x1-y1)-(x2-y2),(x2-y2)-(x1-y1)))$We can now compose each inner max as an absolute value: $max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|)$This is sometimes a nice way to look at Manhattan distance because we can now process each dimension independently if we convert the points from $(x,y)$ to $(x+y,x-y)$.Based on this definition, when two points have a manhattan distance of d, that means that one of $|x1'-x2'|$ or $|y1'-y2'|$ equals $d$ and the other is less than or equal to $d$. For my insight, I like to think of the manhattan distance as "using" either the $x'$ distance or $y'$ distance, whichever is bigger.When looking at a manhattan triangle, at least one point in the triangle will either use $x'$ twice or use $y'$ twice when finding the distance with its neighbors. We can prove this by considering a triangle ABC. Let edge AB use $x'$. For A to not use $x'$ twice, edge AC must use $y'$. Once you've done this, however, there will be a vertex that either uses $x'$ twice or uses $y'$ twice no matter what dimension that we choose for our third edge BC.Let's fix point $(x1',y1')$ as a point in the triangle that uses the same dimension twice. Given the dimension used twice is the $x'$ dimension (the following holds for $y'$ too), we know that the following holds:$x2=x1+d$ or $x2=x1-d$and$x3=x1+d$ or $x3=x1-d$If we choose one point to have an $x'=x1'+d$ and the other to have an $x'=x1'-d$, that means that the $x'$ distance between points 2 and 3 will be at least $2*d$ which fails the triangle condition. This means that we have to choose $x2'$ and $x3'$ to both be $x1' + d$ or both be $x1' - d$. This therefore proves that $x2'=x3'$ which is incredibly useful.The hint suggests that there must exists two points such that $|x1-x2|=|y1-y2|$. In my proof I suggest that there must exist two points such that either $x1'=x2'$ or $y1'=y2'$. If I were to undo the transformation for my coordinates, my statement is: $x1+y1=x2+y2$ or $x1-y1=x2-y2$. We can transform my statement to $x1-x2=y1-y2$ or $x1-x2=-(y1-y2)$. This means that $x1-x2$ is either equal to or is the inverse of $y1-y2$. When you take the absolute value of both sides, the sign for both becomes positive and therefore they must be equal.$x2'=x3'$ clearly indicates $|x2'-x3'|=0$, so for there to be a valid Manhattan triangle we must use the other dimension $y'$ such that $|y2'-y3'|=d$. Let $y2$ be the smaller value of $y2$ and $y3$. To solve this problem from here, what I did is look at all possible values of $(x2',y2')$ and see if any point exists such that $x2'$=$x3'$ and $y2' + d = y3'$. With those two points, all you need to check is if there exists a point with $x1'$ equal to $x2'-d$ or $x2'+d$ such that $x'$ is the used dimension (i.e. the $y'$ distance of the original point is not greater than $d$ which is true iff $y2' <= y1' <= y3'$). Once we do this we can switch $x'$ and $y'$ and run the algo again for the case where point 1 uses $y'$ twice. Once I fixed a given point $(x2',y2')$, I was able to search for the other points using maps and binary searches which all took logarithmic time.You can see my solution here: 264520131
•  » » 7 days ago, # ^ |   +5 very very elegant explanation!
 » 8 days ago, # |   +3 Can someone explain C to me again? I mean, why the condition SUM(S/ki) < S ??
•  » » 7 days ago, # ^ |   +3 we have to find x1,x2,...,xn such thatx1 + x2 + ... + xn = Sx1*k1 > S -> x1 > S/k1x2*k2 > S -> x2 > S/k2....xn*kn > S -> xn > S/knthus S = x1 + x2 + ... + xn > S/k1 + S/k2 + ... + S/kn (or SUM(S/ki) < S)
 » 8 days ago, # |   +3 I guessed B and C. in B answer was 2^lowestbiton(a xor b) in C numbers just turned out to be lcmofwholearray/arr[i] (and if it does not work print-1 )
 » 8 days ago, # |   0 In the editorial of C, where is the mention of LCM? You just can't expect everything to be understood beforehand. Please try to write editorial in a proper way.
•  » » 7 days ago, # ^ |   0 Can you explain the editorial for C please ??
 » 8 days ago, # | ← Rev. 2 →   0 How I see problem E, is that if there is a Manhattan triangle, it can always be seen as having a first point $(x, y)$ and two other points having in a certain common relative direction to that first point — one of the two is on diag1, the other is on diag2 (just the segment, not the infinite line), and the two diagonals intersect at, WLOG, assuming the common direction is to the right, $(x+d, y)$. The image looks something like this:I actually managed to forget that without an anchor at either $(x + \frac{d}{2}, y + \frac{d}{2})$ or $(x + \frac{d}{2}, y - \frac{d}{2})$, the two on-diagonal points may not have the distance to each other at $d$. Silly me, this costed my chance for a quick jump to 1950-2000ish given that I solved ABCD absurdly quickly, and I AC'd E in like 3 minutes after figuring out the mistake. :(Well, another lesson to take anyway.
 » 8 days ago, # | ← Rev. 2 →   +3 Some $O(n^2)$ Solutions(264481866) passed problem D easily.Why $n \le 10^5$?
•  » » 8 days ago, # ^ |   +5 Hey, could u please share the O(n^2) solutions that u r stating? For some reasons, I can't open the link.
•  » » » 8 days ago, # ^ |   +3 Sorry, fixed.
•  » » 8 days ago, # ^ |   +11 Uphacked. ~1s solutions are the fastest ones I could hack, I guess.
•  » » » 7 days ago, # ^ |   0 Can you please hack my submission? I want to test my solution. Here's the link: link Thanks!
•  » » » » 7 days ago, # ^ |   0 Python solutions aren't hackable because $\mathcal{O}(n^2)$ solutions wouldn't have passed in the first place. I don't see anything in your code that would make it $\mathcal{O}(n^2)$ and the current time seems reasonable for a $O(n)$ solution with large constant of hashing and Python.Well, I tried and it only took 999 ms.
•  » » » » » 7 days ago, # ^ |   0 Thanks a lot! I used mod value as 2**64 -1 which made python use big int and hence it was little slow. Changing it to 10**9 + 7 (a 32 bit integer) made it significantly quicker. To be safe, I'll consider using double hash with 2 32 bit integer mod values in future.
 » 8 days ago, # |   0 I had solved C at the 25 minute mark and could not approach D for a long time. I was trying to find the first point where the string deviates from being k proper, coded it and just before I could submit,the contest ended. Some days you just can't win
•  » » 8 days ago, # ^ |   0 Nice copied code :0
•  » » » 8 days ago, # ^ |   0 Love how you project your insecurities on everyone around here.I am willing to prove how I coded it myself, contact me privately if you want more clarification
•  » » 7 days ago, # ^ |   0 Bro could you tell me how to figure our the solution for B? It seems so random to me
•  » » » 7 days ago, # ^ |   0 Just check how many bits in the binary representation of x and y are same from the right.To further explain it xor of a series of numbers would be same for both x and y values till the binary representation is same and when it differs the subsequence will not exist. I just checked if (x%2)==(y%2) and increased count. Then printed pow(2,cnt)
 » 8 days ago, # | ← Rev. 2 →   0 Could someone please explain how the condition given in solution of C is sufficient? We have not taken into account that the bet placed on any outcome needs to be an integer right?But if we do take that into account, the necessary and sufficient condition then looks like (sigma 1/ki)+(n/S) <= 1, where we don't know S.
•  » » 7 days ago, # ^ |   0 If the condition is met, you can always choose an S that is multiple of any of the k's by picking S = LCM(k_1, k_2, ... k_n). Thus any S/k_i will result in an integer making the equation trivial.
•  » » » 5 days ago, # ^ |   0 Thanks a lot.
 » 8 days ago, # |   +1 It was quite a nice contest! Altough it would've been better if some losers didnt cheat problem C. Very good contest!
 » 8 days ago, # |   0 Earning on bets detailed video editorialhttps://youtu.be/tipb5tYyHAQ?feature=shared
 » 8 days ago, # | ← Rev. 2 →   +11 F is a good problem, but there are a few issues in the solution!"at least (n−2) edges missing" should be "at most".$\dfrac{n(n - 1)}{2} - (n - 2) - (n - 1) - (n - 3) + 1$ should be $\dfrac{(n - 2)(n - 3)}{2} - (n - 4)$ (not $n - 3$), thus the invariant is keeped!
•  » » 8 days ago, # ^ |   0 Thanks!
•  » » » 5 days ago, # ^ |   0 in problem F, imagine the following case that 5 vertices have degree = n — 1. And when solving the problem recursively say we needed to query "? d" {d <= n — 3} and imagine no vertices have degree between [d , n — 2]. Clearly the answer to any such query will be the same as answer of "? n — 1" . How will we proceed in such a case , as we have no way to know which vertex had degree >=d ? {There will be uncertainty}
 » 7 days ago, # |   0 The problem C can be solved using a big number instead of LCM too. It was AC by my guess, without using LCM. A totally guessforces round!
 » 7 days ago, # |   +10 Guessforces!!
 » 7 days ago, # |   +6 can any one give me a proof about this fact from tutorialNote this fact: in every Manhattan triangle there are two points such that |x1−x2|=|y1−y2|.
 » 7 days ago, # |   +3 a lot of users solved B using: d = x ^ y ans = d & -d how does that work?
•  » » 7 days ago, # ^ |   +3 A computer sees negative numbers using the 2's complement method. Basically, it flips all the bits, then adds one to the result. For example:001 becomes 110, then 111 after adding one.You can observe that this operation preserves the state of all zeros until the first one, then flips all the other bits. Because of this, the result will have a shared one in the least significant bits only. If you perform a bitwise AND operation on these two numbers, you will get the least significant bit
•  » » 7 days ago, # ^ |   +3 d & -d computes the least significant (set) bit, i.e. the "right-most (least significant)" bit set to one. this is also used in fenwick trees: see here (wikipedia article)
 » 7 days ago, # |   +3 I did D by finding the first index( dentoed by j in my solution) where the string is not k-proper. Shifting it to the left if the condition in the last test case happens ( I am not able to explain it properly. Sorry for that.){In this test case -- 110001100110. I check if there are k 0's from j so that it forms a valid if I perform the operation.}But My solution is not working on 2010 test case in 2nd Test. I have hit a roadblock here. Can anybody help
 » 7 days ago, # | ← Rev. 2 →   0 For the C why the all possible winnings outcome must be the same. Is there any logic behind that assertion?Edit : got it, have not read well the editorial.
 » 7 days ago, # |   0 For problem C, I made a deadly mistake. The lcm of a and b equals a*b/gcd(a,b), so I think the lcm of a,b,c and d is a*b*c*d/gcd(a,b,c,d).In fact, it only works in two nums.e.g.: 4 5 8lcm: 40而 gcd(8,5,4) == 18*5*4 == 160[尴尬]
•  » » 6 days ago, # ^ |   +1 Even if it was correct, you can't store 20^50 and then divide it
•  » » » 6 days ago, # ^ |   0 Yeah..Thanks,I also make a mistake: 2^64 is not 1e64 ..hhI didn't AC this promblem is the reason.
 » 7 days ago, # |   0 In problem C, I get that if the coefficient for winning is k_i, we have to place more than S/k_i on this outcome. For each i=1 to n , this should hold...so summing should give the inequality ∑S/k_i< n* S But then how are we getting the inequality ∑S/k_i
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 1) S is the total amount placed on all bets. Since each bet is larger than S/k_i, summation of all bets is larger than summation of S/k_i, that is, S is larger than summation of S/k_i.2) LCM is not taken as total number of coins to bet, rather it is a value greater than total number of coins to bet. The return we get on any of the outcomes is equal to the LCM, and is thus greater than the total (enforced by the check ∑(1/k_i) < 1), hence this distribution of bets is an acceptable solution.
•  » » » 7 days ago, # ^ |   0 Thanks a lot.
 » 7 days ago, # | ← Rev. 3 →   0 solution for problem c with the binary search vl v; ll n; void in(){ cin>>n; v.resize(n); rep(i,0,n) cin>>v[i]; } vl ans ; ll getCondition(ll mid ){ ans.clear(); ll sum =0; rep(i,0,n){ ll val = mid / v[i]; ans.pb(val +1); sum+=(val +1); } if(sum > mid ) return 1; if(sum == mid) return 2; return 0; } void solve(){ in(); ll start=1, end = 1e9; ll valid =-1; while(start<=end){ ll mid = start + (end - start)/2; ll condition = getCondition(mid); if(condition==0){ valid =1; break; } else if(condition==1) { start = mid+1; } else end = mid-1; } if(valid==1){ for(auto ele: ans )cout<
 » 6 days ago, # | ← Rev. 2 →   0 -
 » 6 days ago, # |   0 For some reason, I guessed the solution for B and C and they were right! Here's how I did it:B: I noticed that the last testcase's answer is 33554432, which i remembered as a power of two (2^25), and so are the other testcases' answers. After this exploration, I tried to find how were the last testcase were related to 2^25, and finally found that the difference between x and y was divisible by 2^25, but not 2^26. So I concluded that the answer must be the largest power of two that is a divisor of abs(x — y). I then submitted the solution and got an AC. The entire process took 8 minutes.C: What had catched my attention was the really weird constraints on n and k. My immediate thought was that it was related to the answer of the problem not surpassing 1e9 (x limit) somehow. After that, I think it must be somehow related to the LCM of the array, and it was right, after me testing my theory on the example testcases. I submitted and got AC without proving that my solution was right.I did D afterwards, really enjoyed the problems, good contest!
•  » » 5 days ago, # ^ | ← Rev. 2 →   0 For me, B came after I decided not to give up and just keep trying until the end of the contest. I realized that both sequences would be 0 at some point, and at this point, we would continue increasing the index by 1 each time. So here, I just did 2^builtin_ctz(x^y) I would really like to know if I got any real benefit from this because I'm not sure. I mean, it took almost an hour of brainstorming, and I just want it to take 45 minutes the next time.
 » 6 days ago, # |   0 Hi all, I am new here on codeforces.I tried solving the last contest's (Div2 951) problems and was easily able to solve problem A, but I couldn't come up with a solution for problem B. Can anyone please help me understand the approach, as my mind was completely blank on what to do? What was your guys intuition behind the approach? I also couldn't understand the editorial's hint and solution. Your help would be much appreciated. Sorry, I'm not very good at Codeforces and am a beginner just trying to understand things.
 » 6 days ago, # |   +1 For people who did not understood editorial of problem C maybe this will helpEssentially what the editorial is this for Problem Clet coins we place in bet be c1,c2,c3,c4, ... ,cn and c1 + c2 + c3 +...+ cn = Sthen the following inequalities are formed based on conditions proposed by the question S
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 Perfect proof... first of all thanks for providing this.All the authors should learn from this proof that they should provide the detailed step by step proof in laymen language, that would be great for people who struggles to proof in their initial days!!
 » 6 days ago, # |   0 for C, I understood that 1>(1/a1+1/a2.....1/an) as the sum will cancel out from both sides undoubtedly and we have to just select the sum so that it yields an integer by every array element division hence it's the LCM. But can someone explain me what happens if one element of the array is LCM itself? It is clearly visible that it would be wrong but proof it if someone can please
 » 6 days ago, # | ← Rev. 4 →   +1 A short straight forward implementation using 2 pointers for D : 264776035 Logic : basically if you notice carefully then you will find that in the final string there should be alternate blocks of 0s and 1s of each of length 'k'. so the working is that whenever we find any block of len != k then we have to forcefully take p = this index(otherwise we always take p = n), then we create two prefix and suffix strings and check (suffix string + reverse of prefix string) to ensure that this will have alternate blocks of 0s and 1s simply otherwise p = -1 Don't forget to check first condition -> first k digits are same
 » 6 days ago, # |   0 Can someone please explain intuition and proof for hint of problem E? In every Manhattan triangle there are two points such that |x1-x2| = |y1-y2|`
 » 5 days ago, # |   0 For C, I think it's testing such a thing:In fact, for 1/k1 + 1/k2 + 1/k3 + ... + 1/kn, we need to unify the denominators when we sum them up, which means multiplying each k by a different number.For example:2 3 6: 1/2 + 1/3 + 1/6 = (3+2+1)/6 = 6/62 3 7: 1/2 + 1/3 + 1/7 = (21+14+6)/42 = 41/42Similarly, the numerators represent the amount of money allocated to each position, but the denominator is always greater than the total amount of money.
•  » » 5 days ago, # ^ |   0 21*2>41   ; 14*3>41  ;  6*7>41
•  » » 5 days ago, # ^ |   0 Testing: Whether the sum of fractions with numerators of 1 is greater than or equal to 1
 » 5 days ago, # |   0 I solved C using binary search here is my intuition let say a1,a2,a3,a4,a5,a6,a7....n are the multipliers given for each position in a sorted order and c1,c2,c3,c4,c5...cn are coins used by us at each position in an optimal way , now let say S is the total sum of coins used here. a1 is the minimum multiplier we have from this I observed that S < a1*c1 so S can be at max a1*c1 — 1 so I did binary search on c1 coins but here as we don't need to find the minimum possible coins and we just need to find whether it is possible or not I just continued my mid towards right end.please excuse me for my poor english and if my approach is wrong please let me know. My submission(264463858)
 » 5 days ago, # | ← Rev. 2 →   0 Thanks for Editorial very much! But can u see my code for C, i think it's also a good way for this problem: 264471661
 » 5 days ago, # |   0 in problem C code why z/k[i] and not k[i]/z ??
 » 4 days ago, # |   0 I just learnt from problem C after reading 20 different code and watching 3 youtube videos that if you encounter an array and math problem just randomly think about LCM and no intuition needed