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
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 22:27:11 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Awesome!
Why don't you add a full gold contest, silver problems are easy ? Does the contest supports partial scoring ?
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
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 .
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
cool , thanks! :D
Cool idea! :)
Great thanks Dwik.
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
Hi I am new to Hackerrank and I wonder why I can't find the contest in
the contest list
It's private contest only those who have the link can get access to it .
OK :(
you've dug your grave my friend :D
no one miss with the rated contests :3
Yeah, I wanted to post the same comment this morning. Maybe if I had posted it before you, I could get some upvotes :(
seems you have so many haters :v
Seems it's not him who has so many haters :D
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.
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.)
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 :)
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
I also can't prove that my solution always leads to optimal results in fourth task) but it was accepted
It is over. Lets discuss.
Please share if you have links to editorials.
how did you solve the first one ???
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
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
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?
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
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
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
Also wth, it's really easy to create a counterexample to that one...
:(
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
Okay, then some small modifications:
I can't believe your solution passed. Here's a counter example:
2 1 10
4 3
20 5
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
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!?
why should i :/
i think u haven't understood my solution , that's my code link :D
http://codeforces.net/blog/entry/44419?#comment-289881
He probably means:
Hacked! :D
Successful hacking attempt
This solution is obviously wrong.
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
The cf handle of those you mentioned:
The_Watcher: Deemo
Gnadook: INVWVZ
Enchom: Enchom
sigh, only 8 months more until handle changes.
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
"...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
http://codeforces.net/blog/entry/44454 :D