### seland's blog

By seland, 4 years ago, translation, ,

Hello everyone!

I am glad to announce that soon will Codeforces Round #303 for Div.2 paricipants, the author of which I am. Traditionally Div.1 participants can take part out of the competition.

This is my first round, and I hope that it will be interesting.

Round wouldn't take place without the help of the Codeforces team! Great thanks to zlobober for helping me preparing the round and delinur for translation. Special thanks to everyone who puts his effort into the creation and maintenance of Codeforces and Polygon systems.

Score distribution will be announce later.

Good luck and inspiration!

UPD Score distribution will be — 500-1000-1750-1750-2500.

UPD Congratulations for winners in Div.2:

And in Div.1:

• +174

 » 4 years ago, # |   -67 Hoping for interesting problems and more rounds in future from you
 » 4 years ago, # |   -19 Hope the English version won't be from Google translator!!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Come on people,why downvote? I made some prediction here and as you can see the 1st problem really had some sign of google translation: "Little Susie, thanks to her older brother, likes to play with cars." Didn't my prediction work?
•  » » » 4 years ago, # ^ |   -12 People just like to downvote comparatively low rated programmers comments whatever they write.Racist everywhere.
 » 4 years ago, # |   +53 World Final for div 2 :)
 » 4 years ago, # | ← Rev. 2 →   +25 Maybe not so many genius unrated contestants, because most of them are in relaxation mode for tomorrow Div. 1 World Final ;)
 » 4 years ago, # |   +12
•  » » 4 years ago, # ^ | ← Rev. 2 →   +16 Many strong coders won't take part due to world finals . All of the strong coders are in div1 . That's why there are many div1 contests consecutively lined up after the WF ends.
 » 4 years ago, # |   +42 When tourist said his team did not feel any pressure for the world finals i thought OK.. But then querty787788 went ahead and registered for this contest as if he has nothing to do tomorrow. Let's see if he actually participates.
 » 4 years ago, # |   +4 I wonder why all the contest at the same time of the day ! It's not suitable and not reasonable at all .. can anyone explain this ?
 » 4 years ago, # |   +21 Score distribution will be announce later :) When??? JUST 10 min. befor contest and no announce :/
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 now 1 min :D
•  » » 4 years ago, # ^ |   +12 Well, the author thought that good luck and inspiration are enough :)
 » 4 years ago, # |   +15 Just 5100 participants?? too few! :D
•  » » 4 years ago, # ^ |   0 Do you believe in EDITORIALS??
•  » » » 4 years ago, # ^ |   0 stfu
 » 4 years ago, # |   0 who was translating statements??? i hate him with passion.
•  » » 4 years ago, # ^ |   +69 Telling what exactly you think is wrong in a translation is a more constructive way rather than just saying you hate someone.
•  » » » 4 years ago, # ^ |   0 I thought the translations were totally fine with a few minor mistakes that didn't really matter in understanding the problems.
•  » » » 4 years ago, # ^ |   0 ye sorry for nonconstructive criticism, but some of the problem's statements weren't translated fully, compared to russian statement (example: E's english statement didn't contain that graph is connecte initially, while russian statement did)
 » 4 years ago, # |   +5 The worst Contest EVER!A,B,C,D,E were all obvious! -_-
•  » » 4 years ago, # ^ |   +9 E was so obvious that I thought my logic has got to be wrong.
•  » » 4 years ago, # ^ |   +110 Guy registered 3 hours ago judges the problemset. You even weren't brave enough to participate from your real account, lol =)
•  » » » 4 years ago, # ^ |   -6 what a ad hominem attack
 » 4 years ago, # |   0 In problem E, using std::set(to implement Prims) gives TLE ?
•  » » 4 years ago, # ^ |   +3 How do you use Prims?Dijkstra with set doesnt give TL on pretests
•  » » » 4 years ago, # ^ |   0 Sorry, not Prims its Dijkstra. I keep getting TLE on 6th pretest. http://codeforces.com/contest/545/submission/11165455
•  » » » » 4 years ago, # ^ |   0 I can't open it until system tests will pass(.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 My Dijkstras gave MLE on test 6. What changes are expected ? http://codeforces.com/contest/545/submission/11167671
•  » » » » 4 years ago, # ^ |   0 What I did (after contest) was just to add a check when there is a tie in distance to reach a specific node X. If the distance of the last edge checked is smaller than the last edge of the previous path to X from the source, then update the path to X to the new one.Of course you also need to store all the time the edge that took you to each node after visiting it so you can be able to replace it afterwards.
•  » » » » » 4 years ago, # ^ |   0 That's exactly what I implemented
 » 4 years ago, # |   0 In E, how to prove that shortest path tree we get using dijkstra is indeed the shortest path tree with least weight ?
