Sereja's blog

Codeforces Round #179
By Sereja, 12 years ago, translation, In English

Hello everyone!

Codeforces Round #179 will take place on Thursday, April 11th at 19:30 MSK. This is my fifth Codeforces round and I hope not the last.

I'd like to thank Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problems point values for 1 division will be standart. For the 2 division it will be: 500-1500-1500-2000-2500.

Gl & hf ! :)

Contest is over. I hope that problems vere interesting for you.

Division 1 winners:
1). marcina007
2). yeputons
3). gawry
4). KADR
5). enot110

Division 2 winners:
1). goie
2). Koblyk
3). Beriand

Ideas of the solutions are here.

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

Comments Comments (63)
| Write comment?
»
12 years ago, # |
  Vote: I like it -22 Vote: I do not like it

I can't wait to participate in the contest！！！！ I love codeforces!!!!

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

Good luck everyone

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

unfortunately I cant participate in this round but seems a great contest like all contest that Sereja have prepared.

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

good luck & good rating changes .

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

than contests author is Sereja my rating decreases, I hope that today this tradition will be destroyed;))))

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -51 Vote: I do not like it

Ignore this please. It wronged my meaning. . .

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

Where is score distribution?

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

    If there is any change in score distribution it will be mentioned before the contest. If not then the score distribution will be traditional.

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

    here.

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

"I strongly recommend you to read ALL the problems" — it does remind me of problems with close difficulty :P

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

    Sereja tells this before every contest written by him.

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

    Its hard to form problems with 7 different difficulty levels, where the only assessing tool for difficulty level is experience!

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

Great contest. Good Luck

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

very good system test speed thank you codeforces

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

Thanks for ultra-fast system testing :)

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

Very nice and balanced problem set...One of the best contest I have ever participated in...

Thanks

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

good problems.thanks.

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

Hello, during contest I had trouble with C and got TLE status...

I tried to use a map to group the number of times each query needed to be used and did a double for loop to update answer...

I also think that some sort of Range Query algorithm would help, but I can't yet implement one. Can someone help me and describe a possible solution for C Div2?

Thanks in advance,

Bruno

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

    Use Binary Index Tree or Segment Tree.

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

      I used delta encoding twice, less code + better complexity.

      one on the number of times that each operation executed, and the other to compute the new array

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

    Or you can just use idea described in this editorial (problem C, two last paragraphs). That problem also was about intersection the segments.

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

    There exist O(N) solutions.Considering each operator (Li,Ri,Di),we add a[Li] with Di and minus a[Ri+1] with Di,then the sum of a[1] to a[i] is the change of ith number.We can count the times of each operator in the same way.

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

      So considering 1st example of the statement, how can we apply that approach? If we add + d to left element and subtract d from right element, how can we find the updated array?

      3 3 3 1 2 3 1 2 1 1 3 2 2 3 4 1 2 1 3 2 3

      Array is 1 2 3...

      1st query is 1 2 1, so array stays now 2 1 3 (?) and so on? :/

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

        We should calculate the times of each operators first. For each [xi,yi],add 1 to b[xi] and -1 to b[yi+1] The sum of b[1] to b[i] represents the times of ith operator. Multiply each times to corresponding Di and then apply the method above.

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

Thanks a lot for this hard contest. Both of my codes for problem A and C got "Pretest Past" but now both of the are Red! Also Thanks for this fast system test.

Now I get that an unrated user won the contest again!

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

    what's your problem with them? I can't understand your wondering.

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

Great contest!Thanks to Sereja and Gerald!

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

Nice problems overall, I really like the idea behind the solution of problem D, very clean, although it was an odd round for me I solved A, C and E.

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

