Hello!
Today, at 08:00 UTC will be held Deadline24's qualifying round.
Let's discuss problems here, after the contest of course!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
Hello!
Today, at 08:00 UTC will be held Deadline24's qualifying round.
Let's discuss problems here, after the contest of course!
Name |
---|
Is it rated?
why not?)
Can you give the registration link?
www.ebimajkasi.com
You'll be banned if you do things like this here
Oh sorry this is the wrong link I got it from my history but maybe I have copied the wrong link. Sorry!!
I dont believe ya.
Is it rated?
I got lost in their website. I din't find registration link for 10 minutes. Please give the exact registration link :)
Last date for registration was 25th Feb
Any solution for B with better complexity than O(T*SZLIST^3)?
Did you meant O(T * K3)?
It seems that orders07.in was only test with K > 200. I wonder what was the purpose tests 8-10, which had large N and small K.
Let's share our results to C and D.
My results for Rancho:
EDIT: I copied wrong results ;)
Lol, my solution is total trash, but
(it's the 27th result)
Our:
Problem D (Rancho) was very similar to TCO15 Marathon Round 1 problem. Did organizers know about that?
For me this was very fortunate :) I worked on the problem C-Hospital in the first 3 hours of the contest and with less than 2 hours left to go the approach that my team mate used had trouble finding any solutions on many of the larger test cases. So I decided to stop improving C and also try something at D, since there were many more points to gain there.
Since there would be no chance to implement anything from scratch in the remaining time, I took my solution from TCO'15 Marathon Round 1 and modified it slightly, in order to find small area polygons. Note that I only considered the case of polygons with exactly N-K vertices (no time to try anything fancy there). The main algorithm I used was to repeatedly select a random subset of N-K vertices, then pick a random empty triangle consisting of 3 selected points. After that, I would repeatedly add the smallest area "good" triangle for which 2 vertices were already on the polygon and the 3rd one was still outside the polygon (this essentially added one more point to the polygon).
Once the min-area solution worked, I thought about what I could quickly do to get large area triangles. Since the remaining time was very short, I modified the above solution to repeatedly add the largest area "good" triangle at each step :) This worked, too.
In the end, this approach produced the best solutions for most of the test cases ("best" in the sense of compared to other approaches we tried, not compared to other teams). Since I made all the submissions for this approach in the last hour of the contest, we didn't get any relative scores, so we didn't know how well this performed. We were quite surprised to see our score for this problem to be 779.68 (7th place overall, and I think 6th place for this problem), given that:
I would be very interested in knowing how other teams approached this problem.
You can reduce maximizing area, to taking convex hull + minimizing area of the inside points. You then have to join those polygons, but it's not that hard.
I worked on C, because marek.cygan forgot to tell me that this task is nearly identical to TCO15R1 ;)
I just used 95% of my code from TCO'15 Marathon Round 1.
How to solve Task-C — Hospital?
I used some greedy ideas, such as:
1) Choose man, who can be cured earlier, than others.
2) Choose man, whose treatment can be started earlier, than others.
3) Choose man, who has got a maximum number of injures now.
4) If you look at formula, you can see that amount of used tables is very important. So it is a good idea to reduse number of tables to only one. Also, you can use some greedy ideas to reduse number of types of used tables(for example, if two treatments can be perfomed at tables of types 1 and 2, you can use only first type).
Different combinations of these ideas gave us 654.54 points.
Our idea (worth only 666.22 points) was also greedy-based. We considered the treatment stages in increasing order of the earliest time at which they are available (initially we have the first stage for each patient available at time 0, but once a stage is scheduled at some time, we have the earliest start time of the next stage for that same patient).
So the only decision to be made is which type of table to use for the current stage (of some patient) and whether to use a new table of that type or not. For a given table type T, we either reuse the table which becomes available the earliest or a new table. For this decision we used a scoring function consisting of a linear combination of 4 parameters:
Each parameter (except the fixed new table penalty W0) was of the form weight * parameter_value (e.g. W1 * completion_time, W2 * wasted_time, W3 * bonus_score). We considered various combinations of these 4 weights, ran the greedy for each of them and picked the best.
Assume you have fixed number of tables.
You can do a following very simple greedy: Take the guy that currently does nothing, and choose an earliest available table for him. Split ties randomly. Randomizing ties is enough to create completely different solutions.
Having this greedy you can do a HC-like solution on amount of tables used. Just make sure that you sometimes should force a move outside of local minimum since it easily gets stuck.
Additionally, there were some cases where the optimal number of tables was somewhat in the middle. And you couldn't start with the maximum, since the evaluation function isn't convex based on the number of tables used. The ugly quick fix is to just start with a random number of tables of each type.
This was enough for a (rather) solid 2nd place after 2-3h of sleep :)