csacademy's blog

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

Hello, Codeforces!

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

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
  • +13
  • Vote: I do not like it

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

This round featured easiest D ever, a simple simulation AC'ed in 124ms!

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

    That's because tests were incredibly weak. If you did the same I did, it will time out with proper test set. Depending on your algorithm, either of the two following test cases will time out.

    • N = 100000, K = 99999, Q = 100000. Group i contains person i as representative and person 100000. Each query consists of the single person 100000.
    • N = 100000, K = 50000, Q = 1. Group i contains person i as representative and i + 50000. The query consists of all 100000 people.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I strongly believe that you are wrong.

      Both of these test pass extremely quickly for the solutions you call slow.

      For example, if you just check whether for each group whose representative is contained in the query, exist all the other people in that query and also just continue if the size of the group is greater than the size of the non-representative people in the query, in the worst case the algorithm will run in a linear square rootish complexity.

      If you however still disagree with me and think you are right, prove me wrong and post a case with all the constraints less than say 9, for which the solution above would've actually been quadratic. This should be a non issue for you with your confidence.

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

I'm anxious to read official solution for problem D. All solutions I checked time out with a proper test case, even those from the top of the scoreboard.

For example, Benq's solution fails with this case...

  • N = 100000, Q = 100000, K = 1. The only group consists of single representative person 1 and all the rest of the people. All queries consist of only one person: person 1.
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Every query can be processed with sqrt dec.

    Let S be the set of bands that have its representative in the query. Only bands in S can be disolved.

    The idea is to keep the number of members of every band in S.

    Let's call a person heavy if it belongs to more than sqrt(1e5) bands. Note that there can be at most sqrt(1e5) heavy people. So we can iterate over every band and remove all its heavy members given in the query.

    For light people we can just iterate over all the bands to which he belongs.

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

    So, top of the scoreboard is top-1.

    Sqrt-decomposition on the size of the query. If the size of the query is less then B, then check only those groups, whose representative is deleted, and if the size of the group is greater than the size of query, than it certainly cannot be deleted. Query of size sz is processed in O(sz2) time, total time is . Otherwise, just check all the groups.

    Also you can see that second solution isn't necessary, because first one also works in that time.

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

You don't write validators or what? How can it be that tests were incorrect?

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

    Please forgive setters for having a weak mind :)

    On a more serious note, that ussually happens when setters doesn't use a good tool like polygon ...Sometimes constraints change and you forget to run validator again

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

For C my solution gave 1 2 3 4 10 9 8 7 5 6 for test case 4 (10 14) which is correct but still it says incorrect. :|

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

    The question requires the permutation that is the smallest lexicographically. In this case, there is a lexicographically smaller permutation: 1 2 3 4 9 10 8 7 6 5.

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

Will the editorial be posted? I haven't seen any editorial in this contest

→ Reply