I failed problem C (div 2) and I cannot find where my solution went wrong. (I'm using segment tree). May someone help me ? Submission.

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

    I didnt really read your code but when i too got WA11 i had an error in vector/array's ranges. Do you use N and M sizes correctly?

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

My solution for problem A gets WA on the codeforces server but on my PC it's giving correct output for that case. Why is this happening? Could someone please help. Here's the code: http://www.codeforces.com/contest/296/submission/3511959

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

    In my blog you can find more about it. I faced this problem a few times. Here is a conversation about how to avoid this problems.

    HF & GL!

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

    int main() { cin>>n;

    rep(i,1,n) { int x; cin>>x;

    num[x]++;

    }

    rep(i,0,1010)
    //1010 is larger than your array's size, I change it to 1000 and your program output "NO" in "Custom Test"

    { D.x=i; D.n=num[i];

    if(D.n) v.pb(D);

    }

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

    rep(i,0,1010), but #define MX ( 1000 +3 ). I think this is the reason.

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

      Thanks a lot guys. Really silly mistake, should've been more careful :(

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

I tried to hack a code in problem C, which was plain brute force. I wrote a hack gen here but i got the error "FAIL Input can't start with empty line, but the first line is empty [validator wfval.exe returns exit code 3]"

Can any one tell the mistake so that I wont repeat it.

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

    Are you sure you've uploaded in source file field and not in input file field? I've got such error because of this previously and i see your source code starts with an empty line.

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

Tried to solve Div2 with DP lol. So much wasted time in debugging, and then saw the simple way :(. But this is one of those bad solutions that I am proud of http://codeforces.net/contest/296/submission/3514056

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

Div2 Problem C: I used the binary indexed tree approach...my code runs fine till testcase 11... Can any1 help me find my mistake? here's my solution http://www.codeforces.com/contest/296/submission/3512783

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

Thanks a lot for the contest! But:

Why didn't you make an illustration in Div 1 problem D?

It was annoying to read that text passage about sets/subsets, without an illustration showing what it's all about.

Even better (= more polite to contestants) would be to give a sample test like "3 3" or "2 3" and show (as pictures) all the valid caves in that pad.

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

    Next time I will note your advice. Thanks :)

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

could anyone please provide english version of the Ideas to problems page? If I click on translate button, only problem A is being translated to English, all other problems solutions are shown in Russian itself (they do not get translated). Thankyou.

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

Can anyone please explain the logic behind this solution of problem B of Div 2 ? I have having hard time understanding the dp state.

Thanks!

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

Can someone explain solution to probl C div 1 / E div 2 in more detail please ? Thanks!

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

    At first, note that we have only 2 type of people, let us call them "small" and "big" according to their weight. Assume some moment (state), then it can be defined by the number of "small" and "big" people on one shore and the position of the boat (the bank of the river it is adjacent to). Let the states be the vertices of the graph. It is understood that we can get from state to state with the help of the boat transportations. Therefore we have the directed (or undirected, it doesn't really matter) edge from one state to another if we can get from one to another by exactly one traversal. Obviously, the initial state is {0; 0; 0} (assuming we count people on the opposite bank, 0 corresponding to the initial bank, 1 — to the opposite), the final state is {n1; n2; 1}, where n1, n2 — the number of "small" and "big" people respectively.

    So the solution can be easily implemented by using breadth-first or any algorithm of finding the shortest path in the graph (because of quite small constraints). Moreover, you don't have to build the graph explicitly, you can do it implicitly (like me , for instance (: 3513759).

    The only thing you might still not understand is how to count the number of various ways to gain the minimal answer. Let us count in how many ways we can choose i people from x "small" ones and j people from y "big" ones. Obviously, that equals to C(x, i) * C(y, j), where C(n, k) = n! / (k! * (n - k)!). In such a way you can maintain another array that counts the number of possibilities and change it when you find the shorter path (assign the new value) or another path of the same length (add to the previous).

    Hope I made it at least a bit more clear to some contestants (:

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

      Great. Many thanks!

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

      Can someone please explain how we can have 72 ways for the following case?

      5 250

      50 50 50 100 100

      The minimum number of rides required are 3. My DP code(12225775) gives 46 ways and I have calculated it by hand as well giving the same answer.

      The possible moves are —

      1. Move 3 small people and bring 1 small person back — C(3, 3) * C(3, 1) = 3
      2. Move 1 large and 1 small and bring 1 small back — C(2, 1) * C(3, 1) * C(1, 1) = 6
      3. Move 1 large and 2 smalls and bring 1 small back — C(2, 1) * C(3, 2) * C(2, 1) = 12
      4. Move 1 large and 2 smalls and bring 1 large back — C(2, 1) * C(3, 2) * C(1, 1) = 6
      5. Move 1 large and 3 smalls and bring 1 small back — C(2, 1) * C(3, 3) * C(3, 1) = 6
      6. Move 1 large and 3 smalls and bring 1 large back — C(2, 1) * C(3, 3) * C(1, 1) = 2
      7. Move 2 larges and bring 1 large back — C(2, 2) * C(2, 1) = 2
      8. Move 2 larges and 1 small and bring 1 small back — C(2, 2) * C(3, 1) * C(1, 1) = 3
      9. Move 2 larges and 1 small and bring 1 large back — C(2, 2) * C(3, 1) * C(2, 1) = 6

      After either of these moves, all remaining on the left side are transported together to the right side in 1 ride.

      The total comes out to be 46. I am unable to find any other case. Can anyone please point out my mistake?

      UPD : Found the mistake. Was only considering cases in which a single person comes back.

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

Two coders form Poland in top 3! Nice to see :)

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

    Although one of them is having relations with the German oppressor!

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

Screencast of me solving this round.

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

Could you please write an English solution?

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

I can't understand the statement of porblem c in div2 , what's the query stands for ? How to explain the sample tests ?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

    Explanation of first testcase : Initially , the elements of array (a) are : a[1] = 1 , a[2] = 2 , a[3] = 3.

    We have three operations :

    operation 1 : 1 2 1 : increase every element a[i] with 1 <= i <= 2 by 1

    operation 2 : 1 3 2 : increase every element a[i] with 1 <= i <= 3 by 2

    operation 3 : 2 3 4 : increase every element a[i] with 2 <= i <= 3 by 4

    and three queries :

    query 1 : 1 2 , query 2 : 1 3 , query 3 : 2 3

    We have to execute the queries.

    by (a,b,c)--->(a',b',c') I mean the new state of the array after performing some operation.

    Query 1 asks us to perform operations 1 and 2. (1,2,3) ---> (2,3,3) ---> (4,5,5)

    Query 2 asks us to perform operations 1,2 and 3.(4,5,5)--->(5,6,5)-->(7,8,7)-->(7,12,11)

    Query 3 asks us to perform operations 2 and 3. (7,12,11)--->(9,14,13)--->(9,18,17)

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

What a pity! I just had a very little bug in Div.2 Prob A , or I would get a lot more Rating!

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

How I wish there is solution in English?

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

solution written in Chinese

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

    Looks good to me. At least, much better than the 'official' one.

    → Reply