### Sammarize's blog

By Sammarize, 6 years ago, translation, ,

Good day for all!

I invite you to participiate in the round 194. I'm author of it. It is my fourth round, but three previous ones were a long time ago: Codeforces Beta Round #79 (Div. 1 Only), Codeforces Beta Round #94 (Div. 1 Only), Codeforces Round #110 (Div. 1) (I apologize to the div-2 participants that I have mention only div-1 round, but even one link looks bulky).

This time you will help to boy Gerald cope with his problems as in the Codeforces Beta Round #79 (Div. 1 Only). This time his problems are so serious that he became coordinator of contests on the Codeforces, to be able to throw his problems to you.

I want to thank Gerald for he is great as coordinator. When you are work with him you are fill the everythink is under control. Moreover I want to thank Maria Belova for translation problems statements to the English.

This round will be held in unusual time — 12:30 Moscow Time.

Score distribution is standart: 500 — 1000 — 1500 — 2000 — 2500.

Thanks everyone for participation, welcom to editoral.

Congratulations to winners:
Division 1:
2. RAVEman
3. PavelKunyavskiy
4. Dmitry_Egorov
6. sy2006
7. mmaxio
8. AlexDmitriev
9. niyaznigmatul
10. RomaWhite

Separate note two Ukrainian participiants, who only solve all five problems!

Division 2:
1. IMOiguanas
2. savsmail
3. suyash666
4. AntiForest
5. kang205
6. jschneider2013
7. qwe123
8. langdamao
9. 9mmlitswe
10. Renkai

Following numerous requests to authors of rounds, I will talk something about me. My name is Valera Samoylov and I'm 24. I have graduated from SPb SU two years ago. Now I working on chemical layout of graphs and bringing up my little daughter together with my wife. Moreover last 8 years I'm teach schoolchilds math (and, last year, programming) in mathematical school in Saint-Petersburg. It all explains why I have not made rounds last time, although I have abound invented problems. Nonetheless I have found some time to make the round while my wife and daughter are on the vacation and schoolchilds on the vacation too. I hope you are will find that I not waste this time.

• +248

 » 6 years ago, # |   +101 One of the best announcement posts in CF :)
•  » » 6 years ago, # ^ | ← Rev. 3 →   -36 No,this announcement forgot to:1)Indicate that the round will be at unusual time2)Thank MikeMirzayanov for the systemlol :)
•  » » » 6 years ago, # ^ |   +9 There were probably enough "thanks for the system" after last round for quite some time forward
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +15 thanks for alerting us for the unusual time.I wasn't aware of this
•  » » 6 years ago, # ^ |   0 Oh I'm really looking forward to it!
 » 6 years ago, # |   +19 Glad to see someone coming back and help setting problems in codeforces. Shows the interest people have for the field :)
 » 6 years ago, # | ← Rev. 3 →   +24 Hope for a round with clear and easy-understanding problems' statement~Best ratings to all participants~
•  » » 6 years ago, # ^ |   +34 and "easy" english, so i don't have to open google translator :)
 » 6 years ago, # |   +25 wow !!! this contest time will be very comfortable for me and I hope for other. if contest time will be at 19:30 i didn't attend. I hope a lot of participant attend in this contest.Thanks codeforces !!!
 » 6 years ago, # |   -6 Good Luck & Have Fun !!!
 » 6 years ago, # |   0 Unusual time.Good luck to every one.
 » 6 years ago, # |   +23 "This time his problems are so serious that he became coordinator of contests on the Codeforces, to be able to throw his problems to you."I liked this :D
 » 6 years ago, # |   +14 Wow! Great memories from your last contest(#110)! Hope this one to be even better :) Thanks for setting problems again.
 » 6 years ago, # |   0 I hope your daughter and wife go on vacations more often,so CF users get to read more such awesome announcement posts.
 » 6 years ago, # |   +13 Qiu Qing Nve!!
 » 6 years ago, # |   +6 what will the scores for each problem? thx.
 » 6 years ago, # |   -6 is codeforces slow with me only or with all?
•  » » 6 years ago, # ^ |   +15 Well, i'm fine.
 » 6 years ago, # |   +43 I don't understand problem A and B T_T
•  » » 6 years ago, # ^ |   +14 fucked up english!
•  » » 6 years ago, # ^ |   +8 took 30mins (asking questions) to finally understand #B
 » 6 years ago, # |   +34 Problem statements are easy to read, but difficult to understand...
 » 6 years ago, # |   +10 I can't understand Problem C
 » 6 years ago, # |   0 For Problem B,what are the 3 points for the first example?
•  » » 6 years ago, # ^ |   0 x1=0,x2=1,x3=2 y1=0,y2=1,y3=2
 » 6 years ago, # |   +7 In problem D,What does "He moves each chip from its original edge to the opposite edge" mean? It means the point can only move in one derection?
•  » » 6 years ago, # ^ |   +1 more formally:if chip starts at (1,k) it should end on (n,k) and vise versaif chip starts at (k,1) it should end on (k,n) and vise versa
•  » » » 6 years ago, # ^ |   0 Also I think it means that it goes directly to its destination point. Otherwise the last given example would have a greater answer.
•  » » » » 6 years ago, # ^ |   0 yes,number of minutes=n-1
•  » » » » » 6 years ago, # ^ |   0 Number of minutes doesn't seem to enforce anything in this case, because there is no requirement to reach destination during this period. The only requirement is not to fail.
 » 6 years ago, # |   -6 what does problem C mean???
•  » » 6 years ago, # ^ |   +5 can't understand either...
•  » » 6 years ago, # ^ |   +2 I couldn't understand whether we should minimize or maximize something and what exactly is this something.
•  » » 6 years ago, # ^ |   +1 after 3 times of "wa in test 3",i guess it correctly....
 » 6 years ago, # |   +1 I wonder what does Problem C want??? Please explain test 2 in detail...
•  » » 6 years ago, # ^ | ← Rev. 3 →   +2 Case 0: Buyer has only 1 coins. Here he will be able to give exact sum. So, invalid. Case 1: Buyer has 1 and 3 coins. In this case, he will be able to give 4 (1,3). Invalid. Case 2: Buyer has only 3 coins. In this case ans is 2. Case 3: Buyer has coins with value more than 3. In this case ans is 1. As we have to maximize the number of coins. Ans is 2 from case 2.
 » 6 years ago, # |   +5 At problem A: It says: Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible.But for 13 the answer seems to be 5 ( 3 + 3 + 3 + 3 +3) when 15 can and must be obtained from the above statement from 9 + 3 + 3
•  » » 6 years ago, # ^ |   0 "Among all combinations choose the maximum of the minimum number of coins."
•  » » » 6 years ago, # ^ |   +6 I can't understand what you want to say.
•  » » » » 6 years ago, # ^ |   +12 One day an unlucky buyer came. He did not have the desired sum without changeThen he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible. What is the maximum number of coins he could get?And then they explain it again: We consider all the possible combinations of coins for which the buyer can not give Gerald the sum of n marks without change. For each such combination calculate the minimum number of coins that can bring the buyer at least n marks. Among all combinations choose the maximum of the minimum number of coins. This is the number we want.
•  » » » 6 years ago, # ^ |   -15 I know that you russians are the best at programming but please learn english
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Another confusion, for me, at problem A is for the second example: if the buyer had a coin of 9 marks, why would not he pay it? The answer in this case is one.
•  » » » 6 years ago, # ^ |   0 Because we are considering all cases where the buyer cannot pay the right amount, and choosing the one where the minimum number of coins payed by the buyer is the largest.In this case that occurs, for example, for a buyer with coins 3 3.
•  » » 6 years ago, # ^ |   0 If the unlucky buyer doesn't have any 9-coin (in particular, he only has 3-coins), he needs to pay with only 3-coins.
•  » » » 6 years ago, # ^ |   0 It says that "Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible". Therefore the buyer should have such coins in order to minimize the number of coins he gives away and it is better for him to have only a 9 marks coin.
•  » » 6 years ago, # ^ |   0 this two are different combinations. As the buyer MIGHT bring 5 coins of value 3, the buyer MIGHT need to use 5 coins even if he want to minimize the coin usage.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I was thinking about the same: Why not just give 3^x, where x is a large number, then the answer will always be 1.But you have to find the maximum out of all combinations.9 + 3 + 3 is a valid combination, 3 + 3 + 3 + 3 + 3 too, but it is also the maximum one.
•  » » » 6 years ago, # ^ |   0 What if we consider the sum 3^0 + 3^1 + 3^2 + ... + 3^k? There is only one possibility to pay it, with k+1 conis.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 9+3+3 is possible assuming the customer has a 9-mark coin.... 3+3+3+3+3 is when the customer has only 3-mark coins (possibly he may have 1-mark coins also) that's why 15 is the correct answer
•  » » 6 years ago, # ^ |   0 For each such combination calculate the minimum number of coins that can bring the buyer at least n marks.In this sentence, it seems that "number of coins" means "change".
 » 6 years ago, # |   +29 A bitset round!! My solution to both D and E used bitset to optimize brute force algorithm.
