Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 186 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #592 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/22/2021 22:22:08 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

(only one $)

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.

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.

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

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

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

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

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

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

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

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:

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

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

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

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

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

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

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

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.

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 ?

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

here I used the same but got out of memory...then TLE after removing one vector https://codeforces.com/contest/1244/submission/77981716

Rahul's approach seems good, his solution makes use of difference array

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

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.

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

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:

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.

How is the solution gauranteed to have minimum cost?? Problem D

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

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

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.

Thank you very much

Editorial for F?

What is s in the Staircase problem?

fcspartakm editorial for f ?

Why L or R must belong to the same array. Can someone explain it in more detail.

How'd you go about implementing D?

Assume you've initially marked the last edge of the input with 2 colors, how do you find which vertex to run the DFS on? Anyone got their solution they could link me to? Would be p cool

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?xw + yd = p, x=d,y=w.

I have a very peculiar doubt in question C.

I got the part "_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 why are we comparing y ans w to get the solution?

In problem C, if i am doing the same thing for x =0 to d-1 then why it is giving WA? It should be correct ?

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

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

consider sample:

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:

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.

Thank you so much..! I got it now.

Why approach is wrong? https://codeforces.com/contest/1244/submission/68103624

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)

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

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

![ ]()

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 TLEthe second one was this -with this

`p%__gcd(w,d)==0`

condition, got ACThe 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 ifc is a multiple of the greatest common divisor of a and b.Source link

Thank you very much. It was really helpful