KAN's blog

By KAN, 4 months ago, translation, In English,
Tutorial is loading...

37617481

Tutorial is loading...

37617515

Tutorial is loading...

37617552

Tutorial is loading...

37617576

Tutorial is loading...

37617599

 
 
 
 
  • Vote: I like it  
  • +75
  • Vote: I do not like it  

»
4 months ago, # |
Rev. 3   Vote: I like it +60 Vote: I do not like it

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

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

    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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Nice solution!

»
4 months ago, # |
  Vote: I like it +38 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    Another (maybe easier) proof is that, if you imagine you know the solution with the maximum number of frogs and 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 most l. So the solution should be at most the minimum sum over all l-length segments. Once we found this upper bound, proving that it is the answer is straightforward.

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

    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

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

      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.

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

    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?

»
4 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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. dpv, x = minsum. Where v is 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. dpv, x = min(dpv, x, dpto, y + dpprevz for all y, z witch satisfies condition y + z == x. It is usual knapsack on a tree.
So it should work in O(n2). 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

    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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

There is a much simpler, two pointer solution to D. Probably similar to the one retrograd 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

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

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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      Let us take the unit i = l. Let us assume for each unit i < j < w, a[j] = infinite. This means that every frog which has reached from (i — l + 1)th till (i — l)th unit can 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 from j till w-1 can store a[i — l + 1]...a[i] frogs, all the frogs can cross.

      Similarly you can determine that for i > l, as long as every l length segment from 1 till j can hold a[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 l length segments.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it +10 Vote: I do not like it

    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)

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

Thanks

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Does a binary search solution works for C ?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how can i solve C's bonus 2 part?

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

    did you find the solution for bonus 2 part?

    my solution is stuck to test case 5

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

      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; } ~~~~~

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else solved D with BIT?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain E!

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

    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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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