•  » » 6 years ago, # ^ |   0 Yes, I tried using bitset for E and some randomized algorithm, but the constants were too large so that I kept getting TLE until contest ends :(
 » 6 years ago, # |   -16 Please codeforces, i beg u for proper english...took me 1 hr to understand Prob c div 2
•  » » 6 years ago, # ^ |   -6 Although the question were pretty wonderful...But native english speakers face a lot of problem understanding the problem statements...
 » 6 years ago, # |   0 Thank you Sammarize for preparing this wonderful round and good problems. After Codeforces Round #193 I became disappointed but now I'm happy to participate in this round.
 » 6 years ago, # |   +3 trappy Div2 B…
 » 6 years ago, # | ← Rev. 4 →   +65 @ Codeforces team:Please, hire a proofreader with excellent English. TopCoder has misof that always checks all problem statements very carefully, word-by-word. Therefore we almost never have confusion in SRM statements.Sincerely,Contestant who took much longer time to understand problem A and B than to actually write the solutions
•  » » 6 years ago, # ^ |   +26 In my opinion, it is better to have someone whose native language is English but knows Russian, not the other way around. It usually works better.
•  » » 6 years ago, # ^ |   0 I can't agree more. In Codeforces Round #192 (Div. 1), I was really confused about problem A. And in this contest div.1 (Codeforces Round #194 (Div. 1)), problem A and B both have a poor expression in English.
 » 6 years ago, # |   +13 Fast system testing! Thank you.
 » 6 years ago, # |   0 Why can't I upload a data input file which larger than 256kb? Today I have lots of chances to HACK!!!! My data is not large enough to stop many solution which not pass the system test!
•  » » 6 years ago, # ^ |   +1 You should use the test generator
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +6 I'll try next time.
 » 6 years ago, # |   +5 nice contest :)
 » 6 years ago, # |   +53 yongheng5871 and sspa write the same code for problem D and E.D: 4179664 and 4179733E: 4184415 and 4185562
•  » » 6 years ago, # ^ |   +19 the same solutions by error202 and Williamacm (problems A, B, D, E):
•  » » » 6 years ago, # ^ |   +11 I found they are all from the same city.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 And their codes of C are the same too. sspa's code of A is the same as error202 and Williamacm's.@CF_team, What's your treatment to cheating?
 » 6 years ago, # |   +1 Fun Div 2 contest, but I really wish B's statement hadn't referred to the missing central point as "the average" (and used a test case in which it was) when it wasn't required to be.
•  » » 6 years ago, # ^ |   0 Totally agree with you, I was confused the whole time about whether the middle point shouldn't be included or the "average of the 9 points" shouldn't be included, which could be two completely different things
 » 6 years ago, # |   +5 Awesome contest ! But in Div 2 problem B You should have stated that points can be repeated or at least include it in pretests.
•  » » 6 years ago, # ^ |   +1 despite getting a wrong answer due to this, i don't agree with you, especially because they had mentioned "You do not have any other conditions for these points." in the problem statement. to all coders who failed B because of this, hopefully this will teach us to take NOTHING for granted in future, and read the constraints properly!!
 » 6 years ago, # |   0 My submission for D (4187066) gives WA on pretest 1, answer 1, but locally it gives 0, what could be the problem?
