Hello, Codeforces.

Codeforces Round 389 (Div. 2) will start on December 25 (Sunday), 09:05 (UTC). It will be based on Technocup 2017 Elimination Round 3. So, if you are a Russian-speaking high-school student, please take part in the Technocup 2017.

Many thanks to KAN, fcspartakm, Endagorion, Kostroma and Golovanov399 Hope to extend the list soon because of testers. Also some problem ideas are mine.

I hope you will like problems. It will be 6 problems.

Wish you good luck and bugless code

**UPD:** The scoring is 500 - 1000 — 1500 — 2000 — 2500 — 2500

Unusual time >:( Never seen a contest this early before.

Contests are the best kind of Christmas gifts.

I love contests, but so far I've only gotten rating drops for Christmas.

Yeah I've been on a pretty bad downward trend of rating drops lately so hopefully we both go up lol.

Yep, good luck to you and everyone else doing the contest! I hope they have more contests coming during Christmas time.

Dont worry, He's working on it. Just believe! :)

I guess I can say congrats on going up now :)

Rating doesn't matter.. Practice and practice :D :)

I hoped div 1 round and another big battle bitween nutela guys and me :D

Anyway thanks for one more contest :)

Want a contest for Div.1

can't you take part in Div.2?

It's unrated (aha!) for Div1 contestants.

unrated is better than downward rating.

Ehhm, actually they are planning to increase their ratings...

"Wish you bugless code" I like this wish

good time for me. hope interesting problem

As usual, the score distribution will be released before the contest starts.

So does the ** ** ***** meme.

What is "** ** *****" ?

"Is it rated"?

yes

[user:Kostoma]? I think it should be Kostroma .

There are two contests in CF now, one is "Technocup 2017 — Elimination Round 3" and the other is "Codeforces Round #389". I do know that I should go to the official website if I were a Russian-speaking high-school student, but now that both the contests are in CF, and I'm an English-speaker, which one should I participate?

Round #389 of course, since you are NOT a Russian-speaking high-school student.

I'm sorry, but I think it will be understandable only for the countries of the former USSR )))

Oh, what a pity! This guy is so unlucky! xDD

And that guy has exactly 11 hacks too.

(Btw are they having a warm-up contest?)

Btw, Wont we get our new year gift this year? I mean, wont there be an option of changing handles this year? :( I'm fedup with my handle

Terms of agreement were in Russian. Will problem statements be in English?

Yes

sorry, but what is the difference between these 2 contest?

First contest only for Russian pupils, second contest for participants from Div 2.

Being more precise, the round that is "Technocup 2017 — Elimination Round 3" is a qualifying round for the russian school (Junior) informatics olympiad.

why are the terms of agreement written in english? Should i just register or is there anything important?

For me this contest will be on the Christmas morning (I am Romanian). I won't be able to participate.

Hope there's no "greedy" tag ^o^

Hi Andy.

The last 4-5 contests have had so many greedy problems! xD

Greedy problems are hard :'(

I agree. They require a lot of out of the box thinking, unlike relatively similar level DP problems. A div 2 C greedy + constructive algorithms is much harder for me than a div 2 D DP.

Technocup problems are usually harder than the normal contest questions right? I am new here.

They are on the same level as div2 problems.

Yes, it is correct.

!

If I am a high school student, but not from Russia, it also can I compete for prizes?

Too many homework. Who can help me with my homework I really want to take part in it:)=>

But I just think it won't be easy at all

No money for Christmas:O

=)

A great way to learn DFS.

Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Is it rated?

Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)Don't see this spoiler)DFS is easy. Now teach us BFS =)

`$('.spoiler-title').click()`

where's my dfs?Yes, It is rated.

I did bfs on it :d

Ok this is dfs on tree, how would you teach us dfs on general graphs? :D

Wish to have upward rating as Christmas Gift...LOL But downward rating won't be able to restrain myself from participating rated Contests.

