I'm not a racist, but just because of your color :D

So , people don't like dynamic scoring??
Every new thing is hated in the beginning :p

add me, i am blocked

Why only experts??? O_O

Iam sure you are the winner :P

yes

Sadly Codeforces system seems not working properly as my submission gives wrong ans before starting evaluation :(

Disagree -1 XD
It's so clear to me. But I can't solve problems. I'm a noob :(

It's dynamic programming. DP[current second][last speed]. But I spent a lot of time on understanding the statement.

V increasing while we can decrease V to Vlast

print(sum(min(v1 + d * i, v2 + d * (t - i - 1)) for i in range(t)))
increase our speed as fast as we can. Also with decreasing
(can't code without brackets highlighting :( and forget we need sum it, not print :( )

This problem can be solved without using dynammic programming .. just traverse first from left to right and then right to left maintain minimum of both side at each second . sum them up :)

if v1 + (t-1)*d <= v2, we know the best way is to increase the velocity by d every second. Otherwise, the speed would first increase to a top speed, let's say Vmax, then decrease to v2. We can enumerate the top speed Vmax to find the answer.

maintain 2 arrays of size t.

first has first element as v1 and contain maximum speed that can be attained at any time by increasing previous element by d.

second have last element as v2 and contain maximum speed that can is possible at any time by increasing later element by d.

example- if v1=10 and v2=30, t=5 and d=4

array1- 10 14 18 22 26 array2- 14 18 22 26 30

add elements from array1 to answer untill array1[i]<=array2[i], then add elements from array2.

int main(){ int v1,v2; cin >> v1 >> v2; int t,d; cin >> t; cin >> d; int ans=0;

while(t--){
    ans+=v1;
    v1=min(v1+d,v2+((t-1)*d));
}
cout << ans << endl;
return 0;

}

i did it without dp.... simply take a array 'A' of size t; A[1]=v1; A[t]=v2;

for<- 2 to t-1 A[i]+=d;

and traverse from back and check if abs(A[i]-A[i+1]>d) make abs exactly d...by changing A[i];

then add all A[i];

You can solve it by 2 pointers..

Bipartite matching !!

My kind of brute-force algorithm couldn't pass pretest 9 but I think the idea is correct.

Store the people in an array of vector, where vector v[i] stores people shaking hands with i people, initialise current index of all vector to 0.

Now start from 0, if current index of v[0] is less than v[0].size(), it means there is a person that can enter now.add this person to solution vector, increment 0 to 1 and repeat.

If, current index becomes >= v[i].size(), then check for current index that are possible, eg. for i=7, other states possible are 7-3=4, 4-3=1 and so on.If you cant find any valid state that has current index < v[i].size(), break out of loop.

Edit: The idea is correct.It passed the system test after removing a stupid bug.

We only need to simulate the whole thing. But, we postpone groupings as late as possible.

Let's say there is X ungrouped people and next one comes. First check if there is exists (remain) a person who shake hands with X people. If yes, allow him to shake hands with X people and add 1 to current no of ungrouped people.

If not, form a group and try again, no of hand shakes becomes X = X - 3. Repeat if necessary. If ultimately not possible because there is not enough people to form groups anymore, output Impossible.

D solution:

Simple greedy: take the largest numbers first, e.g. 0 1 2 3 4 5 6 7, 5 6, 2 3 4, 0 1 2.

I solved with greedy :D

200000 stack

Your A must be define as a long long... I have hacked 9 people like you :)

You have declared sum as int, but if I give you 200000 times 1000000 as d? Then the power goes to 11. Thanks. :)

Ответ: нет.

P.S. Не стоит жадничать на константы от которых не сильно изменяется время работы программы, но при этом может упасть решение.

X + Y — Y would always result in X even if overflow occurs.

As you can see in case 50 the answers are equal to the input.

10685565
я думал ну совсем все знают что делать...

В решении с ТЛ ты удаляешь из начала вектора. erase() работает за O(N).

Это же решение только будем удалять из конца вектора, а не из начала.

У меня в решении по E достаточно было изменить 3 на 4 и WA68 превратилось в AC.

UPD: Хотя то что решение заходит при 4 — это из-за слабых тестов. Моё решение бы упало при N = 200000, M < N / 2, и более менее нормальных остальных значениях.

Вокруг есть добрые люди, которые могут объяснить задачу по лучше всякого разбора, если их вежливо об этом попросить.

you used std::lower_bound, which has linear complexity
use set::lower_bound and you get AC: 10685831

use s.lower_bound(x) instead of lower_bound(s.begin(), s.end(), x)

This have been discussed many many many times in Codeforces