•  » » 6 years ago, # ^ |   0 In function possible, add "return false;".
 » 6 years ago, # |   +25 Number of people who passed each problem: C:14, D:135, E:33.I guess it will be better if we use dynamic scores.
 » 6 years ago, # | ← Rev. 3 →   +6 If the statement on A div 2 says that "You need to print n lines, on the i-th line print n integers", then, why people can print (n*n)/2 lines with only 2 integers each. I tried to hack this solution following the statement but he was right. Why? Thanks in advance.
•  » » 6 years ago, # ^ |   0 all whitespaces are considered equivalent...don't know why, but that's the way it is.also, before you attempt to hack a solution, just below the "Hack" button it says "be careful, whitespaces will not be considered" or something like that just to alert you to this possibility!! so from next time, read properly before hacking!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I guess the checker thinks any kind of whitespace (space, newline, etc) as a single separator. In particular, you can replace any space with newlines, and any number of them is considered a single whitespace. Yes, you can even output everything in a single line, with spaces separating them. If the checker uses scanf in C++ or similar, this makes sense; scanf considers any stretch of whitespaces as a single space/newline.EDIT: Sniped qq
 » 6 years ago, # |   0 Problem B div2 was really tricky! It seemed to be really easy(and it was), but a lot of people got hacked or wrong answer after system testing because of weak pretests.
 » 6 years ago, # |   0 Please explain why the answer for div2D 'pretest 6' is 4? Test case : 5 1 3 2 
•  » » 6 years ago, # ^ | ← Rev. 3 →   +2 0 0 1 1 01 0 0 0 00 # 0 0 00 0 0 0 10 0 0 0 01-chip, 0 — free cell, #- blocked sell
•  » » » 6 years ago, # ^ |   0 Oh right! Thanks. I kept thinking that according to rules we should only place on one side of the row, which was wrong. :(
•  » » 6 years ago, # ^ |   +1 One solution is 2,1 1,3 1,4 4,5
•  » » 6 years ago, # ^ |   +6 (1,4) (2,1) (4,5) (5,3)
•  » » 6 years ago, # ^ |   +1 Gerald will put the chips in cells (1,3) (1,4) (2,1) and (4,5).
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 you can put your chips on this cells to get 4 points (2 1) (1 3) (1 4) (4 5)
 » 6 years ago, # |   -8 Changed cin to scanf in problem D and got accepted :(
•  » » 6 years ago, # ^ |   +6
 » 6 years ago, # |   0 Some questions are hard to explain with pure words. It's better to attach simple graphs explaining the ideas. Also, give one "meaningful" example with a detailed explanation on how to arrive the output would be very helpful too. I suppose it doesn't take a lot of work from the problem writers.
 » 6 years ago, # | ← Rev. 2 →   0 Is the intended solution for D1-D is O(N^3 lg max{a}) + bitmask for speedup?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Editorial says only about O(n^2 log max) solution
 » 6 years ago, # |   -18 why does codeforce run test cases after the contest?that results in wrong answer even if pretests passes
•  » » 6 years ago, # ^ |   +1 1 for faster test during the contest 2 to give chance for participants to hack solutions
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 During the contest your solution is tested on a number of tests called "pretests". If your solution passed those tests it does not mean that it is correct. Therefore it has to pass the entire set of tests so that it may get accepted.
 » 6 years ago, # | ← Rev. 3 →   +21 A question about D,if we sort number in order,insert them from big to small,and use brute force to check.It can pass system test.But what is the upper bound of numbers inserted?I can construct a test case that should use O(nlogn) numbers.1101000101101000001101000001101000001101000001100000001100000001
 » 6 years ago, # |   +8 We can solve E in O(n^2 log n) in such a way (my solution wasn't accepted, I think that it is some bug in my code rather than in and idea). Firstly sort the points from left to right and let's do the binary search on result. For each point P we throw away points which lies closer to P than our actual value from binary search and we have to check if there are a pair of points that distance between them is at least that actual value. But we can find the furthest pair of points among them, there is a well-known algorithm for that problem, which runs in O(n) (recall that we sorted points from left to right at the beginning, so we have O(n) time instead of O(n log n)), so we are done.
