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.

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.

finally became green

justice for 6k rank for doing 3 problems in div2:(

Visual for 1979E

Animation 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

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

https://codeforces.net/contest/1979/submission/264505456

Hey 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?

simple o(n) solution of D :- https://codeforces.net/contest/1979/submission/264506463 BASIC BRUTEFORCE WITH SOME OPTIMISATION

also c sol:- https://codeforces.net/contest/1979/submission/264445819

Does anyone have a proof of why the hint for E is true?

F is just mind blowing, very elegant and very nice : )

Can someone explain the hint of E? Why/How is it true?

Another approach in problem E, which reduces the amount of code to write: 264470284

Solution

Let'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.

can anyone explain D using bitmask ??

Can anyone explain me problem D using bitmask

Really shameful, I couldn't solve anything after A

C number can be solved by just checking sum=10^9. check my solution: 264511010

just checking sum=10^9 gives AC in problem C.

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

264505361. My sol to B.

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 equal

for 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:

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)$$$

Proof by AC: https://codeforces.net/contest/1979/submission/264505623

Edit: Formatting

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

E: https://usaco.org/current/data/sol_triangles_platinum_feb20.html

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.

Guessforces on problem B. The fourth test case was a huge giveaway when I saw it was a power of two.

very good contest,adds me 200 points

if i changed "int" into "long long" in C, my solution will be accepted...still lack of experience :(

if i changed "int" into "long long" in C, my solution will be accepted...still lack of experience :(

Can someone explain more intuitively why checking for 1e9 and lcm works in problem C?

I have some intuition for E I would like to share including one way you could have proved the hint.

Can someone explain C to me again? I mean, why the condition SUM(S/ki) < S ??

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 )

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.

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.

Some $$$O(n^2)$$$ Solutions(264481866) passed problem D easily.

Why $$$n \le 10^5$$$?

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

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.

It was quite a nice contest! Altough it would've been better if some losers didnt cheat problem C. Very good contest!

Earning on bets detailed video editorial

https://youtu.be/tipb5tYyHAQ?feature=shared

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!

Если что есть конвертор c++ в Perl или Python

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!

Guessforces!!

can any one give me a proof about this fact from tutorial

Note this fact: in every Manhattan triangle there are two points such that |x1−x2|=|y1−y2|.

a lot of users solved B using:

d = x ^ y
ans = d & -d

how does that work?

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

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.

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 8

lcm: 40

而 gcd(8,5,4) == 1

8*5*4 == 160[尴尬]

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<S ?

Also, what's the logic behind taking lcm as the total no of coins to bet?

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<<ele<<" ";
        nl;
    }
    else cout<<valid<<nline;
}

-

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!

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.

For people who did not understood editorial of problem C maybe this will help

Essentially what the editorial is this for Problem C

let coins we place in bet be c1,c2,c3,c4, ... ,cn and c1 + c2 + c3 +...+ cn = S

then the following inequalities are formed based on conditions proposed by the question

S<c1*k1
S<c2*k2
S<c3*k3
.
.
.
S<cn*kn

divide by k on both sides

S/k1<c1
S/k2<c2
S/k3<c3
.
.
.
S/kn<cn

add them all up the ineqality still holds

S*(1/k1 + 1/k2 + 1/k3 + ... + 1/kn)  <  c1+c2+c3+c4+ .... + cn

S*(1/k1 + 1/k2 + 1/k3 + ... + 1/kn)  < S

(1/k1 + 1/k2 + 1/k3 + ... + 1/kn)  <  1

fraction addition

let lcm = lcm(k1,k2,k3,...,kn) then (lcm/k1 + lcm/k2 + lcm/k3 + ... + lcm/kn) / lcm < 1

multiply by lcm on both sides

(lcm/k1 + lcm/k2 + lcm/k3 + ... + lcm/kn) < lcm

and this is your final condition for answer

please correct me if my calculations are wrong

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

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

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|

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/6

2 3 7: 1/2 + 1/3 + 1/7 = (21+14+6)/42 = 41/42

Similarly, the numerators represent the amount of money allocated to each position, but the denominator is always greater than the total amount of money.

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)

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

in problem C code why z/k[i] and not k[i]/z ??

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