### Bug's blog

By Bug, history, 4 years ago,

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 — Stonefeang
2 — The_Watcher : Deemo
3 — Enchom : ImAlsoGay
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

• +81

 » 4 years ago, # |   -22 Awesome!
 » 4 years ago, # |   +11 Why don't you add a full gold contest, silver problems are easy ? Does the contest supports partial scoring ?
•  » » 4 years ago, # ^ |   +12 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
•  » » 4 years ago, # ^ | ← Rev. 4 →   -8 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 .
 » 4 years ago, # |   +73 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
•  » » 4 years ago, # ^ |   -6 cool , thanks! :D
•  » » 4 years ago, # ^ |   0 Thanks a lot!!! :) Great site!!!
 » 4 years ago, # |   +11 Cool idea! :)
 » 4 years ago, # |   +1 Great thanks Dwik.
 » 4 years ago, # |   -10 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
•  » » 4 years ago, # ^ |   +1 Hi I am new to Hackerrank and I wonder why I can't find the contest inthe contest list
•  » » » 4 years ago, # ^ |   0 It's private contest only those who have the link can get access to it .
 » 4 years ago, # |   +27 OK :(
•  » » 4 years ago, # ^ |   +8 you've dug your grave my friend :D no one miss with the rated contests :3
•  » » 4 years ago, # ^ |   +15 Yeah, I wanted to post the same comment this morning. Maybe if I had posted it before you, I could get some upvotes :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   -22 seems you have so many haters :v
•  » » » 4 years ago, # ^ |   +3 Seems it's not him who has so many haters :D
 » 4 years ago, # |   +9 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.
•  » » 4 years ago, # ^ |   +1 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.)
•  » » » 4 years ago, # ^ |   0 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 :)
•  » » » » 4 years ago, # ^ |   0 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
•  » » » 4 years ago, # ^ |   0 I also can't prove that my solution always leads to optimal results in fourth task) but it was accepted
 » 4 years ago, # | ← Rev. 2 →   0 It is over. Lets discuss.Please share if you have links to editorials.
•  » » 4 years ago, # ^ |   0 how did you solve the first one ???
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 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 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
•  » » » 4 years ago, # ^ |   0 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
 » 4 years ago, # | ← Rev. 2 →   +5 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?
•  » » 4 years ago, # ^ |   0 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
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » 4 years ago, # ^ |   0 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
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +5 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 :(
•  » » » » 4 years ago, # ^ |   0 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
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Okay, then some small modifications: 8 4 20 1 2 1 2 1 2 1 2 3 10 3 10 3 10 3 10 
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +8 I can't believe your solution passed. Here's a counter example:2 1 104 320 5
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 4 years ago, # ^ |   0 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 couponbased on what you said, shouldn't you buy the first cow with coupon!?
•  » » » » » » 4 years ago, # ^ |   0 why should i :/ i think u haven't understood my solution , that's my code link :D
•  » » » » » » » 4 years ago, # ^ |   0
•  » » » » » 4 years ago, # ^ |   0 He probably means: 2 1 10 4 3 20 5 
•  » » » » » » 4 years ago, # ^ |   0 Hacked! :D
•  » » » » » » » 4 years ago, # ^ |   +3 Successful hacking attempt
•  » » » 4 years ago, # ^ |   0 This solution is obviously wrong.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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
 » 4 years ago, # |   +13 The cf handle of those you mentioned:The_Watcher: DeemoGnadook: INVWVZEnchom: ImAlsoGay
•  » » 4 years ago, # ^ |   +39 sigh, only 8 months more until handle changes.
 » 4 years ago, # | ← Rev. 3 →   +3 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
 » 4 years ago, # | ← Rev. 2 →   +3 "...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
•  » » 4 years ago, # ^ |   0