Sereja's blog

Codeforces Round #204
By Sereja, 11 years ago, translation, In English

Hello everyone!

Codeforces Round #204 will take place on Friday, October 4th at 19:30 MSK. This is my eights Codeforces round and I hope not the last.

I'd like to thank Gerald, yvasyliv, Cenadar and Zlobober 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.

Problem point values for the first division: 1000-1000-1500-2000-2000.
Problem point values for the second division: standart.

Tutorial.

Gl & hf ! :)

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

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

Maybe a bit weird my question, but anyway, which are the numbers of the other rounds you have prepared? I just want to see the style of your problems.

Thanks.

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

    You can easily figure that out by checking his blog entries.

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

      You are absolutely right. Thanks a lot :D

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

I think it is "Friday, October 4th".

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

Two matches in one week. I like it.

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

I like Sereja's contests!!

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

    Sereja's contests like you too!!

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

i think you mean, Friday, October 4th at 19:30 MSK.

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

One of my friends (SeyedParsa) likes Sereja's contests because he improves his rate rapidly in Sereja's contests and I wish I can improve my rate in this contest too:))) Good luck everyone;)

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

    And now I should say I like Sereja's contests too!!
    Because I improve my rate after a long time in this contest!!
    Thank you Sereja:)

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

Static or Dynamic problem weights?

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

Hope the problems would be fun!

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

a question what is different of Div1 and Div2?(i am new here!) and how can i register for them?

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

    Div1 is for high ratings and Div2 for others ! Problems in Div2 are easier than Div 1 !

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

    http://codeforces.net/help I think you'll find your answer in point #15(What are the rating and the divisions?). You can check the rest of the answers for information since you're new here, you'll find it very interesting.

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

reading all problems strongly recommend :D

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

    Thanks Captain.

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

    Just out of curiosity... But why is this comment being down-voted so much?

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

      Maybe because the same is written in the blog post itself? That makes the post sort of a spam. At least I downvote exact cliches (those that don't have anything unique) unconditionally.

      Plus, the grammar's bad.

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

        I rather thought that these down-votes kind of ruin the harmony here at Codeforces... Most of the down-voted comments are posted by newcomers, they may simply want to express that they're here, that they want to be part of the Codeforces community... Maybe what they say contain nothing important but that's not a reason for down-votes... I would think that down-votes are for those who insult people or are impolite... Furthermore, about grammar... As there are people from all over the world, with most of them are from non-English-speaking countries, I think bad grammar is very understandable...

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

          I don't see many comments that are rude, but still not in the "should be deleted by admin" region. There are so few of those that if we really limited the reason for downvotes to be rudeness, the downvote button would just become a tool for trolls and it'd be better off removed. And that'd be weird.

          While I realize it's a bit cruel, writing can be good or bad, and I try to vote accordingly. It's also unfair if someone writes a good comment, and gets around as many votes as someone who copies a sentence from the text on top of the page.

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

            You're totally right... I just find it quite uncomfortable to see a lot of comments getting down-voted for no obvious reason... I really hope everyone can think before they vote like you do...

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

thx...I hope everyone will get high score;

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

Best author's (in my opinion) contest exactly on my birthday, really awesome present :) GL &HF everybody )

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

We have a national level university contest in Bangladesh tomorrow. Hope it would be a good warmup.

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

Good Luck for all~..

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

What about the score distribution? :)

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

seens to be a little bit hard? well, hope everyone can figure out all the problems && enjoy every contests:)

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

first time writing div 1 round

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

Wow... More than 4000 participants :D What is the record, by the way? :)

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

    we will be having acm icpc regional qualifications this month hence the increased number of participants :)

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

    Hope that doesn't affect on stability of the contest :)

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

Looks like no 500-points problem for Div 1 ... It may be thought round for me, first time participant @ Division 1 ... ;-)

Hope better results 4 everyone!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How solve problem C?

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

    Initially round down all the numbers. Now, you have to round up 'n' numbers. Choose as many as you can so that difference becomes less. Next choose as many as you can so that this minimum difference remains (by choosing integers). If still you haven't chosen 'n' numbers, choose the rest. 4667241

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

    It can be solved by DP:

    • DP[i][floor] : In the i-th number having floor numbers rounded down, what's the best answer?

    You should think how to calculate what's the best state as you just have two of them.

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

      I thought of this, but I thought that somehow the sign of the difference would matter. So I added another state and I calculated the maximum from the negative differences and the minimum from the positive differences. Can anyone explain why the sign doesn't matter? Especially when you can reach a state with both x and -x. Thanks!

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

      It can be solved linearly. Unless a_i=0 (discarding the integer part), it doesn't matter whether you round a number up or down. If you round up, you add 1-a_i to the difference. If you round down, you add -a_i. So you end up with the total difference being n-sum(a_i). Now, when a_i=0, rounding up gives 0, not 1. So you count the number of a_i=0 and count how many of those to round up. Subtract this number from n-sum(a_i) and you get the answer.

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

        Thank you for the answer! But it's still not clear for me: in the test case 0.000 0.500 0.750 1.000 2.000 3.000 the N - sumai becomes 1.750, which can't be transformed to the answer of 0.250 by substracting 1s...

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

          Sure it can. Note that at the end you have to take absolute value of the answer. As cfk said you need to count how many a_i=0 you round up. In this case 2, so |1.750—2|=0.250.

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

    i solve it using greedy, sadly, after contest :)

    we just need calculate the elements that have same value, whether rounding up or down, as this number have same value, it doesnt matter we treat this numbers as round up operation or round down operation, let's call this total of elements 'sama'

    assume we have sum of all rounded down numbers, let's call this 'h',

    then, iterate from i = 0 to n, and take the minimum difference of original sum and (h+i) that satisfy i+sama >= n

    http://codeforces.net/contest/352/submission/4676368

    sry for my bad english, hope you can understand

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

