Блог пользователя BledDest

Автор BledDest, история, 7 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Educational Codeforces Round 28
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Another nice idea for solving D can be — link .

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain B more explicitly?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thank you!

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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
            
            
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

can someone please explain problem C !

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Elaborate it please..

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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[k] = 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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        why Answer for current i is the maximum in A

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I meant A[k] = sum[0, k) — sum[k, i]. Now we want to find answer for current i. Ans[i] = max(sum[0, k) — sum[k, i]) <=> Ans[i] = max(A[k]).

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кто может объяснить F-ку более явно.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E's trick in Input constraints! Missed it.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Different approach for F. For each unique value ai in the array find the probability that a random choice for l and r will contain at least one ai. To do this assuming we have all the positions of ai stored we can find the probability of the interval not containing ai by summing each of the probabilities of both l and r being in each of the disjoint intervals not containing ai, which is just the length of the interval squared divided by n2 and subtracting this from 1.

Finally by the linearity of expectation the answer is the sum of these probabilities over all distinct values in the array.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

That moment when you solve Div 2 A with DP!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

we can find max size subwindow with dp. dp[i][j] = dp[i][j] * (min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j])+1) dp[i][j] — right-bottom corner of the window