csacademy's blog

Round #10 + prizes
By csacademy, 8 years ago, In English

Hello, Codeforces!

We are happy to announce that we're going to host a new contest at csacademy.com. Round #10 will take place on Saturday, Aug/06/2016 11:00 (UTC). If you want to take part in this round you need to register before the contest begins. Just like the previous rounds, this will be a Div1 + Div2, with 7 tasks of varied difficulty. We are honoured to have Yury_Bandarchuk as a problem setter.

This round is going to have some money prizes, as follows:

  • First place: 125$
  • Second place: 100$
  • Third place: 75$
  • Fourth and fifth place: 50$
  • Two more special prizes, each consisting of 50$. The criteria for the special prizes is not chosen yet, but we will make it public after the contest.

Also many thanks to HellKitsune for translating the tasks in Russian.

Platform changes since Round #9:

  • Added auto-complete to the editor
  • Worked on cross-browser compatibility
  • Added C# support
  • Small UI improvements

Contest format:

  • You will have to solve 7 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 [email protected]

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

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

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

You got the date wrong !

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

Any ideas about faster than O(NQ) solution for the last problem?

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

    We can divide all queries to blocks. After each block we want to recalculate all the values in time. This can be done if we will do DFS with all active queries in a treap (sorted by y). When we go down we should take only those queries whose y is not greater than y of the edge. When we answer the query we should iterate over the current block and check if we should apply particular query. It can be done similar to finding LCA in time (We have to precalculate binary jumps and minimum of edge values for each jump). Total complexity is

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

    The solutions have been posted. You can read the blogpost or open the task and check the "Editorial" tab.

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

How to solve Subarray Medians?

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

    O(n2). Iterate over the starting index start. Set the ending index end to the last possible index. Maintain a list of values (implemented with pointers to next and previous element), initially with all n numbers. Remove numbers before start. In the list keep a variable (pointer) mid — what is the middle value. This was how to do first for the fixed start. Then we must move end to the right, removing values and moving a value mid if needed.

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

    I think I have easier solution.

    Let's fix the median. Now iterate from it to the left and to the right, calculating balances (add 1 if element is bigger and -1 if it's smaller)

    Now, we are median iff the balance on the left=-balance one right

    code

    I've iterated in increasing order of medians but it's not actually necessary

    I didn't find all the answers one by one but it's possible if we store not sums in l/r arrays but vectors of all ends

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

      You are using the exact formula for hash, aren't you? :)

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

        Well, I use it, but it's easy to find all the answer using this method anyway

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

          Oh, right, I haven't think this way. Great solution!

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

    Iterate over the position of median. Build another array b[], where b[i] is 0 if a[i] == median, b[i] == 1 if a[i] > a[pos], and b[i] == -1 if a[i] < a[pos]. Now u have to count number of segs [L, R] such that L <= pos && R >= pos && sum[L..R] == 0 && (R — L) % 2 == 0.

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

This round we knew we had a hard last task, and that's why we tried to balance this with some slightly easier than usually first problems.

I think that giving a very hard problem doesn't mean you should make other problems easier than usually. It creates a big gap and thus strange results. It's maybe better to keep other problems standard and hope that some participants will try to solve the last problem before finishing others. Possibilities:

  • nobody solves the last problem anyway — it was too hard, apparently
  • somebody solves it but doesn't manage to solve all easier problems — awesome
  • somebody solves everything — sure, fine

Still, it isn't good if two last problems both require much coding. It would be nice to avoid that.

That being said, my opinion about the round is that first six problems were nice but easy. I didn't manage to solve the last problem and it was a bit sad/boring for me because other ones didn't give me much fun. Anyway, thanks for a round.

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

    What problems are you considering 'two last'? My solution to 'Expected Tree Degrees' is pure math and ~40 lines of code.

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

      Oh, sorry. I didn't mean "in this contest two last problems required much coding". I was writing about contests in general. I said that my opinion is: one very hard problem doesn't mean others should be easy but it's bad if two hard problems require a lot of code. This issue wasn't present in todays round of course.

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

For Xor Closure, could someone please elaborate this sentence from editorial a bit more? We create a system of binary ecuations where each bit has an associated equation and each element in the input is a variable.

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

I just saw the author solution of Expected Tree Degrees, and I believe mine's simpler. My dynamic programming is just:

The answer is . Anyone else with the same thing?

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

    Can you explain it?

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

      Well, I'm not good at probability problems so tell me if something doesn't make sense but:

      Suppose we have some tree of size N and we're adding a new vertex. Let's say that we connect the new vertex to some of the previously existing ones which prior to the connection had degree K. The increase of the formula is 2 * K + 1 + 1 (1 from the new vertex of degree 1, and 2 * K + 1 from the increase of the old one with (K + 1)2 - K2)

      So we get an increase of 2*K+2. Well, K is just some random degree so we can take the average of the existing degrees — which is independent of the tree structure. The average degree is . So the increase is simply and there's the formula.

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

My solution to 'Expected Tree Degrees' (informally).

I will denote 'Random variable equal to 1 if v is parent of u and 0 otherwise' as [(v) - (u)].

(all the calulations for non-root vertex, for root it is even easier)

[deg(v)] = 1 + Σv < u[(v) - (u)]

[deg(v)2] = (1 + Σv < u[(v) - (u)])2 = 1 + 2·Σv < u[(v) - (u)] + Σv < u[(v) - (u)]2 + Σv < u, w;u ≠ w[(v) - (u)]·[(v) - (w)]

where and

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

We'll try to do better on future rounds, sorry about the issues. We need to get more stable with developing the website so that we can have a dedicated team on tasks only. Since we're launched pretty recently, we have a lot of work we need to put into making the platform stable.

We some issues with the tests on the last task, so we decided to rejudge it.

So this isn't unfair to anyone, the prize you'll receive for this round will be the prize for the best rank you get before or after the rejudgement.

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

    Were tests invalid? If not then you shouldn't rejudge. Weak tests happen but trying to fail more solutions after the contests isn't right.

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

      Tests were invalid, since we said that the weights on edges are less than 10^5, but they were in int (they needed normalization). This is the reason for reeval actually. LHiC actually had a good solution that got WA incorrectly.

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

        Ok, got it. And well, input validators are very important.

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

The tests for the last task, Yury's tree didn't respect the constraints. The weights of the edges were actually up to 10^9, not 10^5 as mentioned in the statement. We normalised these values an reevaluated the task. There are two changes in the standings: LHiC and geniucos passed the new tests and they are now 3rd and 4th, respectively.

Besides the top 5, we announced two more special prizes. We decided to award them randomly in a similar fashion to the last round. Everyone who submitted at least one correct solution entered the lottery, except the top 5. The contestant placed 6th had a weight of 5, while the one placed 194th had a weight of 1, with everyone in between linearly distributed. This round's winners are Errichto and Egor.

Congratulations all and we hope to see you soon at Round #11!

→ Reply