iNNNo's blog

Codeforces Round 951 (Div. 2) Editorial
By iNNNo, history, 3 weeks ago, translation, In English

Thank you for participating!

1979A - Guess the Maximum

Solution
Code

1979B - XOR Sequences

Hint
Solution
Code

1979C - Earning on Bets

Hint
Solution
Code

1979D - Fixing a Binary String

Solution
Code

1979E - Manhattan Triangle

Hint
Solution
Code

1979F - Kostyanych's Theorem

Solution
Code
  • Vote: I like it
  • +74
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -47 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    U really want to help such cunts ?

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      i know its useless but still i want them to know their place.

      → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      check my solution,you will get it

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 = 3

        clearly 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

        → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

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

        → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      .

      → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think binary search is the correct approach. It might have worked due to numerous values of sum satisfying the condition.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I really struggle with binary search problems, how to identify it in specific, can you help me some resources

    → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    check my code: I just checked sum 10^9 and it is AC. 264511010

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    So many downvotes,did I offend the cheater community here.

    → Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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<<endl;

void solve(){
    int n;
    cin>>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
}
    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah i wrote the same code

      → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is no such thing as shortcuts, LOL! AC is AC, and clever AC is even better.

        → Reply
    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I came up with the exact same implementation but it doesn't work for some reason, keeps giving me WA verdict on the 341st case of pretest 2. But glad to see that I had the right idea.

      → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ya, solved using binary search only

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 weeks ago, # |
  Vote: I like it +89 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thanks! Found it to be more intuitive than the posted solution

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes i also thought of same solution, but poor implimentation skills mine

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh i get it, thanks, should have read the problem better

        → Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

finally became green

→ Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's up was this problem copied from somewhere??

    → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +79 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    This is very cool! What did you use to make the animation?

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      I used the processing.js library on Khan Academy's coding environment with the following code.

      Rendering Code

      Then I recorded screen and exported as gif.

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    you're either doing practice with too hard or too easy problems, try changing the difficulty and solve problems on multiple platforms other than codeforces

    However, improvement takes a long time to see and you should not give up

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if i am bouncing between, 1200-1300,what should be the ideal rating to solve?

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/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?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    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]

    → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    check my code: I just checked sum 10^9 and it is AC. 264511010

    → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    10 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. The hint's observation is equivalent to the fact that 2 points are on the same diagonal.
    2. Prove by contradiction: Take (x1, y1) and (x2, y2), s.t. distance equals to d and they are not on the same diagonal. The set of all points that are d units away forms a 45°rotated square. Now imagine all points that are exactly d units away from first point — set S1, or the second point — set S2. The third point is one of the points that are in both S1 and S2 (intersection of S1 and S2). But this third point is on the side, that is intersecting either first point, or second point. Thus, it is surely on the same diagonal.
    → Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. The hint's observation is equivalent to the fact that 2 points are on the same diagonal.
    2. Prove by contradiction: Take (x1, y1) and (x2, y2), s.t. distance equals to d and they are not on the same diagonal. The set of all points that are d units away forms a 45°rotated square. Now imagine all points that are exactly d units away from first point — set S1, or the second point — set S2. The third point is one of the points that are in both S1 and S2 (intersection of S1 and S2). But this third point is on the side, that is intersecting either first point, or second point. Thus, it is surely on the same diagonal.
    → Reply
»
3 weeks ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me problem D using bitmask

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really shameful, I couldn't solve anything after A

→ Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

Check my solution
→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it not matching the k

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, can you be more specific?

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For example, with k=3 , the strings 000, 111000111, and 111000 are k -proper, while the strings 000000, 001100, and 1110000 are not.

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            Bro read the problem again

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I've read it many times, still I am not able to understand. Can you explain why 1101 is not 2-proper?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                1011

                i1=1

                i2=1

                i3= i1+k= 0

                i4= i2+k= 1

                you 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

                → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

264505361. My sol to B.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 weeks ago, # |
← Rev. 5   Vote: I like it +43 Vote: I do not like it

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:

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

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

Edit: Formatting

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also used binary search during contest, but after it I came up with easier solution: https://codeforces.com/contest/1979/submission/264516424

    The main idea is that if it is solvable, then your overall coins should be maximized

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, It's more easy and simple solution

      → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the solution ??

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!!!

    → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    But how do you check if a + rev(b) is k proper or not in O(n) for every possible suffix b?

    → Reply
»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

very good contest,adds me 200 points

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

Explanation
→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    we have to find x1,x2,...,xn such that

    x1 + x2 + ... + xn = S

    x1*k1 > S -> x1 > S/k1

    x2*k2 > S -> x2 > S/k2

    ....

    xn*kn > S -> xn > S/kn

    thus S = x1 + x2 + ... + xn > S/k1 + S/k2 + ... + S/kn (or SUM(S/ki) < S)

    → Reply
»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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 )

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the editorial for C please ??

    → Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hey, could u please share the O(n^2) solutions that u r stating? For some reasons, I can't open the link.

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Uphacked. ~1s solutions are the fastest ones I could hack, I guess.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please hack my submission? I want to test my solution. Here's the link: link Thanks!

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice copied code :0

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro could you tell me how to figure our the solution for B? It seems so random to me

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Earning on bets detailed video editorial

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

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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!

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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}

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Guessforces!!

→ Reply
»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

a lot of users solved B using:

d = x ^ y
ans = d & -d

how does that work?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

    → Reply
»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same problem!! Do you have solved it? I can't find where the mistake is.

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My expert frnd just said my approach is incorrect

      → Reply
      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        But why (ToT) How can we find some counterexample

        → Reply
      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I have been accepted!! Look at this→ https://codeforces.com/contest/1979/submission/266091447 It's in python

        → Reply
        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nice!

          I am trying to understand ur code. Can you tell what mistake u found? Was your code also getting stuck at 2010th testcase?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            After the change, my code looks like this: judge the length of each substring that consists of all 1s or 0s, and if it's less than k, then cut it at the end; if it's equal to k, then judge the next substring; if it's greater than k, then cut it at the k positions before the end, and then finally judge whether the changed string is compliant or not. In fact, it looks like I only added some breaks to my previous code.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks, I also made a silly error. Got it now.

              → Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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[尴尬]

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Even if it was correct, you can't store 20^50 and then divide it

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah..Thanks,I also make a mistake: 2^64 is not 1e64 ..hh

      I didn't AC this promblem is the reason.

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
2 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

-

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!!

    → Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice. finally understood. thank you

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 weeks ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

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
→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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|

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. The hint's observation is equivalent to the fact that 2 points are on the same diagonal.
    2. Prove by contradiction: Take (x1, y1) and (x2, y2), s.t. distance equals to d and they are not on the same diagonal. The set of all points that are d units away forms a 45°rotated square. Now imagine all points that are exactly d units away from first point — set S1, or the second point — set S2. The third point is one of the points that are in both S1 and S2 (intersection of S1 and S2). But this third point is on the side, that is intersecting either first point, or second point. Thus, it is surely on the same diagonal.
    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    21*2>41   ; 14*3>41  ;  6*7>41 

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Testing: Whether the sum of fractions with numerators of 1 is greater than or equal to 1

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

ok

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In D there may be such case: s = "1011", p = 4 As I understood the string will be: "1101", this means that the length of the last block will reduce, which contradicts first statement in the author's solution. Somebody tell me, where I made a mistake?

→ Reply