when is the winter look of the site coming? :D

the holiday comes to us!

i liked the new style of CF <3

Just curious, why do you have Div.1 Rated Unofficial Round for Technocup round 2, but not round 3. Is round 3 easier than round 2?

For Round 2 we've added two extra problems specially for D1. This time we do not have enough time, sorry. We expect interesting D2 round, you can join in unrated way.

Bugless code would be great but I am happy with less buggy code currently. Thanks Mike.

Today is my birthday! I am going to take part in this contest as my birthday gift =D Thanks to codeforces!

Merry Christmas to all and wish you a positive rating change...

same 2 u bro.. merry christmas..

finished 3 problem, look at standing, rank 1200, neat. look again 1200 out of 2700, damn, rating will drop.

take it easy .

I did not understand problem C. :( Everyone did that and now problem B is Hacked. :|

Same thing happened with me :P

Pretty scared about system tests. Every problem from B onwards could have some tricky corner-case. Good luck guys!

Problem F is similar to 364 Div1 B.

Exactly what I am thinking.

How can be hacked B?

aa ab Answer should be -1

ad

aa

answer is -1.

Darn I can't believe I didn't realize this during contest.

I was trying to hack other people after I solved your hack, but then I couldn't manage to open other people's solution somehow. Probably something with my browser. What a pity.

Can confirm was hacked by the cases above.

Edit: Jesus Christ just took a look at the leaderboard. Calm your +18 hacks down mate...

Best tests for B:

aa ab

pp ap

LOL :D

So fail;)

Why high school olymps always goes wrong for me?:D

I know that feel bro...

Your rating is inspirational :D

Was pretest 8 of question E some edge case?

Same, got 3 WA on pretest 8.

Problem C is much more easy than B :/ Solved C in 2 minutes, but B took about an hour

Good for you — This sounds promising as you probably didn't get hack.

First, I found it difficult to understand C. How did you solve it?

Ex: RRRU|LU|RURUU|LULLL|DLDD|RDRD|LD| answer is 7

Oh, interesting. Will have to think why that works. Thanks for sharing your solution.

There are many ways to solve it.

Start currX and currY with 0. If 'R' occurs, then currX=currX+1, etc. And now check the distance b/w prevX,prevY) to (currX,currY). If it is increasing, then its ok and update curr. Otherwise it is required point, so count++, and update prev and curr.

First delete all the consecutive duplicate characters (For example, RRLUDDL will be same as RLUDL). If current character is making U-type-turn, then it is the point,so count++. else move forward. (RUL,RDL,URL,RL,UD,etc will make U-type-turn). Solution for this : 23321935

Whats the logic for E,please?

Binary search on the number of slices that each person can get .

There are a couple of ways to solve it. I think the optimal way is this one:

Keep the maximum value at the start, you'll choose only this one.

Go through all the ones that have more than the current minimum value and split them. You'll do this O(log(max_value)) times, so the complexity is O(log(max_value)*n)

Hits for problem D?

Hash and group the strings, then compute the results by taking strings greedily.

u_u I could not found the greedy approach!I had no idea if it was convenient for a string to pair with itself or with his palindrome

You can't be greedy in all the problem, only in the first part of it =P

Try to separate it in two cases:

1 — the string is not a palindrome? Than, I can put it on the final string IF AND ONLY IF I put his reverse; you can check if Santa will get happier with it xD

2 — the string is a palindrome? If so, do I have 2 of it, and it compensates to put two of it on the final string?

For the not greedy part, you have to look for the better string to put in the middle (it has to be a palindrome); notice that this is the same that removing one palindrome string from the final string

You can greedy all the way if you keep the value correctly.

Did you use trie as a hash or map<> was enough for this problem?

map<string, vector > was enough.

The cost to insert a string with size

ninto a trie is Θ(n).What is the cost to insert that same string into

`map<string, ..>`

?O(nlog(amount of input)), which is still good enough to fit into TL.