•  » » 4 years ago, # ^ |   +1 This solution may be hacked by following test case:3 3 1 2 8 1 3 6 2 3 2 1Simply doing djikstra — it will output 14; correct answer is 8.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Even using dijkstra, we get 8. Ofcourse, the modification if ( dist[X] <= dist[current]+weight of edge )then parent[X]=current is to be made.
•  » » 4 years ago, # ^ |   0 Is that always true anyway? At least my implementation of Dijkstra does not have that property, and I spent forever trying to figure out how to modify it to get that property.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +3 its wrong, so you cannot prove it :D UPD: I wasn't fast enough 
•  » » » 4 years ago, # ^ |   +5 so, what's the correct solution for E?
•  » » » » 4 years ago, # ^ |   0 Use Dijkstra and modify (d[v] == d[u] + w);
•  » » » » 4 years ago, # ^ |   +1 i used this method. consider the spanning-tree (shortest path ST) with minimum weights. delete a leaf from it then it can be prove that the remaining spanning tree is still with minimum weight. so remove all nodes then add them one by one, in which you add you shout set it parent the node with minimum edge weight. 
•  » » 4 years ago, # ^ |   +4 it isnt because i used dijkstra and i got WA. i think you should modify dijkstra so when (d[v] == d[u] + w) happens, you change d[v] to d[u]+w if the trees wieght decreases.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Let d[x] denote the minimum distance from u to x. Let's construct a tree in G using this approach: 1. Let u be the root. 2. For all other vertex p, we can choose as a parent any node q such that d[p]=d[q]+w[q][p]. The most natural idea is to select the q with minimum w[q][p].Since for each vertex we are selecting the edge with minimum weight, the total sum of weights will be minimum. It just remains to prove that for two different vertices, we can't choose the same edge as a link to the parent node (this is a consequence of positive weights)
 » 4 years ago, # |   +5 Question similar to E was asked in ICPC regionals this year. Here is the link.
•  » » 4 years ago, # ^ |   0 Actually solution algo was directly google-able too :P one can get ready-made algo for E in 2 clicks :/
 » 4 years ago, # |   0 Problem C was really hard for third problem(C).
•  » » 4 years ago, # ^ |   +3 It's obvious I think :) But D is easier than C.
•  » » » 4 years ago, # ^ |   0 i think C is the obvious one cuz its a simple DP.
•  » » » » 4 years ago, # ^ |   +3 i think you can solve it by using greedy approach also.
•  » » » » » 4 years ago, # ^ |   0 i would love to hear how.
•  » » » » » » 4 years ago, # ^ |   0 Starting from left, If you can fell a tree left, make it go left else if you can fell it on right make it go right. Why this works ? If you are falling left then it is easy to see that you are not spoiling the chance of the next tree. The option for next tree is open. If you are falling the tree to right, may be there is a possibility that the right tree can't fall left. Only thing is worst case scenario you have to select only one of this tree.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I did the same thing except in a way which is unnecessarily more complex. Why do you think it gets WA? My Submission
•  » » » » 4 years ago, # ^ |   +28 It was greedy. All problems were greedy :)
•  » » » 4 years ago, # ^ |   +5 D easier than A
•  » » 4 years ago, # ^ |   +1 Hard ?? why ?? it was a simple implementation .
 » 4 years ago, # | ← Rev. 2 →   -48 During coding phase,Earthquake at NEPAL-INDIA border ruined everything!! :( :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +56 I am From Nepal (Original) . Please Don't Make a Joke about Earthquake
•  » » 4 years ago, # ^ |   +5 I am from north India. There was no such earthquake.
 » 4 years ago, # |   +93 unexpectedly easy problem set. appears as if we are participating in a DIV 3 contest
