ikatanic's blog

COCI Round 3 Season 14/15
By ikatanic, 9 years ago, In English

Join us on Saturday, November 29th, 2014 for the third round of COCI!

Click here to see when the coding begins in your timezone!

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

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

blah blah blah (so that this blog goes to recent actions)

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

How to solve the 4th problem(120 points) ? How to obtain the best and worst rank for the contestants ?

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

    The idea is to find for each contestant how many contestants will beat him for sure and how many contestants will he beat for sure. It can be done with 2D Binary indexed tree in O(N* log^2 N) :)

    Edit: It's not log^2 N, it's actually log^2 700 so let's say O(N * 20).

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

      We can actually use a 1D BIT and accomplish the same thing. Just sort the contestants by score in contest 1, and iterate through the list while updating the BIT with the score from the second contest.

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

        Actually , We don't need neither 2D BIT nor 1D BIT , 2D partial sum is enough because the array is only 650*650 and we don't need to update it.

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

          Yes, I saw what did Xellos write and now I'm asking myself why did I use BIT :D :D :D

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

    For a fixed person p, best rank: all that have strictly more points in the previous round have higher ranks total; if they all get 650 and p also gets 650 (anyone else gets 0) in the 3rd round, then nobody else will be better than p.

    Worst rank: anyone that has at least as many points as p in at least one contest (except p) can get 650 in the 3rd contest and be better, with one exception: if p has 650 in that contest and that other person has 0.

    You can compress everyone into a 651 × 651 table, then count in O(6512) the number of people better/worse in both contests and compute the answers directly from that (+ checking the special case).

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

2D BIT submitted in the last 30 seconds!(problem D — COCI)

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

in problem C i wanted to find the perimeter by doing this for every component ans += MaxLen(max length of component)*2 + R(rightmost) — L(leftmost) + 1 so any ideas what my problem is

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

Can someone help with problem COCI please?
I can't find out what is wrong with my code.

PS I guess only problem is with the way I calculate lowest possible rank (as all mismatch element numbers are even).

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

    The way you calculate lowest possible rank is wrong. If person A gets 650 and x points in two previous rounds and there are D people who get (0, x), the worst rank of person A will be increased by D, not the number of all people getting from (0,0) to (0,x) as you do.

    Secondly, Fenwick tree doesn't work with index 0, so be careful!

    This code is Accepted: http://ideone.com/hlnoGb

    → Reply