I've understood from your previous comment that map<> is good enough for this task :)

Now I am more interested in general understanding of the situation with keys in

`map`

and`set`

.When we are inserting

stringsin`map`

it is not the same as insertingintegervalues. Internally`map`

has to performO(log(m)) comparisons to find the place where we should insert the key. Forstringkeys andintegerkeys this estimate is the same, but not for the comparison. It takesO(1) operations to compare 2 integers, but to comparestringsof sizenwe need Θ(n) operations.So, to sum up, according to my calculations the complexity of inserting

mstrings of sizento`map`

or`set`

isO(nmlog(m)).Am I right?

Yes, you are correct. In total m times of query should take O(nmlog(m))

What is the test 10 of problem E?

this is it

50 300

9293 9540 6585 6756 215 6853 4819 3033 5529 8201 4072 4862 4071 5500 5717 229 7696 5440 4407 1108 1680 1974 5414 9053 8480 1030 5556 5551 4741 452 1045 2553 8944 7627 3737 3876 2846 3563 3246 8436 1075 2974 9410 1127 1968 830 1380 7371 6414 6384

Too bad it's not possible to hack own solution. While hacking others I realized, that my code has the same bug, so I could have used the extra 100 hack points, since it will fail systest anyways...

U want to hack yourself?!:d and u want to earn points when hack yourself?!

It is not too bad :D , if I realized that I will fail a test , I will hack my self then I will submit again with an if condition added xD which says if (input == certainInput) print (the right answer) , then I will hack my self again with another test case but the same concept ...... and I will get a lot of points which I don't deserve :D

You can't resubmit after locking solution and you can't hack without locking

Best contest ever

but it needs more time to solve all the problemset :\

Good Luck everybody :D

5651 registered for contest.

2745 have actually participated.

More than a half decided to skip this round. What happened?

Christmas magic! :)

wtf, my binary search in problem E was giving wrong answer? testcase 8. anyone please?

You probably didn't do the divisions in half. I had WA test 8 as well until I fixed that.

omg, what a blunder! It was easier than D, you know.

I got this wrong too, you can't just divide. Pieces can only be cut in roughly halves.

Problem C seemed really hard to me. What are some important observations for it that lead to a solution?

Intuitively, we can tell that if the robot changes the vertical / horizontal direction, then the current position of the robot may lie one of the point.

One of the way to approach this question is by keeping whether the robot is free to change it’s vertical or horizontal direction without declaring an extra point.

OBS1:A path is shorthest path if is true that his length is equal to the manhatan distanse,I mean abs(X)+abs(Y)

OBS2:Try to get minimum number of intervals where OBS1 is true

The idea is that the robot will not decrease the distance from its starting position when he is moving to the target. That is, the value |

x| + |y| should always increase when he is moving to a target. When you see that this value is decreased, that means he has reached a target before that move and he is now moving to the next target.If he is going from point p1 to point p2, he can't go to Left and Right beyond that path, only to one of then. Same for Up and Down ;)

There are many ways to solve it.

Start currX and currY with 0. If 'R' occurs, then currX=currX+1, etc. And now check the distance b/w prevX,prevY) to (currX,currY). If it is increasing, then its ok and update curr. Otherwise it is required point, so count++, and update prev and curr.

First delete all the consecutive duplicate characters (For example, RRLUDDL will be same as RLUDL). If current character is making U-type-turn, then it is the point,so count++. else move forward. (RUL,RDL,URL,RL,UD,etc will make U-type-turn). Solution for this : 23321935

How to solve C ?

Between any two points, to move on the shortest path, you will go only in two directions: {R, U} or {R, D} or {L, U} or {L, D}. You can't go R and after other moves, make L because it won't give you the shortest path. So, all you have to do is to check if you "change" your directions. For example, if you move to R and U/D, and then move to L, it means that you arrived at a point before move to L. In other words, you have to split your string in continuous substrings such that in any substring, there aren't 'U' with 'D' and 'R' with 'L'.

