By MikeMirzayanov, 2 years ago, translation, ,

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

•
• +181
•

 » 2 years ago, # |   0 Unusual time >:( Never seen a contest this early before.
 » 2 years ago, # | ← Rev. 2 →   +84 Contests are the best kind of Christmas gifts.
•  » » 2 years ago, # ^ |   +6 I love contests, but so far I've only gotten rating drops for Christmas.
•  » » » 2 years ago, # ^ |   0 Yeah I've been on a pretty bad downward trend of rating drops lately so hopefully we both go up lol.
•  » » » » 2 years ago, # ^ |   0 Yep, good luck to you and everyone else doing the contest! I hope they have more contests coming during Christmas time.
•  » » » » 2 years ago, # ^ |   +38 Dont worry, He's working on it. Just believe! :)
•  » » » » 2 years ago, # ^ |   0 I guess I can say congrats on going up now :)
•  » » » 2 years ago, # ^ |   +33 Rating doesn't matter.. Practice and practice :D :)
•  » » » » 2 years ago, # ^ |   0 only if that was true .. .. .
 » 2 years ago, # |   +29 I hoped div 1 round and another big battle bitween nutela guys and me :DAnyway thanks for one more contest :)
 » 2 years ago, # |   +44 Want a contest for Div.1
•  » » 2 years ago, # ^ |   +9 can't you take part in Div.2?
•  » » » 2 years ago, # ^ |   0 It's unrated (aha!) for Div1 contestants.
•  » » » » 2 years ago, # ^ |   -33 unrated is better than downward rating.
•  » » » » » 2 years ago, # ^ |   +39 Ehhm, actually they are planning to increase their ratings...
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   -22 I didn't mean that. I was trying to say, div 1 contestants are more capable of div 2 problems. So these problems are easy to them. So, I thought current rating of div 1 contestants is better than to be the 1St in div 2. So, rating might be decreased!
 » 2 years ago, # |   0 "Wish you bugless code" I like this wish
 » 2 years ago, # |   +6 good time for me. hope interesting problem
 » 2 years ago, # |   +207 As usual, the score distribution will be released before the contest starts.So does the ** ** ***** meme.
•  » » 2 years ago, # ^ |   +9 What is "** ** *****" ?
•  » » » 2 years ago, # ^ |   +22 "Is it rated"?
•  » » » » 2 years ago, # ^ |   -7 yes
 » 2 years ago, # |   +9 [user:Kostoma]? I think it should be Kostroma .
 » 2 years ago, # |   0 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?
•  » » 2 years ago, # ^ |   0 Round #389 of course, since you are NOT a Russian-speaking high-school student.
 » 2 years ago, # |   +61 I'm sorry, but I think it will be understandable only for the countries of the former USSR )))
 » 2 years ago, # |   +26 Oh, what a pity! This guy is so unlucky! xDD
•  » » 2 years ago, # ^ |   +6 And that guy has exactly 11 hacks too.(Btw are they having a warm-up contest?)
 » 2 years ago, # |   +23 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
 » 2 years ago, # |   +3 Terms of agreement were in Russian. Will problem statements be in English?
•  » » 2 years ago, # ^ |   +5 Yes
 » 2 years ago, # |   +6 sorry, but what is the difference between these 2 contest?
•  » » 2 years ago, # ^ |   +4 First contest only for Russian pupils, second contest for participants from Div 2.
•  » » 2 years ago, # ^ |   0 Being more precise, the round that is "Technocup 2017 — Elimination Round 3" is a qualifying round for the russian school (Junior) informatics olympiad.
 » 2 years ago, # |   +2 why are the terms of agreement written in english? Should i just register or is there anything important?
 » 2 years ago, # |   -8 For me this contest will be on the Christmas morning (I am Romanian). I won't be able to participate.
 » 2 years ago, # |   0 Hope there's no "greedy" tag ^o^
