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

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

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

1 | 1-gon | 208 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 21:21:10 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

The most brilliant solution to problem D must be the one with max-flow min-cut theorem in my opinion :)

oh, I think about using maxflow here. But I think it is hard to make network here. Moreover complexity of such solution would not pass in TL, am I right?

I think so!

well, in my opinion, just simple observation was required.

Since, we are given that frogs can jump on the distance of "L" , we can maintain the window of the size "L", and for this window, we can find the sum, wherever the sum is minimum , that is our answer. Because it will become bottleneck for all frogs. :) .

http://codeforces.com/contest/965/submission/37608075

This is link to my on contest solution. It took me less than 10 minutes to solve this D. it was way too much easier than normal D.

lol your solution is max-flow min-cut theorem.

hmmm, sorry about that. I don't know much algorithms. I don't know what I have implemented is maxflow or something else.

I just implemented with my

intuition. I will look into Maxflow algo.It's not the max-flow algorithm, it's just the idea of max-flow min-cut theorem. In your solution, you are using the fact that "max-flow is min-cut", where min-cut is the min(sum) of a length L. ;-)

Nice solution!

your remark only justifies that your output must be greater or equal to the real answer, since real answer cannot be greater than the bottleneck; but you give no proof that your output "IS" the real answer. Though, with some careful thought, you can actually prove this, or more specifically, you can easily construct a solution /scheme where the frogs with the same num of bottleneck can jump across the bank

A pretty late reply keeping in mind the contest happened 2 years ago, but I used a very similar logic, instead I maintained a dp, where dp[i] gives the max frogs ith place can hold which allows them to reach the riverbank, and then calculated minimum sliding window sum of length L over that dp.

I got an accepted verdict but clearly our logic is different (Feel free to correct me if I am wrong). Any thoughts on why this is working out?

AC submission:

https://codeforces.com/contest/965/submission/91799129

D can be solved with O(n) compexity. Imagine a graph where it is n * 2 vetices. From source you have edges to 1, 3 .. 2 * k — 1 vetices with capacity INF. From i'th vertice if i is odd you have edge to i + 1 vertice with capacity a[i]. From i'th vertice if i is even you have edges to i + 1, i + 3, i + 2 * k — 1 with capacity INF. if i is even and i / 2 >= n — k you have edge to sink (smth like that i can make little mistakes) And you can instead of building such a big graph and running max flow algorithm just try to find minimum cut. And after some greedy thoughts it is clear that you must choose segment [i, i + k — 1] with minimum sum of a[j] where j belongs to [i, i + k — 1]. It can be done with just a pair of loops in your code. See my implementation for details.

http://codeforces.com/contest/965/submission/37610259

Another (maybe easier) proof is that, if you imagine you know the solution with the

maximum number of frogsand simulate the process for sequentially with all the frogs, making sure that the left-est frog moves at all times, you can see that every time in this process the frogs will be in a contiguous segment of length at mostl. So the solution should be at most the minimum sum over alll-length segments. Once we found this upper bound, proving that it is the answer is straightforward.hello there,can you please tell me why must i choose continue segment? what if i Don't choose one of the continue edge? i think that this maybe a minimal cut ,too

when you take i'th vertice to first set ( by cut ) if i is even you need to take next k vertices with odd i to first set (otherwise you'll add INF edges to your cut) therefore it is clear that it must be k consecutive odd vertices which goes in first set when his connected even vertices goes in second set. And as it must be k consecutive a[i] you can just not add other a[i] to your cut.

I solved problem using fenwick tree, greedy approach. But I dont understand your solution. Why it is important if i is even or odd? How can that be important?

Can someone explain why my solution passed tests. I want to believe that complexity is but i can't proove it.

Shortly it is dynamic programming on tries.

dp_{v, x}=minsum. Wherevis number of vertice in tries.x— number of words that we didn't written in final set of prefix (it means that we will write it higher in tries — with smaller prefix).There I do stupid smth like knapsack on a tree.

