BledDest's blog

By BledDest, history, 2 weeks ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

»
2 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Is the round rated?

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

Another nice idea for solving D can be — link .

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

Can someone tell me why I get wrong answer here in problem D?

http://codeforces.com/contest/846/submission/30118738

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

Can someone explain B more explicitly?

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

    Suppose you know how many tasks you are solving completely, say i. This costs you i times the sum of costs over all subtasks, and gives you i*(k+1) points.

    For the remaining time, you are not solving complete tasks. How can you do separate subtasks most efficiently? They all give 1 point, so greedily keep solving the lowest time cost one until you have not enough time left.

    So try every possible number for i and take the maximum.

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

      Why not solve maximum number of tasks completely and then solve the remaining tasks greedily till we run out of time? I tried doing this, but didn't work.

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

        For example input: 10 2 10 1 9

        In this case you can solve 10 times subtask 1 (10 points) which is better than doing maximum number of tasks completely; that would be solving a single task completely (2 + 1 = 3 points).

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

Please elaborate the logic for Problem A.

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

can someone please explain problem C !

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

Problem C can be solved in linear time. Solution O(n).

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

    Elaborate it please..

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

      First let's solve subtask: Given an array of length N, for each 0 <= i < n we need to find k such that sum[0, k) — sum[k, i] = max.

      Assume we store array A, where A[j] = sum[0, k) — sum[k, i]. Answer for current i is the maximum in A. Now we want to update it for i + 1. To do this reduce all A[0 <= j <= i] by x[i + 1], A[i + 1] = abs(sum[0, i + 1]). So we can use dp, because maximum answer for i + 1 is maximum of (ans[i] — x[i + 1]) and abs(sum[0, i + 1]).

      Then iterate with c through array. It divides into two intervals: [0, c), [c, n). You need to find k1 and k2 such that (sum[0, k1) — sum[k1, c)) + (sum[c, k2) — sum[k2, n)) is maximum. We can use previously calculated dp because this two ranges are independent.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

E's trick in Input constraints! Missed it.