•  » » 4 years ago, # ^ |   0 if the difficulty level was "standard" ANY of problems A,B,C,D could be Div2. A or at most Div2. B.Because no specific algos were needed,and problem C had some tricky coroners and wasn't actually difficult
•  » » 4 years ago, # ^ |   0 Well, easy problems don't matter. If you can't solve them quickly your score will not be sufficient enough. That's the advantage of dynamic scoring. But, today's dynamic scoring seems not so effective! I've taken more time to solve A,B,D than yours. But, my ranking is so close to yours!!
 » 4 years ago, # |   0 Thanks for nice contest for Div.2. There were interesting problems. Maybe pretests could be a bit weaker.
 » 4 years ago, # |   0 Why am I still unrated after this contest? (It is my first btw)
•  » » 4 years ago, # ^ |   0 You will get rating after system tests and rating recalculation
•  » » » 4 years ago, # ^ |   0 Thanks!
 » 4 years ago, # |   0 What was the 7th pretest for C :(..Kept getting WA
•  » » 4 years ago, # ^ |   0 It was DP. You should initialize 0th tree at -infinity(-10^14) and n+1th tree at infinity.
•  » » » 4 years ago, # ^ |   0 Well, that's obvious. But what about other trees, could you please explain to me? I couldn't code a working solution.
•  » » » » 4 years ago, # ^ |   0 Either a tree doesn't fall at all, or falls on left or right. So, 3 arrays to hold these results.
•  » » » » » 4 years ago, # ^ |   0 Actually when the tree falls on the left or doesn't fall generates the same sub-problem!So you can use only 2 arrays :)
•  » » » 4 years ago, # ^ |   0 I did C in a greedy manner: keep 3 arrays(one for trees position, one for trees height and one for where will the rightmost part of the i-th tree be). I initialised the rightmost part of the first element as the position of the first tree and the (n+1)-th with INFINITY. Then for each tree starting from the second to the last i check first if i can make it fell to left(using the rightmost array), if i cant i check if it can fell to right and it is still impossible i move to the next tree without increasing the amount of trees that can be cut.PS sorry for bad formating.Here is my source code: CODE
•  » » » 4 years ago, # ^ |   0 Actually it could be solved in a greedy way without any extra space.The first tree is toppled to the left and the last to the right.Keep a variable "lastUsed" initially equal to the position of the first tree.For trees [2, n-1] try to topple it to the left. If not possible try toppling it to the right and update to x[i] + h[i]. If it couldn't be toppled or it was toppled to the left "lastUsed" gets updated to x[i].My code
 » 4 years ago, # | ← Rev. 2 →   +11 Hmmmm.... either I drunk too little coffee or I have to participate in Div3 contests....
 » 4 years ago, # |   +31 It was a GREEDY contest!! :D
 » 4 years ago, # |   +15 A car is good if it turned over in no collision --> RIP English
•  » » 4 years ago, # ^ |   +1 What's the problem?
•  » » » 4 years ago, # ^ |   +4 A car is good if it was not turned over in any collision
 » 4 years ago, # |   +9 This was easier than Codechef Lunch time contest, which is supposedly designed for school students.
•  » » 4 years ago, # ^ |   +11 Have you actually participated in those, because I certainly feel that overall level of lunchtimes is at par with Div2 contests(old ones when I used to participate :)) and most of the times even difficult than that.
•  » » » 4 years ago, # ^ |   0 Yes, I have and I believe that last two problems of Div2 contests are harder than last 2 problems of lunchtime. The level of first three problems are more or less the same. But today first 4 problems were very easy and 5th was direct implementation.
•  » » » » 4 years ago, # ^ |   +6 I don't think you can judge the difficulty of problems which you can't solve in contest time. Just because the solution uses a familiar concept or uses less code doesn't necessarily mean it's simple. Have you solved Div2 E or the last problem from Lunch Time contest?
•  » » 4 years ago, # ^ |   +14 IOI is also for school students. Do you think it's easy?
 » 4 years ago, # |   0 Codeforces favors C++ over Java too much. I cant make E accepted with Java, got TE all of the time. The algorithm I implemented is exactly same with accepted C++ version.