•  » » 2 years ago, # ^ |   +26 Hi Andy.
•  » » » 2 years ago, # ^ |   +2 The last 4-5 contests have had so many greedy problems! xDGreedy problems are hard :'(
•  » » » » 2 years ago, # ^ |   -8 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.
 » 2 years ago, # |   +12 Technocup problems are usually harder than the normal contest questions right? I am new here.
•  » » 2 years ago, # ^ |   +19 They are on the same level as div2 problems.
•  » » » 2 years ago, # ^ |   +16 Yes, it is correct.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 !
 » 2 years ago, # | ← Rev. 2 →   0 If I am a high school student, but not from Russia, it also can I compete for prizes?
 » 2 years ago, # |   +2 Too many homework. Who can help me with my homework I really want to take part in it:)=>
•  » » 2 years ago, # ^ |   0 But I just think it won't be easy at all
•  » » » 2 years ago, # ^ |   +4 No money for Christmas:O
 » 2 years ago, # | ← Rev. 2 →   0 =)
 » 2 years ago, # |   +162 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)
•  » » 2 years ago, # ^ |   +17 DFS is easy. Now teach us BFS =)
•  » » 2 years ago, # ^ |   +62 \$('.spoiler-title').click() where's my dfs?
•  » » 2 years ago, # ^ |   +11 Yes, It is rated.
•  » » 2 years ago, # ^ |   +8 I did bfs on it :d
•  » » 2 years ago, # ^ |   +24 Ok this is dfs on tree, how would you teach us dfs on general graphs? :D
 » 2 years ago, # |   +8 Wish to have upward rating as Christmas Gift...LOL But downward rating won't be able to restrain myself from participating rated Contests.
 » 2 years ago, # |   +2 when is the winter look of the site coming? :D
•  » » 2 years ago, # ^ |   +58 the holiday comes to us!
•  » » » 2 years ago, # ^ |   +4 i liked the new style of CF <3
 » 2 years ago, # |   +22 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?
•  » » 2 years ago, # ^ |   +21 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.
 » 2 years ago, # |   0 Bugless code would be great but I am happy with less buggy code currently. Thanks Mike.
 » 2 years ago, # |   +31 Today is my birthday! I am going to take part in this contest as my birthday gift =D Thanks to codeforces!
 » 2 years ago, # |   +12 Merry Christmas to all and wish you a positive rating change...
•  » » 2 years ago, # ^ |   +3 same 2 u bro.. merry christmas..
 » 2 years ago, # |   -28 The comment removed because of Codeforces rules violation
 » 2 years ago, # |   +2 finished 3 problem, look at standing, rank 1200, neat. look again 1200 out of 2700, damn, rating will drop.
•  » » 2 years ago, # ^ |   +5 take it easy .
 » 2 years ago, # |   +6 I did not understand problem C. :( Everyone did that and now problem B is Hacked. :|
•  » » 2 years ago, # ^ |   +11 Same thing happened with me :P
•  » » » 2 years ago, # ^ |   0 same thing ;_; back to green
 » 2 years ago, # |   0 Pretty scared about system tests. Every problem from B onwards could have some tricky corner-case. Good luck guys!
 » 2 years ago, # |   +10 Problem F is similar to 364 Div1 B.
•  » » 2 years ago, # ^ |   0 Exactly what I am thinking.
 » 2 years ago, # |   0 How can be hacked B?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 aa ab Answer should be -1
•  » » 2 years ago, # ^ |   +1 ad aa answer is -1.
•  » » » 2 years ago, # ^ |   +5 Darn I can't believe I didn't realize this during contest.
•  » » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 Can confirm was hacked by the cases above.Edit: Jesus Christ just took a look at the leaderboard. Calm your +18 hacks down mate...
 » 2 years ago, # |   +8 Best tests for B: abb bab  bab bba  aca bdc 
•  » » 2 years ago, # ^ |   +2 aa ab
•  » » 2 years ago, # ^ |   +66 pp ap
•  » » » 2 years ago, # ^ |   0 LOL :D
 » 2 years ago, # |   +5 So fail;)Why high school olymps always goes wrong for me?:D
