Bug's blog

IOI Training Contests

By Bug, history, 9 years ago, In English

Hello , this year i qualified to the IOI , so to get ready for that i think the best way is participating in contests but as everybody see the ioi style contests are so rare , so i decided to add an old contest (USACO , COCI , COI , etc...) every three or four days and participate on it.
so i'm going to invite you to join me and participate on those contests .
i will add the contests to Hackerrank , and i will post the time and the description here on codeforces .

the first contest will be held on Apr/19/2016 at 18 MSK , the contest's duration is 4 hours and the problems are from USACO 2012 February Contest there will be four problems 2 gold and 2 silver .
the contest URL : https://www.hackerrank.com/ioi-training-contest-1
let us practice together :D
have fun and good luck :)
UPD: 15 minutes to go :) :D
UPD: the contest has finished :D
congratulation for :
1 — Radewoosh
2 — The_Watcher : Deemo
3 — Enchom : Enchom
4 — the_art_of_war
5 — IMAN_GH
6 — Gandook : INVWVZ
i think that i'm not appearing on the standings :v maybe because i'm who added the contest , my handle is superior1 and my score is 344.4 :D , https://www.hackerrank.com/contests/ioi-training-contest-1/compare/superior1/superior1

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

Comments Comments (47)
| Write comment?
»
9 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Awesome!

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

Why don't you add a full gold contest, silver problems are easy ? Does the contest supports partial scoring ?

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

    Some of the harder silver problems aren't easy, and are often equal to average gold problems. Also note that some of the easier gold problems are as difficult as the average silver problems. What division a problem is in is not an absolute measure of its difficulty :P

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

    good coders find the gold problems interesting for them .
    new coders find the silver problems interesting for them .
    so everybody gonna find interesting problems :D .
    and you will find a lot of useful ideas in the silver problems :3 :D
    yes it supports partial scoring , you will take 10 points for every accepted test .

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

have you seen my IOI online archive on contest.yandex.com/ioi? Check it out! Send a feedback message if you will see any mistakes

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

Cool idea! :)

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

Great thanks Dwik.

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

For those who aren't used to participate on hackerrank contests , i've made test contest you can find it here https://www.hackerrank.com/contests/ioi-training-contest-test-contest it's opened forever :D
try everything you want :D

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

    Hi I am new to Hackerrank and I wonder why I can't find the contest in
    the contest list

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

      It's private contest only those who have the link can get access to it .

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

OK :(

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

    you've dug your grave my friend :D
    no one miss with the rated contests :3

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

    Yeah, I wanted to post the same comment this morning. Maybe if I had posted it before you, I could get some upvotes :(

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

    seems you have so many haters :v

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

I want to tell you thanks because it was very good training for me and I realy liked tasks. And when the contest will finish I am for to discuss problems here.

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

    I look forward to an explanation for the coupons task...

    After thinking for over an hour, I gave up and looked up the original USACO site with the solution. It's a really nice solution, it sounds right, but I can't really prove it always leads to optimal results (and the editorial just says "this solution is clearly optimal" with very minimal reasoning).

    (Do wait until the end of the four hours before answering of course. :) I'm just asking now because I won't be here to post when it ends.)

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

      you should keep trying until the end of the contest my friend :) maybe you will have to think for 5 hours on some problem in the IOI :D :)

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

        Sure, but with 3 actual hard problems for 5 hours, if I have only one task left and I've thought about it for over an hour, the contest is probably over :P

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

      I also can't prove that my solution always leads to optimal results in fourth task) but it was accepted

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

It is over. Lets discuss.

Please share if you have links to editorials.

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

    how did you solve the first one ???

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

      I used a scan line. Sorted all points for x coordinate and iterate. If it is starting point I add new interval {Y1[i],Y2[i]} to set. If it is point of end I erase interval {Y1[i] ,Y2[i]} from set.

      And on every step I count the area of rectangles. I iterate through set and count area. If our pair <Y1[i] ,Y2[i] > we count the area of this rectangle and remember that we end on the value Y2[i] and we don't count the area of recrangle which is under Y2[i].

      Sorry for my english and not good editorials. Here is code. Maybe it will help you

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

      I used a technique called coordinate compression — basically, you put all X coordinates that appear in the data into a sorted array, then do the same for the Y coordinates. These coordinates define sort of an irregular "grid".

      If you take two adjacent X coordinates and two adjacent Y coordinates, they form a rectangle that is either completely covered with grass or completely free. This means that you can create a two dimensional bool array, storing whether each area is free or not.

      I started with the bool array full of "false". For each rectangle, I found the incides of its coordinates in the sorted coordinate list, then marked the corresponding elements of the bool array "true", adding their area to the sum if an element had been "false" before.

      My code here

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