I have a TLE on system tests, but I used 3 smaller multimaps(each element only in one multimap, depending on shakes[i]%3 and I cycled between them) and used insert, lower_bound ( s.lower_bound) , erase, empty operations. What could go wrong? Isn`t is supposed to be N*log N solution? Or is it not good enough? http://mirror.codeforces.com/contest/534/submission/10675989

When calculating DP you are setting your initial ret value to be 0. However, your recursive call can return you negative infinity, because there is no solution. Since you update ret to be a max of a previous ret value i+get(...), you lose that information. So for a state that doesn't lead anywhere, you will return 0, which is wrong. As a result, when the correct solution is 1+2+3+4+5+6+5+3+2+1, your program can do 1+2+3+4+5+6+7+8+9+0 (10 can't reach 1, so we use 0).

Change line 50 from ret=0LL; to ret=-inf; and you'll get an AC :)

Good luck!

As far as I can tell you just need to switch to faster i/o methods.

Scanner.nextInt and Scanner.nextLong() is REALLY slow. You should use Integer.parseInt(sc.next()) and Long.parseLong(sc.next()).
If it is not sufficient, you must implement method to parse integer.

Because 6>5, as it says.

А как ее вообще решать?

Я написал какой-то перебор с запоминанием и тупыми отсечениями (если уже поставили слишком много/мало групп, выходим) и получил TL. Неужто выпиливание векторов правда все ускорит?

You remove elements from the beginning of it. In ArrayList I guess it's O(n) so total complexity is O(n²). Remove last element and it will pass

Adjacent elements should differ by at least two, so if you enumerate first the odd numbers and then the even numbers you have a correct solution. For example, n = 5: 1 3 5 2 4

This algorithm doesn't work when n < 5. In these cases, solve it on paper and hardcode into your source.

Probably you would do better if you think the problem in two cases: + when all the other dices do their best + when all the other dices do their worst (summing 1 each)

this give you a range of points you need on the a_i dice you are working on (once at a time), and of course tells you the amount of points (or faces on the dice) that you will never see to accomplish A points.

Hope this helps http://mirror.codeforces.com/contest/534/submission/10679438

you did the same job as others! but your time complexity is O(log(n)) and other's is O(1)

:D

You are right, but the task wants you to output maximum possible value, and your 23 is certainly less than correct 26.

Notice that in a given row there can be maximum of 10 blocks (because we have at most 20 columns, and each block must be separated from next and previous block by at least one free cell). Also notice that we can encode any tiling by m integers as bitmasks (so that 0-th bit of every integer gives us the first row, 1-st bit gives second row, and so on) up to 2⁵.

Given that, let's do dynamic programming: dp[num_placed][r1][r2][r3][r4][r5][last] = true or false. It means, that we've already filled num_placed leftmost columns, and we must build r1 more blocks in first row, r2 more blocks in second row, ..., r5 more blocks in the fifth row; and last is the bitmask of last placed column. Let's estimate number of states: 21 * 11⁵ * 32 = 10⁸. Not all possible states are reachable.

Instead of doing dp, I've made a backtracking, because it effectively visits all reachable states, with memoization it is done only once, and with some heuristics (for example, if we must place 5 blocks in some row and there are only 3 columns left, we can say 'goodbye' to this state immediately) it works even faster.

But if you prefer dp approach, the main observation here is to encode [r1][r2][r3][r4][r5] as a single integer in numeral system base 11 (because each r_i have possible values from 0 to 10), that makes coding more convenient.

1st dice cannot show 3 by definition: d₁ = 2, so it can only show 1 or 2 (but not 3, 4, 5 or any greater value).

What was this word "Tutorial"?

Let's hope that the author haven't posted it yet because he wants to make it more understandable and detailed :)

No, it isn't a correct order because if 2 shakes hands with 0 guys, then 7 will shake hands with 1 guy instead of 4 guys :)

No, it is impossible. If 4 handshakes with nobody, then 5 could not handshakes with 4 people. "At any time any three students could join together and start participating in a team contest, which lasted until the end of the day. " "so when another student came in and greeted those who were present, he did not shake hands with the members of the contest writing team." You assume the 1 2 3 formed a team so 4 handshakes with nobody then 5 can only handshakes with 4. So it is impossible. Sorry for my bad English

If the 4th person shook hands with 0 people, how could the 5th person shake hands with 4 people?

The answer is indeed Impossible.

А по-моему, это хорошая идея. Стоит лишь заметить, что тип точки (начальная/конечная) не так важен. Пусть все такие 'волшебные' точки будут начальными, остается перебрать лишь направление движения на старте.

Теперь нужно всего лишь написать функцию, которая проверяет совпадает ли путь для заданной стартовой вершины и направления с путем, указанным во входных данных. Эта функция также может попутно считать длину пути. Вышеуказанную функцию можно реализовать за O(N).

Остается лишь заметить, что 'волшебных' точек лишь O(1).

First,You should count a[i]. a[i] is the number of students who shook hands i times. We define cur .cur is the number of student who we can shake hands with now. In the beginning cur=0.

1. if a[cur] > 0 , it tells us we can add a student who will shake hands cur times in the permutation.And than a[cur]--(because we use a person)

2. else cur-=3 (3 student start writing a contest) until (cur<3 or a[cur]>0)..

　　　2.1 if (a[cur]>0) is same as 1.

　　　2.2 cur < 3 it means the sought order of students doesn't exist.

My english is very poor. You can see my code 10681578..I hope you can deal with it!

10734329