•  » » 2 years ago, # ^ |   +5 I know that feel bro...
•  » » » 2 years ago, # ^ |   0 Your rating is inspirational :D
 » 2 years ago, # |   0 Was pretest 8 of question E some edge case?
•  » » 2 years ago, # ^ |   0 Same, got 3 WA on pretest 8.
 » 2 years ago, # |   0 Problem C is much more easy than B :/ Solved C in 2 minutes, but B took about an hour
•  » » 2 years ago, # ^ |   +2 Good for you — This sounds promising as you probably didn't get hack.
•  » » » 2 years ago, # ^ |   0 i hope so
•  » » » 2 years ago, # ^ |   0 You were right Link
•  » » 2 years ago, # ^ |   0 First, I found it difficult to understand C. How did you solve it?
•  » » » 2 years ago, # ^ |   0 You should count number of the longest substrings which does not contain both L and R or both U and D
•  » » » 2 years ago, # ^ |   +1 Ex: RRRU|LU|RURUU|LULLL|DLDD|RDRD|LD| answer is 7
•  » » » » 2 years ago, # ^ |   0 Oh, interesting. Will have to think why that works. Thanks for sharing your solution.
•  » » » » » 2 years ago, # ^ |   0
•  » » » 2 years ago, # ^ | ← Rev. 6 →   0 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
 » 2 years ago, # |   0 Whats the logic for E,please?
•  » » 2 years ago, # ^ |   +1 Binary search on the number of slices that each person can get .
•  » » 2 years ago, # ^ |   0 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)
 » 2 years ago, # |   0 Hits for problem D?
•  » » 2 years ago, # ^ |   0 Hash and group the strings, then compute the results by taking strings greedily.
•  » » » 2 years ago, # ^ |   0 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
•  » » » » 2 years ago, # ^ |   0 You can't be greedy in all the problem, only in the first part of it =PTry 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 xD2 — 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
•  » » » » » 2 years ago, # ^ |   0 You can greedy all the way if you keep the value correctly.
•  » » » 2 years ago, # ^ |   0 Did you use trie as a hash or map<> was enough for this problem?
•  » » » » 2 years ago, # ^ |   +2 map was enough.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 The cost to insert a string with size n into a trie is Θ(n).What is the cost to insert that same string into map?
•  » » » » » » 2 years ago, # ^ |   0 O(nlog(amount of input)), which is still good enough to fit into TL.
•  » » » » » » » 2 years ago, # ^ |   0 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 strings in map it is not the same as inserting integer values. Internally map has to perform O(log(m)) comparisons to find the place where we should insert the key. For string keys and integer keys this estimate is the same, but not for the comparison. It takes O(1) operations to compare 2 integers, but to compare strings of size n we need Θ(n) operations. So, to sum up, according to my calculations the complexity of inserting m strings of size n to map or set is O(nmlog(m)).Am I right?
•  » » » » » » » » 2 years ago, # ^ |   0 Yes, you are correct. In total m times of query should take O(nmlog(m))
 » 2 years ago, # |   0 What is the test 10 of problem E?
•  » » 2 years ago, # ^ |   0 this is it50 3009293 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
 » 2 years ago, # |   0 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...
•  » » 2 years ago, # ^ |   +4 U want to hack yourself?!:d and u want to earn points when hack yourself?!
•  » » 2 years ago, # ^ |   0 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
•  » » » 2 years ago, # ^ |   +5 You can't resubmit after locking solution and you can't hack without locking
 » 2 years ago, # |   0 Best contest everbut it needs more time to solve all the problemset :\Good Luck everybody :D
 » 2 years ago, # |   +5 5651 registered for contest.2745 have actually participated.More than a half decided to skip this round. What happened?
•  » » 2 years ago, # ^ |   +11 Christmas magic! :)
 » 2 years ago, # | ← Rev. 4 →   0 wtf, my binary search in problem E was giving wrong answer? testcase 8. anyone please?