•  » » 4 years ago, # ^ |   +3 There have been many Java AC too ,so probably your implementation could have been slightly slow ?
•  » » » 4 years ago, # ^ |   0 Could you please give me a link to Java source of whom got AC? Many thanks!
•  » » » » 4 years ago, # ^ |   +3 http://codeforces.com/contest/545/submission/11164079Also you can search by language as parameter too ,if you want to see more solutions :)
•  » » » » 4 years ago, # ^ |   +2 I think the status filter is good enough for what you want: And here are some of the source who got AC with Java: http://codeforces.com/contest/545/submission/11161969 (fastest in Java 7) http://codeforces.com/contest/545/submission/11163503 (fastest in Java 8)
•  » » » » » 4 years ago, # ^ |   0 Thank a lot! It's very useful.After looking deep into the solution, the trick for Java developers is re-implementing ConsoleIO and PriorityQueue (Heap).It is still a bit favor for C++ developers, since the built-in STL is pretty good already.
 » 4 years ago, # |   0 Only 3 "Failed System Test" solutions in my room. wow... XD
 » 4 years ago, # |   +3 Can anybody explain this?Task D. Sort and calculate got AC. But in query 1 1 1 1 1 1 1 5 two satisfied. But in query 1 1 5 1 1 1 1 1 1 three satisfied. Where am I wrong?
•  » » 4 years ago, # ^ |   +1 Because we sort the array first, so both of them will produce 1 1 1 1 1 1 1 5. The answer should be three: serve the first two, and serve the last person.Hope it helps!
 » 4 years ago, # |   +10 what an awful contest ?! Everything depends on problem E!
 » 4 years ago, # |   0 What did solve task C? I am build dinamic and found states with binary finder... Why it was not correct: http://pastebin.com/PHVYYqWC ?
•  » » 4 years ago, # ^ |   +1 o_O what a grammar ?!
 » 4 years ago, # |   +3 The pretest was so strong i got two times WA in problem C&D and at last AC.I scanned the whole c++ coders of my room and there was no sign of mistakes in their codes :D
 » 4 years ago, # |   +3 My room 1016, NO successful hacking, NO system test fail. :|
•  » » 4 years ago, # ^ |   0 The same situation is in my room, 1014.
 » 4 years ago, # |   -23 rasoolll and Behnam.B cheated look at their submissions : 11152882 and 11153982 they are also from same university (shame on ferdowsi university of mashhad)
•  » » 4 years ago, # ^ |   +28 Code doesn't look 100% similar. Their outputs on the third test differ also.
•  » » 4 years ago, # ^ |   +8 This is Common Problem With Short code. Two code can Have similar Idea ( Even These Code seems to be same but not Exactly Same). And another thing is, Generally Student from same University have closer Idea about many problems.
 » 4 years ago, # |   +2 I am new to this site, and this was my first ever coding contest. I managed to solve 3 problems getting a rank of 1802. However, I cannot see any rating being alloted to me. Can anyone explain the reason for this, and how I can earn a rating.
•  » » 4 years ago, # ^ |   +2 System testing wasn't finished. It is finished now. Your rating's 1448, gratz on your first contest!
•  » » » 4 years ago, # ^ |   +3 Thanks, I also wanted to know that few people were awarded more marks for certain questions, and I lost out on few points. For example Problem #1 was of 500 points, where as I was awarded only 408 points, even though I didn't fail any submission. I read somewhere about hacking other people's code and some room concept. Can someone explain me my roles about hacking and what am I supposed to do in a room.
•  » » » » 4 years ago, # ^ |   +4 you get less points if you take more time to solve. If you are sure of your solution you can press the lock button on the dashboard. Then you can view others' solutions to that problem by clicking the score in the room. If you find a mistake in their code, give a test case which satisfies constraints and gives sub optimal answer wwith their code. You get +50 if their code gives wrong answer and -50 otherwise. Also, if you click the lock, you cant resubmit for that problem.
•  » » » » » 4 years ago, # ^ |   +3 It is actually +100 for correct hack.
 » 4 years ago, # |   +6 Finally into DIV 1 (purple) after almost a year on CF :D
•  » » 4 years ago, # ^ |   +3 Congrats
•  » » » 4 years ago, # ^ |   0 Thanks.
 » 4 years ago, # |   0 Answers to both of my wrong submissions (WA on pretest one in Problem A and Runtime Error in Problem D) is showing correctly on my computer. anything i am missing here?
•  » » 4 years ago, # ^ |   0 When a[i][j] == 3 || a[i][j] == 1 you should skip entry. i cant understand your code seems like you do the same for a[i][j] == 2 and it give WA.
 » 4 years ago, # |   +42 In my opinion, problemset was like A-B-B-B-D, but it's just my opinion.
