KADR's blog

Codeforces Beta Round #13
By KADR, 15 years ago, translation, In English
Welcome all to Codeforces Beta Round #13, which will be held on Thursday, 6th of May at 18:00 MSK. I am an author of the problems.
I would like to thank Mike Mirzayanov who made this contest possible, Roman Iedemskyi and Andriy Maksay for helping to test authors solutions and Dmitry Matov for the translation of problem statements into English. Hope you will like the problems.

I hope that number 13 would be lucky for you!


UPD: Congratulations to Ivan Metelsky who became the winner, having solved all 5 tasks!
You can view the tasks here.
You can view the results here.

UPD2: I've added an editorial.

Some personal information:
I am a student of the first course of Kyiv National Taras Shevchenko University. I started training olympiad programming more or less seriously at the end of 10th grade (out of 11) after failing the national school olympiad and I don't want to give up now. After a year of practicing I've got gold on IOI 2009. Now I want to feel myself on the other side of barricades being an author instead of contestant. I'm glad to take part in the life of such a great resource as Codeforces. 

You can discuss the problems here in the comments after the end of the contest.

Announcement of Codeforces Beta Round 13
  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (52)
| Write comment?
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good Luck and Have Fun!
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thank you for difficult but interesting contest. I was glad to work with you.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Damm, only saw the B problem question faulting 15 minutes to the end, 8 wrong answers could be avoided!
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there any tricky case in B?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What is test 2 in this task?
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Do I understand task corretly? Each line is one of the segment drawn by Petya, isn't it?
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I wonder whether you had a Java implementation for D and if yes then what was the worst execution time on a single testcase. My Java implementation timed out despite all possible optimizations I was able to come with and then the same solution on C++ passed. [My solution was N^3 * M / 32 and I understand that it's possible to solve in N^3, but still it wasn't something I liked, despite even some straightforward N^3 precalculations took around 1 second on my PC.]

Overall, the problems were nice. Thanks for the round!
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My solution is O(N^2 *M + N^3). It also timed out due to some minor optimization issues.
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Seems it would be nice to have a higher time limit (as even this solution required additional optimization).
      → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    As a clarification of my previous post, "you" meant "problem writer and/or testers".
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Unfortunatelly, there was not any solution, written on Java for this problem. The complexity of my solution is O(N^2*(N+M)) and the worst execution time was 0.86s, so I decided that 2s will be enough to pass all test cases using any language.
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      I see, the decision is reasonable since your implementation being rewritten in Java would almost certainly pass within 2 seconds. But this almost doesn't leave any space for not so optimized solutions (generally speaking, this is not necessarily a bad thing, but for this particular problem it seems that C++ coders had a significant advantage).

      I think (and this is a question to Mike) it would be nice to have a kind of standard for setting time limits at Codeforces. For example, time limit must be at least twice the running time of the reference solution implemented on the slowest available language (or something like this).
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think setting the time limit to be twice that of the judge solution is a good idea, but lets keep it in C or C++.

        The slowest language here would be Ruby or Python (or maybe php?) - and they are pretty slow. 2x Ruby speed allowance might sometimes make slower C++ pass.
        → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think setting the time limit to be twice that of the judge solution is a good idea, but lets keep it in C or C++.

        The slowest language here would be Ruby or Python (or maybe php?) - and they are pretty slow. 2x Ruby speed allowance might sometimes make slower C++ pass.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Yes, you're correct, I haven't noticed we have Ruby/Python/php in the list of allowed languages. Though, as far as I understand, it's just impossible to solve some of the given problems on these languages.

          In this case, it would be nice to define the subset of allowed languages such that each problem is guaranteed to be solvable on each of these languages. Then the limit can be set based on the reference solution written on the slowest language from this subset. I'm not sure if it's a good idea to include only C/C++ in this subset.

          Anyway, I don't really mind how the time limits are set. It just would be nice to have a common publically available standard to set them.
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            А не лучше ли сделать так, как делают на NEERC? То есть установить разные ограничения по времени для C++ и Java, а остальные языки вообще оставить с пометкой "it is your own risk".
            Ещё раз повторюсь, что в идеале надо так тщательно подгонять размер входных данных (или даже корректировать формулировку задачи!), чтобы алгоритм с плохой асимптотикой не проходил даже при сколь угодно хороших оптимизациях.
            → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can you post Test Case 8 of Problem C?  Thanks.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My solution of B fails on the following test case, although it passed systests:
