fcspartakm's blog

Codeforces Round #592 (Div. 2) Tutorial
By fcspartakm, history, 5 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +37
  • Vote: I do not like it

Comments Comments (42)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

First of all thanks for the tutorial,

But I can't get problem C, I don't understand why looping from 0 to w will guarantee finding a solution(if it exist)

I got this observation " The crucial observation is that d wins give us the same amount of points as w draws. Let's use them to solve a problem where we want to minimize the total amount of wins and draws giving p points (if it is not greater than n, we can just lose all other matches) " but I can't understand the rest.

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

    Let x be # of wins, y be # of draws, z be # of losses.

    We need to prove that if there is a solution where y >= w, there will be a solution where y < w.

    When y >= w, we exchange w draws with d wins. The total points remains the same (from the observation), and we do not overshoot the limit as x'+y' = (x+d)+(y-w) = x+y-w+d < x+y <= n. Thus this will also be a solution.

    So if we keep exchanging w draws for d wins, we will eventually end up with a solution where y < w and we cannot exchange further.

    Now that it is proven, we can say that if a solution exists, a solution will exist where y < w. Similarly if there are no solutions where y < w, there are no solutions.

    Thus, we search y from 0 to w-1 to find a solution, and if we cannot then there is no solution.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      If you want to input $$$\geq$$$,you can just input:


      $$$\geq$$$

      (only one $)

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

      I am still not able to understand how did you proved that if there does not exists solution for y<w then there will no solution.

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

        Since we proved that if a solution exists, a solution will exist where y < w, it is equivalent to saying that if there is no solution where y < w, a solution does not exist. (This is the contrapositive of the first statement)

        Proof: Assume otherwise: there is no solution where y < w but there is at least one where y >= w. However, we can say that will be a solution with y' = y-w, since (w draws = d wins + w-d losses) in terms of points. We can then also say that there is a solution where y' = y-2w, and so on until we have a solution such that y' < w.

        Hope this helps.

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

      why can't we do the same for x instead of y?

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

        This is because it is optimal to have less draws and more wins, but not the other way round. Wins give you more points than draws.

        So we can constrain the number of draws, but not the number of wins, as the number of wins can be as large as n (10^12).

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

    I don't know if it would still be relevant for you but I solved this problem completely as an abstract number theory problem: Given non-negative integers $$$n, p, w, d$$$, find non-negative $$$x, y, and$$$ $$$z$$$ satisfying $$$x⋅w+y⋅d=p$$$ $$$x+y+z=n$$$ with $$$w>d$$$. Now, express $$$p$$$ and $$$w$$$ as $$$k_1*d+c_1$$$ and $$$k_2*d+c_2$$$. This means $$$y=k_1-x*k_2+(c_1-x*c_2)/d$$$. Now again express $$$x$$$ in terms of $$$d$$$ as, say, $$$k_3*d+c_3$$$. Now you can iterate over all possible $$$c_3$$$ from $$$0$$$ to $$$d-1$$$ and find the maximum $$$k_3$$$ such that $$$y$$$ is still non-negative: This is true because it turns out that $$$x+y$$$ decreases with increasing $$$k_3$$$, so we have more options for $$$d$$$ (greedy approach).

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -44 Vote: I do not like it

solution of problem E(translated by google translate)

The only mid-range question in this competition.

Obviously greedy.

Sort the series first.

To make the minimum value in a series +1, you need to +1 each of the minimum values in the series; to make the maximum value of -1 in the series, you need to have a maximum of -1 for each of the series. ——mangoyang's comment on XJOI (not this question)

Now let's categorize the discussion:

  • If the remaining number of operations is sufficient: compare the smaller values of the difference between the left and the right, select a smaller operation

  • If the number of remaining operations is not enough, select an operation with fewer numbers on both sides.

In a total of four cases, the code is a bit annoying, be patient

In addition, if the number of times is stable, it will output 0 directly.

code:

62540846

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

    I think you should put all the codes in a spoiler. That will reduce the size of the comments.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -45 Vote: I do not like it

      It is sorry that I don't know how to use spoiler,so i use link.

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

    I'm not really able to see why E is greedy.

    Suppose k was 20 and we have the following frequency table

    1 -> 16 2 -> 1 3 -> 1 4 -> 1 5 -> 50 6 -> 10 7 -> 10

    Wouldn't greedily first reducing 7 and then reducing 6 be worse than increasing 1, 2, 3 and 4

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it -38 Vote: I do not like it

      Because my English is not very well,I don't quite get your question.

      greedy means "choose the less cost one that can influence to the answer"

      In fact,you can see the example 1:


      4 5
3 1 7 5

      reducing 7:1 3 5 6

      reducing 6:1 3 5 5

      increase 1:2 3 5 5

      increase 2:3 3 5 5

      then,whatever you do,the $$$Maxnum-Minnum=2$$$

      so the answer is 2

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

      You will decrease or increase whichever group of numbers in top or bot that have less quantity (just compare top and bottom groups).

      10<16 so go from top: "1 -> 16 2 -> 1 3 -> 1 4 -> 1 5 -> 50 6 -> 20" now 16<20 so go from bot but because 16>k (k is 10 now) we can't do anything and program terminates.

      Python code: 62526246

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

    I tried something similar during the contest but failed. My idea was to compare which side was cheaper, but it did not work. Can somebody point out what is wrong with this logic?

    62484346

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

      you should first compare which cost less,then compare $$$k$$$ is enough or not.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -36 Vote: I do not like it

solution of problem G(translated by google translate)

This is one of the four best questions (ABDG) that can be done in this competition.

Simple construction

Since the output order is independent of the correctness of the answer, we assume that one of the two sequences of the output is in the order from $$$1$$$ to $$$n$$$.

We find a property: the sum that can be made by the permutation is $$$[\sum_{i=1}^n i,\sum_{i=1}^n max(i,n-i+1)]$$$

So the output of $$$<\sum_{i=1}^n i$$$ $$$-1$$$, $$$\geq \sum_{i=1}^n max(i,n-i+1)$$$ is a fake example 2 output

Now the range of $$$k$$$ becomes $$$[\sum_{i=1}^n i,\sum_{i=1}^n max(i,n-i+1))$$$

Construction method:

Set the current unfilled interval to $$$[L,R]$$$, and fill in $$$R$$$ if $$$\leq k$$$ after $$$R$$$ is filled in, otherwise fill in $$$L$$$

code:

62537353

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -21 Vote: I do not like it

solution of problem F(translated by google translate) a bit late,sorry!

The harder one of the two questions (CF) in the competition

We found a property: if the consecutive $$$k(k \geq 2)$$$ colors are the same, then their color will not change.

Then, it will only change type like $$$\dots BWBWBW \dots$$$.

Every time you change, the left and right ends will become the final color, and the other middle will become a different color($$$B \rightarrow W,W \rightarrow B$$$).

Then we can simulate directly.

The time complexity of the simulation is $$$O(min(n,k))$$$

why?

For each operation (time complexity is $$$O(1)$$$), it must change the value of two characters, and each character changes at least once.

Code:

62554014

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The greedy for E:

The idea is to sort the array, and start with the initial maximum difference, and try decreasing it while we have operations left.
We need only 1 operation to decrement answer by one, if we increment the leftmost number. We can keep incrementing it until it becomes equal to the next number. After that, we need 2 operations (increment both of them) to decrement answer by one, and so on.
The same is symmetrical for the right side too.
So, we greedily move towards center from both ends together, minimizing the answer at each step.
62586395

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

    I had come up with something similar, and it seemed to work on whatever examples I could find, but I can't prove correctness. Could you prove intuition on how I would go about proving this is always optimal? Thank you.

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

      Look at it like this,

      1) let's agree that it's always your best choice to either increase the minimum number or decrease the maximum number since those are what bring you your result.

      2) does it matter if you choose to increase the minimum by one or decrease the maximum by one ?

      • the answer is No since both will make the final answer decrease by one

      3) so now we're at the point where we must choose to either increase the minimum or decrease the maximum what will be my greedy choice is the number or occurrence of each

      say we have 5 5 7 8 9 9 9 9

      If we choose to increase the minimum we will need 2 moves to decrease the final answer by 1 ( 1 for each 5 )

      If we choose to decrease the maximum we will need 4 moves to decrease the final answer by 1 ( 1 for each 9 )

      hence it's always optimal to choose the once with the minimum number of occurrence

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

    is this a usual way to code or something?

    like after taking examples i understood why your code works

    but did u think of this approach? how this performs on an array like 1 2 3 16 25 36 (say k = 5) is very interesting(for me)...

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

      This type of approach often occurs in similar type of problems.
      You generally learn these by coming across similar problems and looking at different approaches of top competitors, who usually solve it in simpler way.

      Also, the linked submission is of practice, it probably wasn't the first approach that came to my mind.

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

    I'm trying to figure out how your solution works. If you are going to be sharing a code at least make it readable and name variables meaningfully, been trying to understand what the "p" variable is doing for 30 min.

    I'd appreciate it if you could explain it further or resubmit something better for explanation purposes.

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

      It will be easier to think of the case when all integers in array $$$a$$$ are distinct and sorted. $$$p$$$ is tracking the count of $$$min(a)$$$ (or $$$max(a)$$$, both are same after our each step) present in $$$a$$$. Initially $$$p$$$ is 1, and $$$ans$$$ is $$$max(a)-min(a)$$$.

      On first step, we calculate the ops we need to take to increase $$$a_0$$$ to $$$a_1$$$ and decrease $$$a_{n-1}$$$ to $$$a_{n-2}$$$. This will be $$$take = (a_1 - a_0) * p + (a_{n-1} - a_{n-2}) * p$$$. (Also make sure this isn't more than than remaining ops $$$k$$$). Doing these ops will decrease the $$$ans$$$ by $$$\lfloor \frac{take}{p} \rfloor$$$.

      On next step, the new minimum is equal to $$$a_1$$$, max is $$$a_{n-2}$$$ and $$$p$$$ is 2. Now increasing the $$$min(a)$$$ by 1 (or decreasing $$$max(a)$$$ by 1) takes $$$p=2$$$ ops. We increase the min till $$$a_2$$$ and decrease the max till $$$a_{n-3}$$$, and repeat with $$$p = 3$$$ and so one until all elements are equal (when we reach the mid of $$$a$$$) or we run out of ops.

      Now this same approach works with duplicates in $$$a$$$ without loss of generality. (sorry for the bad code :p).

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain me how to solve Problem C using Linear Diophantine Equations.I read this Comment but his ans is not clear to.

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

    From extended gcd we get (x0, y0) such that ax0 + by0 = g = gcd(a, b). We then scale this to satisfy ax + by = p; x = (p/g)x0; y = (p/g)y0

    We can now shift our obtained solution to (x + kb', y - ka') where a' = a/g and b' = b/g [you can verify this]

    Now we have 3 inequalities:

    • x >= 0 or k >= -x/b'
    • y >= 0 or y/a' >= k
    • x + y <= n or k >= (x + y - n)/(a' - b')

    Just pick a k which satisfies all the inequalities or return -1.

    ---
    Keep in mind that scaling will lead to an overflow in cpp. We can overcome this using the fact that there's a solution with y < w' from the editorial.

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

Can someone please take a look at my code for problem D. I can't figure out why is giving runtime error. 62637783 or wa

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new in trees. How can we implement D? Please help.

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

    if you are using c++ then tree/undirected acyclic graph can be represented as array of vectors. if tree contains n nodes represent it as vectorvec[n+1]. to make the n-1 connections in the tree number=n-1; while(number--) { ll int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } for more basic info refer to hackerearth theory section regarding graph.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial for F?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, " The crucial observation is that d wins give us the same amount of points as w draws" i didn't get this. Can someone please explain?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

has anyone implemented problem D with the second approach told in the tutorial?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem E's editorial, can someone explain the 2nd para with an example ?

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

    consider sample:

    10 12
1 2 3 6 7 8 9 13 14 15

    2nd paragraph tells you that if there is answer that reach $$$(min, max) = (4, 12) = (L, R)$$$ then there are same amount of numbers that you need to increase, so there are also answers $$$(3, 11)$$$ and $$$(5, 13)$$$ but among them are those with $$$L$$$ or $$$R$$$ from input array. Now, other sample:

    9 11
1 2 6 7 8 9 13 14 15

    Think of $$$(L, R) = (4, 12)$$$ again. It require $$$5+6 = 11$$$ to make it. It's not optimal because there are two numbers that we increase, and three that we decrease, so we can move $$$L$$$ and $$$R$$$ up by one to $$$(L+1, R+1) = (5, 13)$$$, so each decreasing number will need one step less, and each increasing number will need one step greater. So, total difference will be $$$\# L - \#R$$$, where $$$\#L$$$ is number of increasing numbers, and $$$\#R$$$ is number of decreasing numbers. And, because $$$\#L < \#R$$$ this difference is negative, so result will be better. It was requiring 11 and $$$\#L - \#R = 2 - 3$$$ so it will require $$$10$$$. By anology, if $$$\#L > \#R$$$ you can change to $$$(L-1, R-1)$$$.

    And... of course in this case $$$(4, 12)$$$ is not answer, because this is reason why answer must have one of bounds if amount of increasing and decreasing numbers are not equal. If they equal, then answer may have bounds from initial array or not, but there is always answer that has $$$L$$$ or $$$R$$$ from initial array.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C can be solved in O(1) time the best lower bound for y is (y = ((p / g) % (w / g) * modInverse(d / g, w / g)) % (w / g)). Just check for this (y) if there is a suitable non negative x satisfying the bound (x + y <= n) and (x * w + y * d = p)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DP solution for D : https://codeforces.net/contest/1244/submission/62501364

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

Solution for Problem C :
Given: $$$w.x + d.y =p $$$ (eqn 1) and $$$x+y+z= n$$$
Also we know $$$x>=0$$$ , $$$y>=0$$$ and $$$z>=0$$$ .
Let $$$x + y = k$$$ (eqn 2) where $$$k=n-z $$$ and as $$$z>=0 , $$$ $$$k<=n$$$
Next we multiply eqn 2 with $$$w$$$ to form eqn 3.
Solving eqn3 and eqn1 for x and y, we obtain x to be $$$\dfrac{p - d.k}{w - d}$$$ and y to be $$$\dfrac{w.k - p}{w - d}$$$.
We put in the newly found values of $$$x$$$ and $$$y$$$ in $$$x>=0$$$ and $$$y>=0$$$ to obtain $$$k>=\dfrac{p}{w}$$$ and $$$k<=\dfrac{p}{d}$$$
Thus we iterate k from $$$\dfrac{p}{w}$$$ to $$$\min(\dfrac{p}{d},n)$$$
Code Link
![ ](88a04e71-45ca-4e45-a0b1-99301c415da6.jpg)

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

    Ingenious! I was looking for such a solution for a long time, thanks! Btw, could you please explain why you're checking p%__gcd(w,d)==0 why if this is false, then the solution doesn't exist?

    I made two submissions, the first one was this -without this p%__gcd(w,d)==0 condition, got TLE

    the second one was this -with this p%__gcd(w,d)==0 condition, got AC

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

      The simplest linear Diophantine equation takes the form ax + by = c, where a, b and c are given integers.
      This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b.
      Source link

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

    Thank you very much. It was really helpful

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pls lowering rating on E

→ Reply