Hello, Codeforces!

I'd like to invite you to Codeforces Round #298 (Div. 2). It will be held on Sunday, April 12 at 19:00 MSK and Div. 1 participants are invited to join out of competition.

Problems have been prepared by Maxim Mescheryakov (Neon) and Danil Sagunov (danilka.pro). We hope you'll find them interesting.

Great thanks to Maxim Akhmedov (Zlobober) for helping us preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon systems and ideas of some problems. Also thanks Vitaliy Aksenov (Aksenov239) for writing solutions.

You will be given six problems and two and the half hours to solve them.

**UPD:** Scoring system 500-1000-1500-2000-2500-3000

**UPD2:** Competition completed! Thank you all!

**UPD3:** Congratulations to the winners!

**UPD4:** Editorial here

Why minus ? When I wrote this comment, scoring system wasn't announced. Also there wasn't even a " scoring system will be announced later " message

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

Scoring system will be announced later :/

It should be Dynamic Scoring :)

So , people don't like dynamic scoring??

Every new thing is hated in the beginning :p

Ok,you are right

OK. I don't have any thing to say.

Ok

:) Good luck

add me, i am blocked

Nothing

don't mind me : http://codeforces.com/blog/entry/16607

I think it will be a good contest wish succes for every EXPERT

Why only experts??? O_O

They want it ...

XD

i hope you all know who is going to win this round!

Iam sure you are the winner :P

Specialist Let's Muster...

So is there a dynamic scoring system or not? Does this mean that if I submit a 2000 point system even almost at end of contest, I get 2000 points if its accepted?

I hope to participate in Round #299 with (div.1) :)

six problems.Time duration 2.5 hours.

Coding Time

yes

There is some issue.. i m always getting wa on pretest 1.. i checked my ans

i m sorry.. it is my mistake.

GLHF guys :)

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

i m sorry,, it is my mistake

The statments was very dificult to understand. problems are good but it takes very large time to understand a problem. Agree : +1 Disagree : -1

Disagree -1 XD

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

I will see you soon.......

Every body, Ehsan.poursaeed wants that you give me -1 and give him +1. see his conspiracy. Don't give him +1. but if you like give me -1

The pretest #15 of problem E doesn't have the visited stop list sorted. This costs me 45 minutes :( Was any one affected by this?

I liked the problems :)

How to solve second problem?

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

You don't need the dynamic programming. You just need to run from zero to t and update the speed using greedy approach. Check out my solution.

Exactly. You just need to always increase the speed until it's possible to get to the required final speed in the remaining time.

V increasing while we can decrease V to Vlast

I think this idea in contest,but can't implement.How to implement?

You can see my submission. I used exact this idea :)

`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;

}

bayram98 could you please explain the logic used in the code ?

you only need know how far is your v2:

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];

thnx, can you give correctness proof?

You can solve it by 2 pointers..

arr[0] = v1; arr[t — 1] = v2; int s = 0, e = t — 1; for (int i = 0; i < t-2; i++) { if (arr[s] <= arr[e]) { arr[s + 1] = arr[s] + d; s++; } else { arr[e — 1] = arr[e] + d; e--; } } ll ans = 0; for (int i = 0; i < t; i++) ans += arr[i];

How to solve D? I think that I got the idea but I had 4 unsuccessful attempts. I know that we have to change the remainders in order 0-1-2-0-1-2-0-1-2-... but maybe I implemented it wrong.

how to solve problem D handshakes ?

Bipartite matching !!

can you please explain the idea ?

let's suppose the entering position are from 0 to n-1...

since a team of 3 can be formed, so in general student with 'i' handshakes can go at positions i,i+3,i+6,i+9... (because additional 3's can form a team resulting in 'i' handshakes).. (make edges correspondingly to form bipartite) so Now the question reduces to bipartite maching of n students with n positions.. :)

Building the graph seems to work in O(N^2) at least for me. Am I missing something?

Yeah, even bipartite matching takes O((n^2)*sqrt(n)) hence ,I think this one will get tle...

I only used DFS for this :) but didn't managed to fix it during the contest

http://codeforces.com/contest/534/submission/10685298

take into account we don't need some of the structures declared... because I changed my mind during the coding and forgot to delete them

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.Umm i seem to getting a TLE on #72. Encountered such a problem? Have a look at my post

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`