How to solve Cow Coupons?

The best I could come up with was a O(n2·k) DP.

So, basically let DP(idx, todo, k) = minimum amount of money needed to choose todo elements from suffix [idx, n]. Answer will be maximum value of todo that is such that DP(0, todo, k) ≤ m. This will definitely TLE and only probably work for upto n = 500 or so. Can anyone provide clues to correct solution, or give some optimisations to this?

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

    I think it can't be solved by DP. You should use the greedy. I think I couldn't explain my solution.

    But here is code

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

    Simple Greedy would pass :D
    put the values of buying the cows without using coupons and the values of buying cows with coupons in one array , sort it and start buying cows from the left to the right but remember that if you bought a cow with coupon you can't buy it without a coupon :D

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

      Whaaat seriously. That is waay simpler than even the official USACO solution (which is not that complicated either, just seems hard to prove sufficiently).

      Does anybody have any solution with a proof of correctness?? :D

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

      Also wth, it's really easy to create a counterexample to that one...

      8 4 12
1 1
1 1
1 1
1 1
2 10
2 10
2 10
2 10

      :(

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

        my solution will pass on your "counterexample"
        make an array {1,1,1,1,1,1,1,1,2,2,2,2,10,10,10,10} you will buy the first 4 without a coupon so you will remove the next 4 (because you can't buy those cows again) , then you will buy the next 4 with coupon and remove the next 4 :D

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

          Okay, then some small modifications:

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

      I can't believe your solution passed. Here's a counter example:

      2 1 10

      4 3

      20 5

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

        this one passes too :D array {3,4,5,20} buy the first cow without coupon , remove the next one (because you've bought the same cow without coupon ) , buy the next one with coupon (you can't buy any cow with coupon after that) remove the last one .

        ans = 2 :D

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

          sort it and start buying cows from the left to the right but remember that if you bought a cow with coupon you can't buy it without a coupon

          based on what you said, shouldn't you buy the first cow with coupon!?

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

          He probably means:

          2 1 10
4 3
20 5
          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hacked! :D

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

              Successful hacking attempt

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

      This solution is obviously wrong.

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

    Here's the USACO editorial.

    As I said I don't see why it's always optimal. Namely, why can we always keep a cow that we added, even if we added it with a coupon and then revoked it? It seems correct, I can't find a counterexample, but it doesn't seem trivial to me at all.

    Edit: I think I figured it out. I ended up messing with inequalities a lot, but now I kind of see a short-ish, intuitive explanation. Let's take P and C values for the cow just added (j in the linked explanation), the cow we're revoking a coupon from (i), and another pair of variables standing for "any other cow" I called k. Basically, if there was a revoke, the i-th cow was also added with a coupon, therefore Cj > Ci. Since we chose to add the j-th now, Cj < Ck. Therefore Ci < Ck, so if you remove the i-th cow from the solution, you would just add it again with a coupon rather than give a coupon to anyone else; and you can similarly show that Pi < Pk, so you'd rather add it again without a coupon than add anyone else without a coupon. (Use the fact that Cj + (Pi - Ci) < Pk).

    Sorry if this wasn't very clear, I hope it points anyone in the right direction at least :D

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

The cf handle of those you mentioned:

The_Watcher: Deemo

Gnadook: INVWVZ

Enchom: Enchom

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

    sigh, only 8 months more until handle changes.

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

My codes for Cow Coupons and Nearby Cows.
UPD: My solution for Cow Coupons is wrong. It fails the test provided by Deemo above. Very weak test data!
UPD2: No my solution is correct, I just copied the test wrong. It's the same as in the tutorial :D

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

"...an old contest (USACO , COCI , COI , etc...) every three or four days and participate on it..."

Any plans for the next one yet? I really screwed up this one, so I'd like a "rematch" soon :D

→ Reply