1
0 10 0 5
0 10 0 0
0 2 0 7
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    will answer be "NO"?
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yep, but my program outputs "YES" (I didn't check that the angle must be positive)
      → Reply
  • 15 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    That's pity that I have missed such test case.
    Anyways, you are lucky :)
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My solution that isn't accepted printf NO, maybe you put such test case with wrong answer?
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        The fact that your solution works correctly on this test case doesn't mean that it is correct :)
        My solution passes this test.
        → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My AC code also says yes.
    Rejudge will be dishonest.
    So, ignore contest results?
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could someone share the idea for problem C??
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    The main idea was dynamic programming:
    F(position,value) - number of steps you need to do in order to obrain a non decreasing sequence starting at 1 and ending at position, when the number in position is equal to value.
    F(1,value)=abs(a[1]-value), where a[1] is the initial value at first position.
    F(P,V)=min(F(P-1,W<=V)+abs(V-a[P])) for P>1
    The second key observation was that it is not optimal to change value of a[i] to value that hasn't been in the initial sequence. F(P,v1), F(P, v2), ..  and so on can be computed in linear time by updating value of minimum on each step and the whole complexity is equal to O(N^2).
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you tell me why the following gets Wrong Answer?

      Let v[0..n-1] be the input sequence.

      1. Let x = 0, cost = 0.
      2. If x >= n, output cost and exit.
      3. Let M be the minimum of v[x .. n-1].
      4. Let r be the largest index in [x, n-1] such that v[r] <= M.
      5. Let k be the number of indexes i in [x, r] with v[i] > v[r], and T be the number of indexes with v[i] <= v[r].
         Note that k + T = (r - x + 1).
      6. If k > T, then let M be the next larger element in v[x .. n-1] and goto step 4.
         If k <= T, then change all values in v[x .. r] to M, record the cost.  Let x = r + 1 and goto step 2.


      Thanks.
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you tell me why the following gets Wrong Answer?

      Let v[0..n-1] be the input sequence.

      1. Let x = 0, cost = 0.
      2. If x >= n, output cost and exit.
      3. Let M be the minimum of v[x .. n-1].
      4. Let r be the largest index in [x, n-1] such that v[r] <= M.
      5. Let k be the number of indexes i in [x, r] with v[i] > v[r], and T be the number of indexes with v[i] <= v[r].
         Note that k + T = (r - x + 1).
      6. If k > T, then let M be the next larger element in v[x .. n-1] and goto step 4.
         If k <= T, then change all values in v[x .. r] to M, record the cost.  Let x = r + 1 and goto step 2.


      Thanks.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Sorry for double post.  This seems to be a problem of CodeForces?
        → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        As far as I understood your solution only decreases the value at each point. It is obviously wrong then for test:
        5 5 1
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Hmm...the answer for that is 4, no?

          First it let M = 1, then r = 2, k = 2 and T = 1.  Next, M = 5, r = 2, k = 0, T = 3.  It will then change everything in [0, r] = [0, 2] to 5, or just change 1 to 5.
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            OK, I found a counter example:
            10
            1 2 3 4 5 6 5 4 3 2
             =(
            → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      [This is slightly off-topic, sorry for this.]

      I've seen a similar problem at BOI'2004: http://www.boi2004.lv/Uzd_diena1.pdf (third problem). The main two differences: the limit on sequence length is 1000000, resulted sequence must be strictly increasing. I've been thinking for quite a lot on that problem and still don't have any working ideas. If anybody has clues on how it can be solved, could you please post.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I guess you can assume at least one of the values in the sequence does not change when the sequence is strictly increasing?
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          Yes, we can assume this. More exactly, the solution has the following structure. Let the input sequence be a[0], a[1], ..., a[N-1] and we want to construct b[0] < b[1] < ... < b[N-1]. The solution consists of several segments (st[0], fn[0]), (st[1], fn[1]), ..., (st[k-1], fn[k-1]), where st[0] = 0, fn[k-1] = N-1, st[i] = fn[i-1] + 1. For each  segment i there's some index mid[i], st[i] <= mid[i] <= fn[i], such that each b[j], st[i] <= j <= fn[i], is equal to a[mid[i]] + (j - mid[i]).

          This property leads to O(N^3) solution and this is the best I was able to come with so far. Of course, something much faster is required...
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            I'm a bit lazy now but I think you need to iterate over each element and considering that element is not changed you need to update the other elements.
            The ones on the left and the ones of the right of the fixed element.

            - For example, If you consider the elements at the right of t[k]:

            If you consider the vector c[i] = t[i+1] - t[i] - 1 for each . Increasing an element j by 1 implies increasing c[j-1] by one and decreasing c[j] by one (and the same thing happens when you decrease element j). You need to modify all values such that c[j] >= 0 subject to 'k' being fixed. You can compute this by means of DP considering k (the element you fix) goes from n-1 to 1.

            You can compute the result by doing two passes one for the elements lying at the right and left of the fixed element.

            I don't know if this is correct yet but I will try to explain myself later.
            → Reply
      • 15 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        I have two sources, where you can read about it, but unfortunately only in Polish. One is a magazine called "Delta", where the task was described in 11/2007 by that BOI's winner;) The second is here: http://informatyka.wroc.pl/node/160, maybe you can try it with some translator. It's a full story of jakubr's start in some TopCoder Open round with similiar task :) 
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          That`s intersting, after the round I was just thinking about the same extension and when I saw the comments this question was here.

          Thank you for the reference, even with google translator it was a very good source of learning. But I couldn`t find the specific article in the magazine page, if you know how to get it in PDF or something like please tell me or Maybe I`ll just e-mail Filip Wolski xD
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            This particular article isn't on the website, as you have already discovered. If you e-mail me (through TC for example) I can give you a copy. I don't know if I can make it publicly available (put it in the web).
            → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you give test case #6 ?
      My solution is same but getting WA in #6.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Can you give test case #6 of problem C?
        My solution is same as maksay described but getting WA.

        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Maybe you have used int32 instead of int64.
          → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I can't figure this out :
      F(P,V)=min(F(P-1,W<=V)+abs(V-a[P])) for P>1
      What's W<=V ? What's W ?
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It should say F(P,V)=minW ≤ VF(P - 1, W)+abs(V-a[P])
        → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Let's suppose that we change values of a[i] in strictly increasing order of i. Then we have first to obtain value in position P-1 and then in position P. So F(P-1,W<=V) ( or see how adamax wrote more correctly ) is number of steps needed to get nondecreasing sequence starting at 1 and ending at P-1 with value equal to W, that should be less or equal to V to make the sequence nondecreasing of lenght P.
        → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there someone who can give me some tips about problem D and E?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    autor`s editorial http://codeforces.net/blog/entry/364 . Not loading now, but it will be fixed soon, I think :)
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It would be very nice if tests were published.
→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -13 Vote: I do not like it

I know this blog entry has been inactive for quite a long time. However, I recently heard there is an O(N log N) solution to problem C. Can anyone explain it?

EDIT: Here's a link: http://codeforces.net/blog/entry/18424#comment-234171

→ Reply