.Ditto approach. I seem to be getting TLE on #72. Could you have a look at my post at the bottom?

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.

Ok, How is about 0 1 2 3, 0 1 2 ?

Oh, I understand. You try to increase number of people at first.

I solved with greedy :D

200000 stack

If in Problem 'A' n=4 testcase was not included in pretests, no. of hacks could be more!!

I see several people, including me, failed on system test 50 for problem C. Any idea what it may have been?

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

Ah, seriously. I changed it to int when I uploaded it, since I thought it wasn't necessary and might have slown down the solution.

but there written n,A <= 2·10^5, in test 50 A is 99964566758, am I misunderstand something?

n≤A≤s, not 2 × 10^{5}I have changed all variables to long long, except n, A((. thanks

I think A is not necessary to take as long long, rather sum in his case. Thanks. :)

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

I have done 4 problems and in my view, the difficulty level was C,D,A,B. Problem B just ruined my contest. -_- However, I have enjoyed the problem D very much. Thanks to the Almighty, thanks to the problem setters, thanks to all. :)

Can somebody explain why http://codeforces.com/contest/534/submission/10677423 submission passed test case no 50. The coder in the above solution has used int type for all the values and is still successfully dealing with large inputs. HOW? Costed me a unsuccessful hacking attempt.

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.

Nice problem set can't wait to see tutorial of D

Is something with std::set solution wrong or just mine is incorrect (why?)? I got TLE on test #46 ;-; http://codeforces.com/contest/534/submission/10685572

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

Thank you so much :)

Could you refer me a blog where this has been discussed?

I've seen this discussion couple of times on similar situation: some guys ask why his solution fail, another reply that

`lower_bound(s.begin(), s.end(), x)`

has linear complexity. But it's hard to find comments, so I can't give you links.I couldn't find anything on google search as well.Maybe we can formalise it here. So what it means is that lower_bound(), upper_bound() have linear complexity(I highly doubt that) but s.lower_bound(x) has O(logn). But I have passed programs having O(n*logn) with n<=10^6 using lower_bound().If lower_bound() is linear then complexity would have been O(n^2) (impossible to pass).Is this valid for set only or is it true for vector, array also?Is its complexity based on array configuration or what?

And one more thing, as far as I know c++ stl is highly optimised. So how come lower_bound() is linear, because I sure can implement this in O(logn)?

I'm pretty sure

`lower_bound()`

isO(log) for vector and array (but of course it is assumed that the vector/array is sorted).The thing with

`lower_bound()`

on`set`

is that, you do not have random access inO(1), so probably it was implemented in a way that makes itO(N). I think it is stupid design of this C++ STL that allows people to use the library wrongly like that.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://codeforces.com/contest/534/submission/10675989You gave link to another solution.

For your D, it looks like good, but it gets TL on N=113 which is weird. I ran your solution locally and it spits error in free(). I guess it's because you access myit while lower_bound can return a.end() (so myit does not point to an element) and then you erase myit -> undefined behaviour. Very strange it gets TL on CF...

Add check myit != a.end() and I hope it will pass.

Thank you. Changing one of "Impossible" conditions from (a.empty()) to (myit == a.end()) helped. It was my first time using map, I will watch out for it in future.

فارسی زبونا همیات کنین

Why this solution gives WA for problem-B? Plz, help me--> 10682655

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!

D:Different teams could start writing contest at different times. the number of student -3 or -3*t(t=1.2...) it take me long time to understand the problem

Where can I find the rules for the scoring? Thanks in advance.

Thanks for the problems. It was a great contest with very nice problems.

Can someone explain why my code for C TLEd? http://codeforces.com/contest/534/submission/10682828 Shouldn't it be O(n)? Or do you need to somehow print more efficiently?

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.

For problem

A — Examwhy is the following output wrong for input 6?6 Output 5 2 4 1 3 6 Answer 6 5 3 1 6 4 2 Checker Log wrong answer Jury has better result: 6>5

Because 6>5, as it says.

Found the mistake. And it's silly!

When will the editorial be published?

Is there a problem with submitting? Why can't I submit now?

Edit: It is fix.

I seem to be getting TLE on case #72 of problem D: Handshakes. I am using a Hashmap<Integer, ArrayList> which stores the keys as hand shakes and indexes of people in the arraylist. Code runs perfectly. Its based on the same idea as @_spartan has written. Any optimizations?

Edit: As hellman1908 suggested, the complexity increases. So i changes the ArrayList to a Stack since the order does not matter and VOILA, AC :D

http://codeforces.com/contest/534/submission/10687311

You remove elements from the beginning of it. In ArrayList I guess it's

O(n) so total complexity isO(n^{2}). Remove last element and it will passBetter Still, I'll try with a stack ;)

AC with stack :D Thanks for the hint!!

http://codeforces.com/contest/534/submission/10687565

Is there any editorial links for the contest? sorry if I missed one thanks :)

How to solve Problem 'A'?

What is Logic behind it?

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.

Thanks

it is actually works n < 5 except the fourth :)

n = 2 (1, 2), n = 3 (1, 3, 2) does not work also.

My accepted solution for Problem — 'C' used binary search: http://codeforces.com/contest/534/submission/10684361. As far as I can see, no one else had used binary search to solve this problem. I am not able to digest this. What obvious thing am I missing?

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://codeforces.com/contest/534/submission/10679438

I applied exactly the same concept as you are mentioning, if you look into my code, it's doing the same thing — finding minVals for all dices and then maxVals for all dices.

To get those minVals (and maxVals), I have used binary search (and you are saying that the minVals would simply be 1 for each die). Can there not be a case when the minVal for a die be more than 1? (I could not come up with a proof that there cannot be such a case. If someone has any, then please let me know.) To be certain of the correct answer, I used binary search to get the minimum values for each die and then the maximum values..

think about this example

1 8 9

I hope I am getting your point, but if you are asking for a counter example where the lower value a dice MUST have this is the easiest case, obviously your lower value is 8, so your upper value, giving you 8-8+1 possible valid dice' faces (thus 9-valid = 8 not used faces).

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

:D

Great round, I like how many variants people wrote to solve problem D, really creative.

In case of Problem-B it is given "the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d."

and this also " Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value "

so for first case is it also possible that speed will be constant after 2 second I mean 5+6+6+6=23 2nd second value change by 1 and after that speed not change could be answar

Am I wrong?

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

Ok I got it "maximum possible value"

I missed this phrase

How to solve the problem F? Who can help me ?

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

mintegers 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^{5}.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_placedleftmost columns, and we must buildr1 more blocks in first row,r2 more blocks in second row, ...,r5 more blocks in the fifth row; andlastis the bitmask of last placed column. Let's estimate number of states: 21 * 11^{5}* 32 = 10^{8}. 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.oh!Thank you very much.Your analysis is so distinct.And the search with memoization is more convenient to write.

In case of Problem-C

for the case 2 3

2 3

will not answar be 1,1

instead of 0,1 If second dice could not show 3 then this condition also apply for 1st dice too can't show 3 also?

I think then s=d1+d2+d3...dn condition will not satisfy

1st dice cannot show 3 by definition:

d_{1}= 2, so it can only show 1 or 2 (but not 3, 4, 5 or any greater value).by mean defination you mean this line?

"s = d1 + d2 + ... + dn."

No, I mean second sentence from the problem: "The i-th dice shows numbers from 1 to

d_{i}".Got it thanks

Tutorial ?!

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

Please anyone tell me , why this solution for problem-D is WA on test-9 ? Isn't it a correct order ?.. Sol:-> 10692139

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

Think Problem A pretests without test 5 -> Hacksss :)))

My code in problem 534D - Handshakes got AC 10687529 but when I try the test case n=5 - [0 1 2 0 4] it's output is Impossible but it should be possible 1 2 3 4 5 How come?!!!!!!

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

I was misunderstand this part of the problem.. thanks :)

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

The answer is indeed Impossible.

where are the editorials

Please publish the editorials for the round!!

How to solve Problem-D

I mean from where I should start?

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.

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

Can you explain why this solution works?

Sorry,I can't prove it.

Here is the editorial, but for some reason it is not attached to the contest

Sorry,wrong contest.

hello I am tired , trying D problem

someone can help me !!!!! why does it give me runtime error on case 46 ??? 10733747

that is my code

thanks for advance everyone

10734329

thanks you!!! but could you explain me ?? what happen ??

current = (*it).first; s[where].erase(it);

why it doesn't equals to

s[where].erase(it); current = (*it).first;

You erase

`it`

and after you use invalidated memoryI get it. thanks you !!!