Example: RUDRDDRUURDRDURDRD ===> RU|DRDDR|UUR|DRD|UR|DRD ==> 6 points

Was thinking along the same lines but made some implementation bugs :(

http://codeforces.com/blog/entry/49251?#comment-333247

D hack case :

4 3

aba 4

aba 3

aba 3

aba -2

Answer : 10

Pass your test, but WA8 still)

test 8 must be something with 0. I got four WA on 8 and changed > to >= and got passed

Passed your test but I just realized my solution gives a wrong answer for this:- 2 4 aaaa 5 aaaa 5

My solutions gives 20 :( .RIP D.

free christmas trees for everybodyb solve < c solve :/

Merry Christmas!

I wonder what kind of test is it...

ab aa

We're talking about problem D, not B

No, we are taking about B :)

I thought OP meant problem D lol.

That moment when you make 11 hacks on B and then recieve Wrong Answer on main tests xD Merry Christmas guys

why system test so quickly?

Maybe because only half the registrants participated?

Problem E , WA 21 . Anyone knows why ?

Try this test:

1 3 7

Answer should be 2.

Thanks :)

problem E: 2 2 1 1000

ans 500

Problem E statement says: "Santa Claus wants to present to everyone either a whole tangerine or exactly one part of it (that also means that everyone must get a positive number of slices)", that is #tangerines > 0, but in test #11:

total pupils k = 2000000000

total sum of parts of all tangerines = 128135987

Obviously, no solution. Answer in test is 1. Am I wrong?

How could you tell "total sum of parts of all tangerines = 128135987" ?

I just gotten the test and did

Submission

The issue was the test is cut at the page (that is my fault when copying not full test data). And I've forgotten long long.

Thanks :)

Eventually, got AC. To mention, complexity is NlogM with binary search, M is upper bound on a[i].

Submission

the expected time complexity for E is

Nlog^{2}Nright ? myNlog^{3}Nsolution got TLE.There exist a O(N) solution. I also got TLE. =(

)= any binary search is TLE?

Mine. Tle with bin search

The sole reason I didn't submit was because I didn't have a

O(N) algorithm that would fit TL. I guess we have good enough testcases for the problem! :)I used binary search and got AC, the complexity is

O(log10^{7}* (10^{7}+N)), 23298066Why in java when I defined a HashSet of Pair<Character,Character> and insert (a,a) then insert (a,b), the HashSet only contain (a,b), even the 2 inserted value are different (Obviously (a,a) != (a,b)) ?

Sets by definition don't keep duplicates (duplicate keys in this case). So when you put (a, a) the value a is mapped to key a, and then when you put (a, b), the old value for key a is erased and overwritten as b.

I know that, by I created a HashSet not a HashMap and as I know HashSet contains only keys (not pair <key,value> as you said) and doesn't contains duplicates, now Pair<"a,"a"> != Pair<"a,"b"> and these 2 are not considered duplicates, right ? or I'm messing something there ?

You are wrong.

It only checks for first element in pair. You have to create a custom compare function.