I guess many submissions (including mine) for Div1-A will fail because of small array size (2000+etc) :(

Liked the problem set (y)

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

I'm ready !!

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

There are 644 contestant in Div. 1 and there are almost 200 contestant who have no point.

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

My 2nd Div1, I am very happy with 57th. Thanks for the problems, I really liked them. If only I didn't do A so slowly!

What I am wondering is how people hacked A. I noticed that many people got caught on system test for A, but when I was trying to hack I couldn't find anything! So does anyone know common mistakes in A?

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

The contest is over and I still can't understand the statement of problem B. An explanation for the second test (not for the one with a single number in the array) would have been great ... Could somedody explain it?

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

    You look for each number in which distance (according to indices) they occur. In the second test case, 1 is on the indices 0-2-4-6, means distance 2. 2 occurs on indices 1-5, means distance 4, and so on. If there would be a number that doesn't have a repeating distance (for example indices 1-3-6), then you shouldn't print it.

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

    you need to check all the indexes of all distinct numbers can represent an arithmetic progression 2nd sample indexes of (1) are 1 3 5 7 arithmetic progression with diff =2 indexes of (2) are 2 6 arithmetic progression with diff =4 all other numbers are unique so print them with 0 as the problem states

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

    It means you should output like this:

    Whether the indexes of each number you choose in array meet arithmetic progression?

    Yes, output the common difference. (output 0 when the number appears only once)

    No, do not output this number.

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

    You have to output all the numbers x in the array such that their indices (the positions at which x are located) form an arithmetic progression. If x doesn't appear, then you discard it. If it appears once or twice, it's okay. If it appears more than once, you determine if the indices (say the 1st, 3rd, 5th elements are x) form an arithmetic progression. (To clarify, this is the criteria for if you output x, not how you actually solve it).

    For the second test case, only 1,2,3,5 appear so we only consider those. 1 appears at indices 0, 2, 4, 6 (0-based) and 2 appears at 1, 5. 3 and 5 appear only once. So all the numbers work. If 1 had also been at index 7, then it would not have been included as 0, 2, 4, 6, 7 is not an arithmetic progression.

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

Well, I really wonder can Problem C in Div.2 be solved by greedy algorithm?

Why did my solution come out like this in Test #11?

4671464

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

    I am surprised your submission worked on the first 10 tests, but I guess they are pretty simple. Anyway, the problem states that half the numbers must be floored and half must be ceiling, but you do not take this into account. Also, I don't think a greedy idea like what you are attempting would work anyway.

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

      Thanks for answering. My negligence.

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

Why was E E?

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

    I thought it was hard, but I was wrong :)

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

    I guess they may have a O(n^2) and hard solution and didn't come up with the O(nlogn) and easy one.

    UPD. After reading rng_58's solution, I found what I said is wrong. The O(n^2) solution is much easier to implement :D.

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

    Stupid question: why did all these solutions pass? It seems that for multiple equal elements we can take them with different signs, and this additional cost is not taken into account by straight-forward solutions. Is it possible to somehow exploit this effect and construct a challenge? Or maybe prove that this effect does not matter for some reason...

    Upd: in russian thread people say that it does not matter, since if we take some element with "+", it is impossible to take some next element equal to this one with "-". I wonder how many people actually thought about it during the contest...

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

      If we choose signs greedily, -x will never appear after x.

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

      Well, if you have multiple elements with same absolute value, in optimal solution they will have minus sign until some point and plus sign after that point. So there will be no inversions between them.

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

    Well, another reason that this task is not good for E is that the following "stupid" solution passed:

    1. Initally make all x[i] >= 0.
    2. For i = 1 to n: if we change x[i] to -x[i] and the answer goes better then do it.

    It will WA on test 11. But if we do the step 2 twice, it can pass the system test: 4673192

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

      Is it actually correct solution?

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

      If in step 2 we take "answer does not goes worse" instead of "answer goes better" then we even don't need to repeat this step twice)

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

      And why does it WA, when we do it just once?

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

        Because it's totally wrong. We could need to change several x[i], which would make the answer larger, and then change several other ones that would make it smaller. It just shows the weakness of tests.

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

      Someone can prove, that if there are no i, such that if we change ("update") x[i] to -x[i] the answer goes better, then we could'n improve the answer.

      This is such a natural type of statement, but in this particular case it's hard to believe in it. Of course, there is no guaranty, that after step 2 in our solution there are no such x[i] that we can update.

      The idea of proof: Call the operation "inverse" of x[i] is multipling it by -1. Assume the contrary: there are no such i, that if we inverse x[i] the answer goes better, but we could improve the answer inversing number x[i] = a and x[j] = b to -a and -b (in a general case we have to inverse k numbers, but for more clearness we take k = 2). Let us consider numbers ka and kb. ka = (number of inversions in initial array — number of inversions after inversing a to -a). The definition of kb is analogous.

      By assuming ka >= 0 and kb >= 0. Put the number of inversions = inv Case 1: ka > 0. When we inverse a and b, inv_new = inv + ka+kb. But we don't take in account pair (a, b), that can be "bad" (i.e. this pair is inverse), but (-a, -b) is "good". Then the number of inv_new >= inv + ka + kb — 1. Hence inv_new >= inv. A contradiction Case 2: ka = kb = 0. Let inverse a and b not simultaneously, but one by one. Then we can choose the correct order of chain of inversions (we inverse a, and then b OR b and then a), so that inv_new >= inv (Note, that a > b (elsewhere we have a contradition the same way as in case 1). Assume, that -a < b. First inverse a. inv_new = inv + ka = inv. Then inverse b. Since the pair (-a, b) is already "good" (and (-a, -b) too) and kb = 0, we have inv_new = inv. Again a contradiction. If -a < b is false then we will first inverse b, and then a)

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

      I did step 2 just once (with "answer gets better") and it passed. And I think that it is correct. Reason:

      We don't care about equal elements, as discussed here http://codeforces.net/blog/entry/9056#comment-147490 .

      If we have Pa, Pb;|Pa| > |Pb|, then |Pa| > |Pb| ≥  - |Pb| >  - |Pa|, so if we change Pb to  - Pb, the "inversness" (whether they made inversion, or not) of these two numbers doesn't change. Thus inversness of two numbers can only be changed by inverting greater of them. That means that effects of inverting numbers on total number of inversions are totally independent. So we can do it greedily.

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