•  » » 6 years ago, # ^ |   +5 I've got AC with the same idea. However, there are many O(N3) solutions optimized with bitsets which work much faster than this O(N2·logN) one.
 » 6 years ago, # |   +51 A funny solution about E. 4187525
 » 6 years ago, # | ← Rev. 3 →   -14 KADR — ZADR!
 » 6 years ago, # |   +33 I think you guys should seriously start improving the english translation of the problems. I find it unfair that some people can read the grammatically correct version of the problem in Russian while others have to read it in a translation that sometimes is far from perfect. Just a suggestion
 » 6 years ago, # | ← Rev. 2 →   +19 I got TLE at problem 333D - Характеристики прямоугольников in contest with 4185508, but I've resubmit the same code three times and got accept in 4188799, 4188820 and 4188829 for just 2214ms. I didn't use any random algorithm in the code, would it possible the new judging machine lead to the unstable result?
 » 6 years ago, # |   0 This is the one of the few contests where code reuse may be helpful :))
 » 6 years ago, # |   0 I think 333E - Летний заработок is not a good problem for 2500 point -- it's more like a 1500-point problem! I'd like to know the solution of author, because so many people use std::bitset to solve it and they get AC.
•  » » 6 years ago, # ^ |   0 Well, you can read the editoral.
•  » » » 6 years ago, # ^ |   0 Oh, O(n^2*log(n)) is more reasonable... Maybe you should set the time limit to 5 sec...?a O(n^2*log(n))-complexity problem is really embarrassed and hard to find data to TLE the O(n^3) or O(n^2*log(n)*log(n)) algorithm.
 » 6 years ago, # |   0 i solved two problems and went to sleep and when i woke up to see what happened i found that the first problem was accepted and the second one was skipped , why was it skipped ? :D :D any explanation :D
 » 6 years ago, # |   +25 I didn't take part in the contest, but was interested in language problems people reported. So I started to read A (fushar got +41 and +52 claiming that A and B were hard to understand due to poor English statements). I think I understand the description, although it would be hard to understand even if it was written in my native language. So I don't understand why do they blame English translations.I suggest instead of repeatedly complaining about statements in general, give at least one example of what was said in a wrong way and how it should be correctly and clearly. Otherwise I assume (and so should the contest author) that you just don't know English well enough and the translations are ok and the complains are void.
•  » » 6 years ago, # ^ |   0 Thank you for the support!
•  » » 6 years ago, # ^ |   +29 "Gerald is very particular to eight point sets" should instead be something like "Gerald is very fond of eight point sets". See the definition of particular to see why the confusion."...except for the average of these nine points" in this case case the problem was referring to the middle intersection point in both the x and y axis between the intersections of 3 horizontal lines and 3 vertical lines. Such middle intersection point does not necessarily has to be the average point."At least one of the chips at least once fell to the banned cell" could be, for example, "One of the chips falls in the position of any of the banned cells"And this are just a few examples when the real meaning of the sentence is somewhat hidden. There are other small mistakes that make the reading very rough like misuse or lack of articles for example.I know that you are not native english speakers (me neither) but I'm just saying that it would be nice to have a native english speaker proof-reading the problems so that we can all focus more on solving the problem than in understanding it.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   -8 All the examples come from B other problems, which I didn't read. Your remarks sound reasonable. Probably with A the case was different. I saw some people having problems with understanding the Russian statement of A too.UPD: In Russian version the same problem of "average" exists, so this is not translation problem. The rest of language imperfections doesn't lead to misunderstanding the problem, I think. So it kind of defends my point: the translations (although not perfect) are not real problem.
•  » » » » 6 years ago, # ^ |   +5 I was wrong. кроме средней из этих девяти точек средней may potentially mean average or middle. Definitely middle in this context. So it should be except for the average middle point of these nine points. And it was a translation problem. I hope this time I'm right.