Sammarize's blog

Codeforces Round 194
By Sammarize, 11 years ago, translation, In English

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. riadwaw
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. jschnei
7. littlepanda
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.

  • Vote: I like it
  • +248
  • Vote: I do not like it

Comments Comments (109)
| Write comment?
»
11 years ago, # |
  Vote: I like it +101 Vote: I do not like it

One of the best announcement posts in CF :)

→ Reply
»
11 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

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

Best ratings to all participants~

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Good Luck & Have Fun !!!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unusual time.Good luck to every one.

→ Reply
»
11 years ago, # |
  Vote: I like it +23 Vote: I do not like it

"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

→ Reply
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Qiu Qing Nve!!

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

what will the scores for each problem? thx.

→ Reply
»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

is codeforces slow with me only or with all?

→ Reply
»
11 years ago, # |
  Vote: I like it +43 Vote: I do not like it

I don't understand problem A and B T_T

→ Reply
»
11 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I can't understand Problem C

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes,number of minutes=n-1

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

what does problem C mean???

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    can't understand either...

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it 
    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "Among all combinations choose the maximum of the minimum number of coins."

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I can't understand what you want to say.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        One day an unlucky buyer came. He did not have the desired sum without change

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

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

trappy Div2 B…

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it +65 Vote: I do not like it

@ 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

→ Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Fast system testing! Thank you.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

nice contest :)

→ Reply
»
11 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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

D: 4179664 and 4179733

E: 4184415 and 4185562

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

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

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

5 1
3 2
→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it -18 Vote: I do not like it

why does codeforce run test cases after the contest?

that results in wrong answer even if pretests passes

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +51 Vote: I do not like it

A funny solution about E. 4187525

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -14 Vote: I do not like it

KADR — ZADR!

→ Reply
»
11 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

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?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, you can read the editoral.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the support!

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it -8 Vote: I do not like 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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply