csacademy's blog

Round #66 (Div. 2)
By csacademy, 7 years ago, In English

Hello, Codeforces!

We are going to host a new contest at csacademy.com. Round #66 will take place on Wednesday, January/24/2018 15:05 (UTC). This round will be a Div. 2, affecting users with a rating below 1800.

Facebook event

Recently, Facebook has reintroduced the possibility of recurring events. If you choose "Interested" here, you will be notified before each round we organise from now on.

Contest format:

  • You will have to solve 5 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.

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

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

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

How to solve Flipping Matrix ?

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

    Create a bipartite graph where there is an edge from node i to j + n if aij = 1. If max matching in this graph is n, then it is possible to get a diagonal matrix, otherwise not.

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

      Sorry, but how to prove that if maximum matching is n, then it is possible to get a diagonal matrix ?

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

        Why is it possible — you can find the easy building coustruction Why is it impossible in the another way — use Holl theorem. It's easy to see that after changing columns or strings the theorem statements will turn out the same, and, thus, it won't be a N matching, but the diagonal matrix has N matching.

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

unofficial editorial: https://aleigorithms.wordpress.com/2018/01/25/csacademy-round-66-div-2-only/

→ Reply