csacademy's blog

Round #63 (Div. 2)
By csacademy, 6 years ago, In English

Happy New Year, Codeforces!

We are going to host a new contest at csacademy.com. Round #63 will take place on Wednesday, January/03/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
  • +41
  • Vote: I do not like it

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

I can not open csacademy.com ! it is ok now !

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

Did anyone except writer read the problem statement before the contest starts?

The statement of "Find Remainder" was bad.
"B[i] = A[i] mod K" means "B[i] is congruent with A[i] modulo K". If you want to "mod" to be recognized as an operator, you can swap lhs & rhs (or say "where mod is modulo operator").

Also, for "Graph Game" and "Root LCA Queries", why don't you specify how vertices are numbered? I guessed it from the samples.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

I just realized my submission should have got TLE but got AC on problem Root LCA Queries.

In one case I want to find the children of C which are ancestors of A and B. This could have been done in log(N) using binary lifting but I iterate over the children of C. This could lead to O(NQ) time, right? Or am I missing something?

https://csacademy.com/submission/1223809/

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

    Yeah, it is O(NQ) for graph like a star and all C = middleofthestar.

    You can do binary lifting or save starting dfs time and size for each child component and then run binary search over that sorted vector of components.

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

      Exactly, then the test cases were weak :(

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

        I did the same but used LCA to check if its an ancestor and it got TLE on TC10.
        Submission
        Fixed and it passed well within the time limit (271ms)
        Submission

        Not sure how yours passed.

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

      Isn't that a bit of an overkill or is my solution(that I did not yet implement) incorrect?

      My sol is that if C is not on the path from A to B it's obvious the answer is 0, if it is, find the size of the subtree of C that does not span towards A and towards B.

      If 1 is node A, 2 is node C, and 3 is B. 2 is connected to 1, 3 and 4, while both 1 and 3 are connected only to 2, then the size of that subtree is 2.

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

        This is what we're talking about, but how do you compute "find the size of the subtree of C that does not span towards A and towards B"? I can only think of getting the children of C whose subtrees contain A and B. There you could do binary lifting up from A/B or use BS over the children of C. If you just iterate over the children of C, it should get TLE (but mine got AC xD)

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

How to approach graph game question?

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

    Basic theorems on graph theory:

    • The sum of degrees over all the vertices is twice the number of edges. that implies
    • The number of vertices with odd degree is always even.

    Solution: The player that has to play with an odd number of vertices can always play (there has to be at least one vertex with even degree), so he wins.

    cout << N%2 << endl;

    easiest code ever haha, ignore the rest of the graph

    → Reply