BledDest's blog

By BledDest, history, 2 months 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  
  • +24
  • Vote: I do not like it  

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

Is the round rated?

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

Another nice idea for solving D can be — link .

»
2 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, the size of the array wasn't enough.

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

Can someone explain B more explicitly?

  • »
    »
    2 months 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 months 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 months 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 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you!

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

            Maybe O(n2) can solve this problem instead of n2k...

            #include<stdio.h>
            #define S(x,y) (x^=y^=x^=y)
            #define go(i,a,b) for(int i=a;i<=b;i++)
            int n,k,a[50];long long Time,sum,Score,ans,m;
            int main()
            {
            	scanf("%d%d%d",&n,&k,&m);
            	go(i,1,k)scanf("%d",a+i),sum+=a[i];
            	go(i,1,k)go(j,i,k)if(a[i]>a[j])S(a[i],a[j]);
            	
            	go(i,0,n){Score=(k+1)*i;if((Time=sum*i)>m)break;
            	go(j,1,k)Time+(n-i)*a[j]>=m?Score+=(m-Time)/a[j],j=k:(Time+=(n-i)*a[j],Score+=n-i);
            		Score>ans?ans=Score:1;}printf("%I64d\n",ans);return 0;
            }//Paul_Guderian
            
            
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please elaborate the logic for Problem A.

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

can someone please explain problem C !

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

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

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

    Elaborate it please..

    • »
      »
      »
      2 months 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.

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

E's trick in Input constraints! Missed it.