dp_{v, x}=min(dp_{v, x},dp_{to, y}+dpprev_{z}for all y, z witch satisfies condition y + z == x. It is usual knapsack on a tree.So it should work in

O(n^{2}). But i added condition dp[v].size() = min(depth, cnt[v]) where cnt[v] — number of terminal vertices in subtree. And it gives states in dp because it is a trie. But there is also transitions and i've stuck here how to estimate number of transitions?This is implementation http://codeforces.com/contest/965/submission/37615468.

Can i solve problem div. 2 C using bisection method?

Is this logic correct?

For C, Bonus 1:

Same logic as given.

Just one change: to find xMax formula used earlier was: n / ( k * (i — 1) + 1 ), where i is the current D (in a for loop of D). (I did + 1 at-last to include Arkady as leftover use was not allowed). It should be less or equal to M.

Here, we just have to first check:

if(n % (k * (i — 1)) != 0) then Arkady will get leftover in last level and (n / (k * (i — 1)) in other levels. (Need to handle a case when value of n / (k * (i — 1)) exceeds M as it will be added to leftover and so on...)

else same as earlier.

If this is correct then can anybody tell me how to make it work for large values of D? (1 <= D <= n)

I don't think that works.

36 2 9 3

when d = 1 or 2 : impossible

when d = 3 : possible distributions = 6,7,8 , formula gives 6. best is 7.

For E, I had right idea but failed in implementing minimizing depth.

There is a much simpler, two pointer solution to D. Probably similar to the one bicsi gave.

The idea is to maintain a 0...w array 'reach' where reach[i] tells us the number of frogs that have reached the i'th unit at the i'th step. Note that reach[i] can't be greater than a[i], because we can't accommodate more frogs than the number of stones. We start by having infinite number of frogs having reached the 0th unit. For any i <= l, reach[i] = a[i]. This is because the frogs from 0th unit can directly jump till here.

The key insight here is that for any i > l, we should start letting the leftmost frogs who can reach i, jump till i. I.e first all frogs from the (i — l)th unit jump till i, then (i — (l-1))th and so on. We do this till either i'th unit's capacity is reached, or we've run out of frogs. You can use a pointer 'j' to track where the leftmost frogs are. Just make sure that j >= i — l. Answer is reach[n].

http://codeforces.com/contest/965/submission/37625008

Thanks. I found this easier to understand than the editorial.

You're welcome. To you, and anyone else interested, there's actually an even easier way of doing it (bicsi's one).

Let us take the unit

i = l. Let us assume for each uniti < j < w, a[j] = infinite. This means that every frog which has reached from(i — l + 1)th till (i — l)th unitcan cross the river.Now we want to find out for what values of

a[j], i < j < w, does the above condition still hold. As long as every l length segment fromj till w-1can storea[i — l + 1]...a[i]frogs, all the frogs can cross.Similarly you can determine that for

i > l, as long as everyllength segment from1 till jcan holda[i — l + 1]...a[i]frogs, all the frogs can reach(i — l + 1) till (i — l)th unit.So the solution should be the minimum sum over all

llength segments.I don't get why in C one doesn't need to compute min x for the iterated d like in the editorial. Computation of max x always works, but for me it seems that sometimes max x could make us take candies more than d times for the first person. Why is it never the case?

what's more confusing is that if for some

`d`

, if`max(x) > M`

then taking`x = M`

will always be valid for this`d`

!!! I really cannot account for this.37640931(should fail!)

37648582(probably correct)

the problem is whether n/(d*k-i)*d<=n/(d*k+1)*(d+1) when 0<=i<k-1

Hi! What is "smaller-to-larger optimization"? Does someone has a link to read about it?

Thanks

According to the code(http://codeforces.com/contest/965/submission/37617599), It just merge two sets by joining smaller one to larger one.

I believe this idea is commonly known as 'DSU on tree', you can read more about it here

Thanks! I'm going to read about it

Does a binary search solution works for C ?

how can i solve C's bonus 2 part?

did you find the solution for bonus 2 part?

my solution is stuck to test case 5

38625147 ~~~~~ int main(){ ll n,k,m,d; cin>>n>>k>>m>>d; ll result=m*(((n/m)+k-1)/k); while(true){ ll t= (n/m)%k; t++; ll h = ((n/m)*m)/(n/m+t); if(h>0&&d>=((n/h)+k-1)/k){ m=h; if(result<m*(((n/m)+k-1)/k)) result=m*(((n/m)+k-1)/k); } else break; //cout<<"i m here\n"; } //cout<<"i m out side\n"; cout<<result<<endl; return 0; } ~~~~~

Anyone else solved D with BIT?

i did http://codeforces.com/contest/965/submission/37911989

can someone please explain E!

Firstly,we build a trie tree for all names.Now,the total length of these original names is the total depth of all names.

As we go from the bottom to the top of the trie tree,if a node doesn't contain a name, it is obviously to place the name which is deepest(longest name) to current node,this case is optimal.

And after we go to the top of the trie, the ans will be the total depth of the trie

Can anyone help me in understanding the solution of E given in the editorial . how calc funtion is working ? thanks in advance

Haha, this problem is also solvable via DP. Let dp[i] — the max number of frogs that can get up to distance i. We calculate dp[i] based on values of dp[i — l]...dp[i — 1], only we delete dp[i] frogs from the dp array starting from index i — l, not to count duplicate frogs. This TLs on test #16, so I simply keep track of the current sum dp[i — l]...dp[i — 1] in a variable, which runs in ~200 ms.

Code: https://codeforces.com/contest/965/submission/46261137

Editorial to https://codeforces.com/contest/965/problem/C is one of the most arrogant ones I ever did read on codeforces.

Wow, so many solutions to problem D. Here is yet another one :P

I do a DP on a greedy. I break the entire $$$w$$$ length into $$$w/l$$$ segments of length $$$l$$$ each. And for each segment, I try to fill up this segment in the rightmost way, greedily. This can be done by DP.

88428808