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:

1. KADR

2. RAVEman

3. PavelKunyavskiy

4. Dmitry_Egorov

5. RAD

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.

One of the best announcement posts in CF :)

No,this announcement forgot to:

1)Indicate that the round will be at unusual time

2)Thank MikeMirzayanov for the system

lol :)

There were probably enough "thanks for the system" after last round for quite some time forward

thanks for alerting us for the unusual time.

I wasn't aware of this

Oh I'm really looking forward to it!

Glad to see someone coming back and help setting problems in codeforces. Shows the interest people have for the field :)

Hope for a round with clear and easy-understanding problems' statement~

Best ratings to all participants~

and "easy" english, so i don't have to open google translator :)

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

Good Luck & Have Fun !!!

Unusual time.Good luck to every one.

"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

Wow! Great memories from your last contest(#110)! Hope this one to be even better :) Thanks for setting problems again.

I hope your daughter and wife go on vacations more often,so CF users get to read more such awesome announcement posts.

Qiu Qing Nve!!

what will the scores for each problem? thx.

is codeforces slow with me only or with all?

Well, i'm fine.

I don't understand problem A and B T_T

fucked up english!

took 30mins (asking questions) to finally understand #B

Problem statements are easy to read, but difficult to understand...

I can't understand Problem C

For Problem B,what are the 3 points for the first example?

x1=0,x2=1,x3=2 y1=0,y2=1,y3=2

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?

more formally:

if chip starts at (1,k) it should end on (n,k) and vise versa

if chip starts at (k,1) it should end on (k,n) and vise versa

Also I think it means that it goes directly to its destination point. Otherwise the last given example would have a greater answer.

yes,number of minutes=n-1

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.

what does problem C mean???

can't understand either...

I couldn't understand whether we should minimize or maximize something and what exactly is this something.

after 3 times of "wa in test 3",i guess it correctly....

I wonder what does Problem C want??? Please explain test 2 in detail...

As we have to maximize the number of coins. Ans is 2 from case 2.

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

"Among all combinations choose the

maximumof the minimum number of coins."I can't understand what you want to say.

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 themaximum 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.

I know that you russians are the best at programming but please learn english

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.

Because we are considering

all caseswhere 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.

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.

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.

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.

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.

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.

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

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".

A bitset round!! My solution to both D and E used bitset to optimize brute force algorithm.

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

Please codeforces, i beg u for proper english...took me 1 hr to understand Prob c div 2

Although the question were pretty wonderful...But native english speakers face a lot of problem understanding the problem statements...

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.

trappy Div2 B…

@ 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

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.

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.

Fast system testing! Thank you.

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!

You should use the test generator

I'll try next time.

nice contest :)

yongheng5871 and sspa write the same code for problem D and E.

D: 4179664 and 4179733

E: 4184415 and 4185562

the same solutions by error202 and Williamacm (problems A, B, D, E):

4176567 4181629 4179729 4184648

4176503 4184451 4179783 4186312

I found they are all from the same city.

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?

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.

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

Awesome contest ! But in Div 2 problem B You should have stated that points can be repeated or at least include it in pretests.

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

My submission for D (4187066) gives WA on pretest 1, answer 1, but locally it gives 0, what could be the problem?

In function possible, add "return false;".

Number of people who passed each problem: C:14, D:135, E:33.

I guess it will be better if we use dynamic scores.

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.

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!

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

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.

Please explain why the answer for div2D 'pretest 6' is 4? Test case :

0 0 1 1 0

1 0 0 0 0

0 # 0 0 0

0 0 0 0 1

0 0 0 0 0

1-chip, 0 — free cell, #- blocked sell

Oh right! Thanks. I kept thinking that according to rules we should only place on one side of the row, which was wrong. :(

One solution is 2,1 1,3 1,4 4,5

(1,4) (2,1) (4,5) (5,3)

Gerald will put the chips in cells (1,3) (1,4) (2,1) and (4,5).

you can put your chips on this cells to get 4 points (2 1) (1 3) (1 4) (4 5)

Changed cin to scanf in problem D and got accepted :(

You may be interested

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.

Is the intended solution for D1-D is O(N^3 lg max{a}) + bitmask for speedup?

Editorial says only about O(n^2 log max) solution

why does codeforce run test cases after the contest?

that results in wrong answer even if pretests passes

1 for faster test during the contest 2 to give chance for participants to

hacksolutionsDuring 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.

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.

11010001

01101000

00110100

00011010

00001101

00000110

00000011

00000001

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.

I've got AC with the same idea. However, there are many

O(N^{3}) solutions optimized with bitsets which work much faster than thisO(N^{2}·logN) one.A funny solution about E. 4187525

KADR — ZADR!

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

I got TLE at problem 333D - Characteristics of Rectangles 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?

This is the one of the few contests where code reuse may be helpful :))

I think 333E - Summer Earnings 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.

Well, you can read the editoral.

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.

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

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.

Thank you for the support!

"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.

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.

I was wrong.

среднейmay potentially mean average or middle. Definitely middle in this context. So it should beexcept for the. And it was a translation problem. I hope this time I'm right.~~average~~middlepointof these nine points