csacademy's blog

Beta Round #6 — csacademy.com
By csacademy, 9 years ago, In English

Hello, Codeforces!

We are happy to announce that we're going to host a new contest at csacademy.com. Our Beta Round #6 will take place on Tuesday, May/31/2016 16:00 (UTC). If you want to take part in this round you need to register before the contest begins. Just like the previous two rounds, this will be a Div1 + Div2, with 6 tasks of varied difficulty.

Platform changes since Beta Round #5:

  • We added virtual contests. Now you can simulate a past round easily with a single click in the contests page.
  • Contestants source code is now public. Go to any scoreboard and click on a check mark.
  • The online editor now support an "Open file" button. No more copy paste when trying to submit.
  • We added some useful shortcuts to the editor. Hover a button to see its shortcut combination.

Contest format:

  • You will have to solve 6 tasks in 2 hours.
  • There will be full feedback throughout the entire contest.
  • Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
  • Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
  • Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

About the penalty system:

  • Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
  • Solutions that don't compile or don't pass the example test cases are ignored.
  • Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

We still recommend using an updated version of Google Chrome. If you find any bugs please email us at contact@csacademy.com

Don't forget to like us on Facebook, VK and follow us on Twitter.

EDIT: The ratings have been updated and the editorial has been published.

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

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Are the problems sorted by difficulty?

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

    Yes, but sometimes we can mess up, like in Beta Rounds #4 or #2

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

In the last Codeforces round i had an exam next day, but still didn't study it.

This time i have an exam at the same round time, Should I stay home to participate in the round, or go do the stupid exam ??? :D :D :D

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

    When is this exams thing ending

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

      take my advice and don't attend the university, join the army :3

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

Can anyone please provide a case where my solution for Perm Matrix fails?

My idea is as follows:

  • Process all pairs of neighboring rows.
  • Sort the first row.
  • Sort the second row.
  • For each element in the first row, find the minimum one in the second row that is bigger and assign to it and delete it. If there's no such element, assign to the minimum one from the second row and delete it.
  • If at any point, all remaining elements from the second row are equal to the one being processed from the first row, then there's no solution.

It seems it fails in a lot of cases, but I can't find what's wrong in that logic. Here's my code just in case -> C++ Code

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

      No, that one doesn't fail. I assign 1->2, 2->3, 3->1, 3->2.

      But I already found one that does fail:

      1 3
2 3

      First element bigger than one is 2, so next I assign 3 to 3. I still don't know how to greedily assign elements without repetition (and without using max flow, of course). I suck at greedy.

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

        I think on my example you'll assign 1->2, then 2->3

        Now you have 2 and 3 used from 2nd row, left with 1 and 3.

        So you can't match both 3's :) Anyway, your example is even simpler.

        Editorial has been published already; I also sucked on this one — I implemented some overcomplicated trash with idea : move from left to right, prefer picking element for which remaning valid ways to place minus remaining entries is smallest.

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

          You're right. It fails on your case too. Now you can see why I suck on greedy :P

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

Can someone explain me the detailed solution of this problem: https://csacademy.com/contest/beta-round-6/#task/exponential_game . I didn't understand the editorial. Thank you!

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

    If all the heaps' values have even frequencies, then whatever move the first player makes, the second player copies his move and wins. Now, if there is at least a heap value with odd frequency we can split the biggest of them to make all of the other odd frequency values become even.

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

Can anyone explain how the greedy solution in the editorial works for Perm Matrix? I have no clue.

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

    The greedy is: pick the most frequent element and match it with a different element on the opposite line and update the frequencies. In order for this to work, at any step there must be no element with a frequency of at least n + 1, considering we have 2 * n unmatched elements (according to Dirichlet, we couldn't make a matching if an element appears more than n times). Now, if the most frequent element has frequency of at most n — 1, then at the next step our condition remains viable as the maximum frequency won't be n. Now, if the most frequent element has frequency exactly n, at the next step this element will have frequency n — 1 which is ok. Now, if there would be 2 elements with frequency n, our only matching would be between them so there still wouldn't be an element with frequency n after the matching, so there is guaranteed that our condition remains viable during our greedy.

    → Reply