•  » » 2 years ago, # ^ |   0 You probably didn't do the divisions in half. I had WA test 8 as well until I fixed that.
•  » » » 2 years ago, # ^ |   0 omg, what a blunder! It was easier than D, you know.
•  » » 2 years ago, # ^ |   0 I got this wrong too, you can't just divide. Pieces can only be cut in roughly halves.
 » 2 years ago, # |   0 Problem C seemed really hard to me. What are some important observations for it that lead to a solution?
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +3 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
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +3 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 ;)
•  » » 2 years ago, # ^ |   0 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
 » 2 years ago, # |   0 How to solve C ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 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
•  » » » 2 years ago, # ^ |   0 Was thinking along the same lines but made some implementation bugs :(
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # | ← Rev. 2 →   +9 D hack case :4 3aba 4aba 3aba 3aba -2Answer : 10
•  » » 2 years ago, # ^ |   +5 Pass your test, but WA8 still)
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 test 8 must be something with 0. I got four WA on 8 and changed > to >= and got passed
•  » » 2 years ago, # ^ |   0 Passed your test but I just realized my solution gives a wrong answer for this:- 2 4 aaaa 5 aaaa 5My solutions gives 20 :( .RIP D.
•  » » 2 years ago, # ^ |   0 i could pass this case，but still wrong on test 4；why？
 » 2 years ago, # | ← Rev. 2 →   +14 free christmas trees for everybody
 » 2 years ago, # |   +39
•  » » 2 years ago, # ^ |   0 b solve < c solve :/
 » 2 years ago, # |   0 Contest always end up with hacking :(
 » 2 years ago, # |   0 WOW even with all these hacks there were more many hacks in a and b
 » 2 years ago, # |   +45 Merry Christmas!
•  » » 2 years ago, # ^ |   0 I wonder what kind of test is it...
•  » » » 2 years ago, # ^ |   0 ab aa
•  » » » » 2 years ago, # ^ |   0 We're talking about problem D, not B
•  » » » » » 2 years ago, # ^ |   0 No, we are taking about B :)
•  » » » » 2 years ago, # ^ |   0 I thought OP meant problem D lol.
 » 2 years ago, # |   +4 That moment when you make 11 hacks on B and then recieve Wrong Answer on main tests xD Merry Christmas guys
 » 2 years ago, # |   0 why system test so quickly?
•  » » 2 years ago, # ^ |   0 Maybe because only half the registrants participated?
 » 2 years ago, # |   0 Problem E , WA 21 . Anyone knows why ?
•  » » 2 years ago, # ^ |   0 Same doubt
•  » » 2 years ago, # ^ |   +7 Try this test:1 3 7Answer should be 2.
•  » » » 2 years ago, # ^ |   0 Thanks :)
•  » » 2 years ago, # ^ |   0 problem E: 2 2 1 1000ans 500
 » 2 years ago, # | ← Rev. 3 →   0 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 = 2000000000total sum of parts of all tangerines = 128135987Obviously, no solution. Answer in test is 1. Am I wrong?
•  » » 2 years ago, # ^ |   +3 How could you tell "total sum of parts of all tangerines = 128135987" ?
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 I just gotten the test and did ll sum=0; RR(i,n) {R(a[i]); sum+=a[i];} printf("%lld\n",sum);Submission
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » » » » 2 years ago, # ^ |   0 Eventually, got AC. To mention, complexity is NlogM with binary search, M is upper bound on a[i].Submission
 » 2 years ago, # |   0 the expected time complexity for E is Nlog2N right ? my Nlog3N solution got TLE.
•  » » 2 years ago, # ^ |   0 There exist a O(N) solution. I also got TLE. =(
•  » » » 2 years ago, # ^ |   0 )= any binary search is TLE?
•  » » » » 2 years ago, # ^ |   0 Mine. Tle with bin search
•  » » » 2 years ago, # ^ |   0 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! :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 I used binary search and got AC, the complexity is O(log107 * (107 + N)), 23298066
 » 2 years ago, # |   0 Why in java when I defined a HashSet of Pair 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)) ?
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 I know that, by I created a HashSet not a HashMap and as I know HashSet contains only keys (not pair 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 ?
•  » » » 2 years ago, # ^ |   0 You are wrong.
•  » » 2 years ago, # ^ |   0 It only checks for first element in pair. You have to create a custom compare function.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Oh thanks I didn't know that ,it's disappointing that I was aware of the hack but I was wrong with syntax :( !
•  » » » 2 years ago, # ^ |   0 You are wrong.
•  » » 2 years ago, # ^ |   0 Check your line if(a.charAt(i) != b.charAt(i)). You never insert (a,a) into the set.
•  » » » 2 years ago, # ^ |   0 Thanks i got it now.
 » 2 years ago, # |   0 anyone who got TLE on E? sorting the numbers of slices gives me AC.. it's weird..
 » 2 years ago, # | ← Rev. 2 →   +40 B :O WTF !!
 » 2 years ago, # |   0 In what time does the ediorial come in general ?? I am new to codeforces.
•  » » 2 years ago, # ^ |   0 10 minutes — 1 day.
•  » » 2 years ago, # ^ |   +7 http://codeforces.com/blog/entry/49311I just wrote my approaches to the problem, you can read them if you want to know the solutions right now.
»
2 years ago, # |
0

# taketop150

 » 2 years ago, # |   +3 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 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.
•  » » 2 years ago, # ^ |   +6 for (auto &p : val) 23308346
•  » » » 2 years ago, # ^ |   +3 Absolutely 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> 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 :)
•  » » » » 2 years ago, # ^ |   0 cAN Anyone Explain me the problem C : Santa claus and Robot problem ? What is the gist of this problem ? . I dont understand how the output come ?4RURDhow answer is 2 ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 Чтобы изменять элемент map'a надо писать: for (auto &p : val), т.к. иначе p только копирует значение.
•  » » 2 years ago, # ^ |   0 for(auto &p : val) 
 » 2 years ago, # | ← Rev. 2 →   +13 Can anyone help me in D? WA test 14, don't know what's wrong...http://codeforces.com/contest/752/submission/23309705
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 3 3aba 5aba -2vvv 1answer: 5your answer: 4
•  » » » 2 years ago, # ^ |   +8 I thought I had taken care of this, thanks a lot!!!!!!
 » 2 years ago, # |   0 How the output for first test case 4 RURDis 2 ?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Robot in (0, 0) First point is (1, 1); Second is (2, 0) OR First point is (2, 1); Second is (2, 0)
 » 2 years ago, # |   +8 Where is UPD2???(((
 » 2 years ago, # |   +39
 » 2 years ago, # |   +12 TLE in div2E because I didn't sort the array :( such case very problem no wow
•  » » 2 years ago, # ^ |   0 Actually O(n × log2(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.
•  » » 2 years ago, # ^ |   +3 Without sorting, solution of O(log(10^7) * (n + 10^7)) is getting AC.
•  » » 2 years ago, # ^ |   +3 log(10^7)*log(10^7)*n is getting AC. However, I had to do a little optimization like getting rid of long long .
 » 2 years ago, # | ← Rev. 2 →   0 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
 » 2 years ago, # |   0 How to solve F?
•  » » 2 years ago, # ^ |   +6 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
•  » » » 2 years ago, # ^ |   0 Thanks!
•  » » » 2 years ago, # ^ |   0 Not always the centroid of the tree.
 » 2 years ago, # |   +8 When will be editorial??
•  » » 2 years ago, # ^ | ← Rev. 3 →   -12 "results will be later". This is written on oficial web-site of TechnoCup.
•  » » 2 years ago, # ^ |   +5 Here it is, sorry for the delay.
•  » » » 2 years ago, # ^ |   0 А будут ли написаны победители контеста? И ссылка на разбор с самой записи о контесте — как обычно?
 » 2 years ago, # |   +5 Can anyone tell how to solve E using binary search (if possible) ???
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 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
•  » » » 2 years ago, # ^ |   +5 Thanks a lot :)
•  » » » 2 years ago, # ^ |   +8 could you explain this part of your code? fr(n) { int p = 1, j; for (j = m; j <= a[i]; j *= 2) { p *= 2; } c += max(p / 2, p - j + a[i]); } 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.
•  » » » » 2 years ago, # ^ |   +6 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 a[i] = 8, m = 2 : {8} -> {4,4} -> {2,2,2,2} a[i] = 7, m = 2 : {7} -> {3,4} -> {3,2,2} a[i] = 6, m = 2 : {6} -> {3,3} -> {3,3} a[i] = 5, m = 2 : {5} -> {2,3} -> {2,3} a[i] = 4, m = 2 : {4} -> {2,2} -> {2,2} 
•  » » » » » 2 years ago, # ^ |   +5 Nice Observation :) ... I could never have observed it by myself :(
•  » » » » » 2 years ago, # ^ |   +5 Jeez, Thanks man... Thats some observation
 » 2 years ago, # | ← Rev. 2 →   +3 My first realization for Problem D to 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. :)
•  » » 2 years ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 2 years ago, # ^ |   +3 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 6rty 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 = 6So, Total = 6 + 6 = 12
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 If you want my code, 23314454. Try writing it your way and compare the two. Maybe you find that your way easier.
•  » » » » » 2 years ago, # ^ |   0 Thanks. I had solved using my logic. Again thanks for your nice support. You can also check my easy implementation. Here
•  » » » 2 years ago, # ^ |   +3 The answer should be 6.
•  » » » » 2 years ago, # ^ |   0 You are right. I think she made a mistake (typo). "ytr" and "rty". I tests her case thinking "rty" and "ytr".
•  » » » 2 years ago, # ^ |   +3 How is the answer 12? Won't the final string be "aba" giving beauty 6. Am i missing something? Thanks.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Optimal answer will be: "rtyabarty" with considering "aba" that has 6 beauty so max beauty will be 4 + 2 + 6 = 12Edit: nvm i realized I was mistaken, maybe he meant the second "rty" to be "ytr" then in this case it will be 12
•  » » » 2 years ago, # ^ |   0 Maybe test should be like this? If you want answer = 12: 4 3 aba 6 aba -3 rty 2 utr 4
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 2 years ago, # ^ |   0 You can check this case: 4 1 a 2 a -3 b 2 b -3
•  » » » » » 2 years ago, # ^ |   0 answer is 3.
•  » » » » » » 2 years ago, # ^ |   0 But correct Answer is 2
•  » » » » » » » 2 years ago, # ^ |   0 Yes, it's 2, thanks : )
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   -13 Check this
 » 2 years ago, # |   +3 Can anyone tell what wrong am I doing here Solution
•  » » 2 years ago, # ^ |   +3 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++;
•  » » » 2 years ago, # ^ |   +5 That was not expected. Thanks.
•  » » » 2 years ago, # ^ |   +5 Meanwhile, Can you give a hint for D?
•  » » » » 2 years ago, # ^ |   +3 Yeah! For each string you should find reversed with best coast. And maybe in center you will have one polindrome string.
 » 2 years ago, # |   +77 Who's waiting for Mike's blog on chaning handle like me!? :-""
•  » » 2 years ago, # ^ |   +9 And on changing color too :D
 » 2 years ago, # |   +1 When we can change nickname?
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ |   +1 I don't know what is wrong with your code, but you fail in this testcase:3 3aba 5aba -5xyx 3answer is 5.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 thank you so much :) i got what was wrong... now it was Accepted :) thx
 » 2 years ago, # | ← Rev. 2 →   0 Can somebody tell me why i got WA in problem D with this solution?http://codeforces.com/contest/748/submission/23331649update : i got accepted
 » 2 years ago, # | ← Rev. 2 →   0 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
•  » » 2 years ago, # ^ |   0 Here is shorter test case that doesn't work: 4 RLUD 
•  » » » 2 years ago, # ^ |   0 By your test case I managed to find my mistake in my code. Thanks a lot :D