•  » » 4 years ago, # ^ |   +20 A A B A D in implementation imho
 » 4 years ago, # |   0 Can anyone tell me why this solution gave WA for test 11 question C? I used DP where prev=0 means previous tree wasn't cut, prev=1 means previous tree was cut to left, prev =2 means previous tree was cut to rightLINK
•  » » 4 years ago, # ^ |   0 its simple because you assume tree number 2 will always be cut in code: int ans=1+func(2,1); ans=max(ans,1+func(2,2));
•  » » » 4 years ago, # ^ |   0 No, I am assuming that tree 1 will always be cut to the left (this is optimal, I know). ans=max(ans,1+func(2,2)) means tree 1 is cut to right. func(i,prev) means I am checking for tree i and I have solved for i-1 trees and (i-1)th tree was cut to prev.
 » 4 years ago, # |   0 I tried to solve the problem E using Dijkstra modified. It is my aproach: Save the parents of each node using dijkstra create a toposort for the directed graph of parents for each node select the parent with the minimum weight. I get WA in the 8th case. The test case is very large and I cant debug it...Here is my code. I read several comments and found some similar ideas. can anyone help me? (sorry for my poor english) thanks in advance
•  » » 4 years ago, # ^ |   +2 Try to change distance (vector dist and priority_queue) to long long :)
•  » » » 4 years ago, # ^ |   0 Thanks a lot!!! long long vs int I try to don't forget it...
•  » » 4 years ago, # ^ |   +6 ";" after if — delete it
•  » » 4 years ago, # ^ |   0 If statement has empty body
 » 4 years ago, # |   0 Too few successful hacks for A, B, C, D. Problems were so clear and obvious. Also, since I passed too many pretests, I was sure about getting accepted for first four problems!
 » 4 years ago, # | ← Rev. 2 →   0 :D
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone plz explain why problem E is not minimum spanning tree? I thought it as MST but I know second test case is not following my observation. So plz elaborate why my assumption is wrong.
•  » » 4 years ago, # ^ |   0 The MST does not satisfy the condition: "shortest-path tree from vertex u" ... " the lengths of the shortest paths from u to any vertex to G and to G1 are the same".Make some test cases yourself and you'll realize it. (Sorry for my bad english)
•  » » 4 years ago, # ^ |   0 You have to find a tree such that each vertex has least-possible distance from an specified vertex of the graph, not just being connected to the tree with least-cost.
•  » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # |   +4 Since this round was the author's first contest as a writer, I think there should have been a reviewer working with him. The problems were okay, but the complexities didn't match the score. Even though most of the problems were easy, I spent relatively too much time trying to solve them because the translation was not clear enough.
 » 4 years ago, # | ← Rev. 3 →   +14 Impressive result from latisel! http://codeforces.com/contest/545/...
 » 4 years ago, # |   0 My E solution failed because of long long. I legit feel sad now.11160086: initial submission11171670: correct submission
 » 4 years ago, # |   0 this round very easy ! =D
 » 4 years ago, # |   +1 has anyone did problem E with MST(kruskal's or prim's )?if yes then please explain the approach?
 » 4 years ago, # | ← Rev. 2 →   +1 This was my first CF round so I can't compare it with others, but I'd like to give the author some feedback: I enjoyed the round :), although it was an one hour contest for me (A, B, C and D). I couldn't finish E as well, although it was a nice problem, also the only difficult one. I think that C deserved more points than D? or D deserved less points than C?
 » 4 years ago, # |   0 that was challenging & easy-D contest! :) thanks.
 » 4 years ago, # |   0 Hi every one in problem C can explain in test #7 why answer is 5? which trees can cut down? I think tree x=1 to right, tree x=41 to left, tree x=55 to left, tree x=59 to right, and last tree with x=105 to right why my answer is wrong?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Your answer is almost right , but always cut the first tree to the left not to the right :)
•  » » » 4 years ago, # ^ |   0 I forgot tree x=68 so: tree x=1 to left, tree x=41 to left, tree x=55 to left, tree x=59 to right, tree x=68 to left, and last tree with x=105 to right we can cut down 6 tree and correct answer is 5! what's wrong?
•  » » » » 4 years ago, # ^ |   0 If you cut down tree x=59 to right, it takes segment [59;66]. If you cut down tree x=68 to left, it takes sement [61;68]. These segments are intersect, so we can't do this.