Разбор Educational Codeforces Round 28

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

Автор BledDest, история, 9 лет назад, По-русски

Tutorial is loading...

Разбор задач Educational Codeforces Round 28

BledDest
9 лет назад
27

Комментарии (22)

Показать архивные | Написать комментарий?

greedy_me

9 лет назад, скрыть # |

← Rev. 2 →

Another nice idea for solving D can be — link .

→ Ответить

Momentum

9 лет назад, скрыть # |

← Rev. 2 →

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

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

→ Ответить

Momentum

9 лет назад, скрыть # ^ |

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

→ Ответить

Hossam

9 лет назад, скрыть # |

Can someone explain B more explicitly?

→ Ответить

ebaalhuis

9 лет назад, скрыть # ^ |

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.

→ Ответить

CaptainDaVinci

9 лет назад, скрыть # ^ |

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.

→ Ответить

ebaalhuis

9 лет назад, скрыть # ^ |

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

→ Ответить

CaptainDaVinci

9 лет назад, скрыть # ^ |

Thank you!

→ Ответить

Paul_Guderian

9 лет назад, скрыть # ^ |

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

→ Ответить

subham301477845

9 лет назад, скрыть # |

can someone please explain problem C !

→ Ответить

Flyce

9 лет назад, скрыть # |

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

→ Ответить

mishi_gun

9 лет назад, скрыть # ^ |

Elaborate it please..

→ Ответить

Flyce

9 лет назад, скрыть # ^ |

← Rev. 2 →

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.

→ Ответить

JayZhan

8 лет назад, скрыть # ^ |

why Answer for current i is the maximum in A

→ Ответить

Flyce

8 лет назад, скрыть # ^ |

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

→ Ответить

unbelievable02

9 лет назад, скрыть # |

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

→ Ответить

ankeshgupta007

9 лет назад, скрыть # |

E's trick in Input constraints! Missed it.

→ Ответить

usernameson

8 лет назад, скрыть # |

Different approach for F. For each unique value a_i in the array find the probability that a random choice for l and r will contain at least one a_i. To do this assuming we have all the positions of a_i stored we can find the probability of the interval not containing a_i by summing each of the probabilities of both l and r being in each of the disjoint intervals not containing a_i, which is just the length of the interval squared divided by n² 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.

→ Ответить

Anish1712

6 лет назад, скрыть # ^ |

Can you please explain to me why is the output for

n = 2 and a={2,2} is 1.000000

→ Ответить

usernameson

6 лет назад, скрыть # ^ |

{2,2} has one unique element in the the array. All segments contain 1 unique element.

→ Ответить

shubhiks1032

8 лет назад, скрыть # |

That moment when you solve Div 2 A with DP!

→ Ответить

Your_Bunny_Wrote

4 года назад, скрыть # |

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

→ Ответить