while(true){ System.out.println("THANKS SEREJA"); } contest very-very good.

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

A question: when i run problem A(in Div2) in custom test, it works fine without error but when i submit it, it shows runtime error! what is wrong?

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

    In these line

            String line=sc.next();

    You only read one char and set it to the line string ...

    So the length of line string is 1 ...

    Run-time Error occur when you try to divide a number by zero or accessing a index less than zero or more than the size of array ...

    Here when index goes more than the 0 Run-time error occurs ...

            for(int i=0;i<n;i++)
        {
            if(line.charAt(i)=='5') f++;
            else z++;
        }

    But its not the only problem in your solution ... Find the others too ;)

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

      it works fine on netbeans, next() read a string. i will try to find why index goes less than zero or more than length,

      thanks,

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

        It reads one string but until the space .The numbers are separated by space so it reads only one number.

        You can easily check it by printing.

        Anyway you need better debugging , Asking such questions may consider as spamming here.

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

Can somebody hint towards the solution for Div 2 C?

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

Can anyone help me on Div2 B Why my code outputs negative numbers in Test#11 4670950

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

    I think sorting is not stable. 

    bool f(pii i, pii j)
{
	return (i.first<j.first)||((i.first<j.first)&&(i.second<j.second));
}

    May be the left of the "or" condition was not intentional. I think the following was your intention 

    bool f(pii i, pii j)
{
	return (i.first<j.first)||((i.first==j.first)&&(i.second<j.second));
}
    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A friend of mine made a correct submission for Div2 B during the contest but he found out it was "Skipped". What's wrong? This is quite unfair.

Here's the link: http://codeforces.net/contest/352/submission/4665780

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

    He made another submission on the same problem afterwards. For every problem, only the last submission is counted, and every submission before it (that doesn't get compilation error or WA on sample tests) gets -50 pts.

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

Why do contest writers offen misspell "standard"? I'm not blaming anyone, I'm just curious.

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

    Because of Russian word "стандарт" which means the same.

    and "т"is usually transliterated as "t"

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

When will the rank be updated ?

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

hey, can anybody tell me why my submission 4674576 for Div-1 A is giving wrong answer? thanks in advance.

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

    What is your algorithm? It would be easier to identify the source of the error then.

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

    got my mistake, thanks!

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

I wonder why this input (n = 2000 and 4000 zeros) was unsuccessful in hacking this code : 4663057, because the size of array in this code is 2010!

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

    Array overflow doesn't necessary mean wrong answer or runtime error. It means undefined behaviour.

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

    But in my case , it correctly gave a runtime error : 4662420

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

      Exactly. It "doesn't necessarily mean WA or runtime error". It's undefined behaviour.

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

Screencast

→ Reply