Oh thanks I didn't know that ,it's disappointing that I was aware of the hack but I was wrong with syntax :( !

You are wrong.

Check your line

`if(a.charAt(i) != b.charAt(i))`

. You never insert (a,a) into the set.Thanks i got it now.

anyone who got TLE on E? sorting the numbers of slices gives me AC.. it's weird..

B :OWTF !!In what time does the ediorial come in general ?? I am new to codeforces.

10 minutes — 1 day.

http://codeforces.com/blog/entry/49311

I just wrote my approaches to the problem, you can read them if you want to know the solutions right now.

## taketop150

During the contest i've found out that my knowledge of C++ is really awful. I've been writing in Java for so long and changed my language about a week ago so that OK I guees. But could you guys please help me. In my code for D I had map<string, vector > val which meant all the prices of string s. After reading the data, I did the following:

`for (auto p : val) sort(p.second.begin(), p.second.end())`

which, as I thought, sorted all the arrays in val. But actually it didn't because when I accesed val[i], it's elements were in input order. Why so?23302886 that's the submission to make it clear.

`for (auto &p : val)`

23308346Absolutely right solution failed because of only 1 character in code. So cruel. Thank you a lot. But could you please explain if I am right that

`for (pair<string, vector<int>> p : val)`

copies it's items, so in fact it works in O(n) ?Despite the fact that I could be in top-15 or even better, I'm not sad because finding this gap in my knowledge in CF round is much better than in some important rated olympiad. Also, I believe that the person who does such a stupid mistakes shouldn't be in Div1 :)

Чтобы изменять элемент map'a надо писать: for (auto &p : val), т.к. иначе p только копирует значение.

Can anyone help me in D? WA test 14, don't know what's wrong...

http://codeforces.com/contest/752/submission/23309705

3 3

aba 5

aba -2

vvv 1

answer: 5

your answer: 4

I thought I had taken care of this, thanks a lot!!!!!!

How the output for first test case

4 RURD

is 2 ?

Robot in (0, 0) First point is (1, 1); Second is (2, 0) OR First point is (2, 1); Second is (2, 0)

Where is UPD2???(((

TLE in div2E because I didn't sort the array :( such case very problem no wow

Actually

O(n×log^{2}(n)) is little bit tedious solution for this problem. Mine got AC without sorting(same complexity). I used some bit-wise operations to reduce the time.Without sorting, solution of

`O(log(10^7) * (n + 10^7))`

is getting AC.log(10^7)*log(10^7)*n is getting AC. However, I had to do a little optimization like getting rid of long long .

Could someone tell me why my code on problem D was wrong on test 11? Is hash unavailable for it?I'm really confused.Thanks! Here is my code: http://codeforces.com/contest/752/submission/23309803

How to solve F?

You can always use a single node, the centroid of the tree. Once you find that, find the list of each vertices in each subtree. Then put them in a priority queue and always make a pair one each from the two longest lists.

Code

Thanks!

Not always the centroid of the tree.

When will be editorial??

"results will be later". This is written on oficial web-site of TechnoCup.

Here it is, sorry for the delay.

А будут ли написаны победители контеста? И ссылка на разбор с самой записи о контесте — как обычно?

Can anyone tell how to solve E using binary search (if possible) ???

Binary search the minimum amount everyone should have. To calculate how many people can receive this amount of slices, just run through every element in the array (since every element is independent). Here's my code (pretty short) 23302187

Thanks a lot :)

could you explain this part of your code?

i know here you are finding for each tangerine how many people can get an amount m. I had to spend almost 3 hours to figure out an appropriate way to do this. Check my submission 23315399 (the howmany(wholesize,piece) function). I knew there must be a more concise approach to calculate this.

I discovered it by observation. Notice that j = minimum (m * 2^k) that k is integer and m * 2^k >= a[i].

If j = a[i] then the amount will be exactly 2^k (equals to p). Otherwise when a[i] is decreased by one, two of the "m" will become m*2-1 and not divisible anymore. The amount will decrease by one until the amount becomes 2^(k-1).

Like this

Nice Observation :) ... I could never have observed it by myself :(

Jeez, Thanks man... Thats some observation

My first realization for

Problem Dto solve using Tries and some greedy approach. But it seems hard for me to code it. If someone thinks like me, please share your logic and code also. Thanks everyone. :)It's actually quite a hard problem, tbh. I thought I solved it in contest but failed systest. The approach is greedy, but you have to be very careful.

First, sort the strings in non-increasing order of cost. Then, when we arrive at each string, we have to consider two cases:

The string is not a palindrome. In this case, we want to pair it with the reverse of this string. Also, we want the beauty to be the highest possible, so we will take one of the "reversed strings" that we need to find from an std::set that contains the strings already traversed. Of course, this should be the one with maximum beauty and can be found using lower_bound().

The string is a palindrome. We do the same process as #1, but slightly modified. Consider the case:

4 3

aba 6

aba -3

rty 2

rty 4

If we implement #1 with this test case, regardless whether the string is a palindrome or not, we will get an answer of 9. The actual answer should be 12. We notice that we can always unpair exactly one pair of palindromes that are already paired from #1 and we will put then in the middle of the final answer's string. Greedily, we will choose the one with lowest negative number (in this case it is -3). Let's denote this value as m. Finally, there is also in another case, where there are not matching pairs for the palindrome. In this case, we will put in the middle of the string, but only if the beauty of it exceeds m.

The answer is retrieved from doing #1 on the whole set, regardless of it being palindrome of not, then along the way take into consideration the cases in #2. Final answer = (answer of #1) + m. Hope this helps.

Thanks. I actually think to map the same string and their beauties. And another variable for putting string in the middle. Variable initialized to 0.

If a string is palindrome, then I could take Even number of string like this and also 1 from putting in the middle. But I will take Even number from this if beauties positive. And if left any positive beauties string, then update the variable I mentioned above, which will maximize my middle string beauty.

If a string is not a palindrome we can took even number of its copy ( I mean from several string). I will take up to it positive donation. Because if I discard it I will not get any positive donation. So, take as many as possible but the donation should be positive.

For your test case:-aba is palindrome. So, it could stay in middle. I can take No even string first. Then, update the variable to 6

rty is not a palindrome. So, I will take up to its positive donation as possible. So, I will take two from this. Donation: 2+4 = 6

So, Total = 6 + 6 = 12

If you want my code, 23314454. Try writing it your way and compare the two. Maybe you find that your way easier.

The answer should be 6.

How is the answer 12? Won't the final string be "aba" giving beauty 6. Am i missing something? Thanks.

Optimal answer will be: "rtyabarty" with considering "aba" that has 6 beauty so max beauty will be 4 + 2 + 6 = 12

Edit: nvm i realized I was mistaken, maybe he meant the second "rty" to be "ytr" then in this case it will be 12

Maybe test should be like this? If you want answer = 12: 4 3 aba 6 aba -3 rty 2 utr 4

the answer for your test is 6, or i didn't understand something.(?) //

p.s by the way , i don't know why i am getting WA on test #8, if someone had the same problem i will be thankful if he will tell me which problem he had. :))

p.p.s my code : CODE,PROBLEM D

You can check this case: 4 1 a 2 a -3 b 2 b -3

answer is 3.

But correct Answer is 2

I don't exactly know, what do you mean when you say "greedy approach" but my solution is smth like greedy approach. Ask smth if you don't understand)

Check this

Can anyone tell what wrong am I doing here Solution

in strings 38-39 first you do i++ and only then you do st.insert( s[i] );, but it should be like this: st.insert( s[i] ); i++;

That was not expected. Thanks.

Meanwhile, Can you give a hint for D?

Yeah! For each string you should find reversed with best coast. And maybe in center you will have one polindrome string.

Who's waiting for Mike's blog on chaning handle like me!? :-""

And on changing color too :D

When we can change nickname?

hi first thx for the contest... this submission 23355723 is for problem D. i don't know why i got WA#8 :( please help me... thanks

I don't know what is wrong with your code, but you fail in this testcase:

3 3aba 5aba -5xyx 3answer is 5.

thank you so much :) i got what was wrong... now it was Accepted :) thx

Can somebody tell me why i got WA in problem D with this solution?

http://codeforces.com/contest/748/submission/23331649

update : i got accepted

Could someone tell me why my answer got wrong in problem C in the pretest 14 (the answer was 50306 but i just got 50305) :(

http://codeforces.com/contest/748/submission/23372619

Here is shorter test case that doesn't work: