Just a friendly reminder about TCO15 Round2C. It'll take place in the Japan and online. Time and Date.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | adamant | 157 |
| 6 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 13.11.2024 05:54:31 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
since the round starts in a few hours...
Another great day for a competitive programmer! 0 problems solved ( ͡° ͜ʖ ͡°) (even 0 compilations :P)
The 500 pointer was a very, VERY bad fit for a contest with systests after the contest and virtually no pretests. Not saying such problems can't appear, but I'd sure prefer it not being there.
You could've still tried hacking, btw.
Could you elaborate why was it that bad? I see that it got ~4% acceptance rate, which is not too high to say so... Was it because there were just many stupid cases or all people just submitted some shit?
More like 0.4% acceptance rate. The number of submits is meaningless since there are many wrong solutions that pass a small subset of tests.
It's because there were no cases. The real solution (most likely) tries all ways to seat all subsets of people (their permutations); for each permutation, it's fairly easy to construct a bunch of inequalities describing the starts of some two intervals / start / end have to have distance ≥ x or < y". If all such pairs of inequalities are possible, then (probably) the last person in the subset can sit down. And something much simpler for the other half of the problem.
But people would think it can be solved more simply. If the most obvious thing fails some pretest... okay, let's find out why and add a check against that type of situations. It's not easy to find out that your solution is wrong by custom testing, since the cases where a strong casework solution fails are hard to find if you don't realise why your solution won't work already. And this leads to a lot of wrong submissions.
Still, seeing as I didn't solve it, maybe there's even more to it or I'm completely wrong?
Let me state this clearly — you say that it was "very, VERY bad fit", because people coming up with some shitty solution without any proof didn't get instant feedback that it is wrong --__--.....???
Yes, that's correct :D
Well, not precisely. People coming up with a solution with a faulty proof didn't get feedback that it's incorrect (or they wouldn't have submitted). And people coming up with a "shitty" solution probably did get proper feedback on samples; the problem is that there are ideas which seem good and yet fail, because they're just patching up a wrong solution (tactically good, strategically bad). And that's hard to see, especially when you're short on time and it didn't seem like a hard problem at first.
Note that I'm not saying it was a bad problem. While I prefer less old-ACM style "only a bruteforce works" (except this time it wasn't disguised by fairly high constraints, see B and G), this troll-aspect provides a good learning experience at least.
Ultimately, the fault for not solving the problem is ours (everyone's). If you think about it, we're pretty stupid — we're failing to solve problems that have known solutions, even after solving thousands of other ones. And even then, we need a lot of hints. Problem placement/points is a hint. Samples are a big hint, many samples/pretests are a massive hint. More time counts as one, too. And for this problem, it seems we desperately needed more hints to solve it.
What I mean by the problem being a bad fit for the contest is:
the contest would've been more balanced if the 500-pointer had "more hints" as above, or had more alotted points
the problem would've had more solutions in such a situation, and that difference is considerably bigger than for a typical 500-pointer
Do you disagree with one or both of these points, or do you think it isn't good to prefer more balanced contests?
Also generally directed at people who downvote this and didn't reply(yet) — do you disagree, if so, then why? Try joining a debate instead of giving le upboats/downboats. Pic related.
Of course, I'm not trying to blame anyone. I'm aware that we see it all just in retrospect. Nobody expected
the Spanish Inquisition2 solutions, I'm sure. Anyway, this doesn't matter for the two claims I present.That seems to solve the problem, from a (somewhat lengthy) discussion we had in our room post-contest.
The fact that it's TCO probably contributed to the low acceptance: if you can't solve a problem you usually submit whatever random stuff that passes the pretests, because you really want to advance. If there is a 0,00001% chance that it is correct, it's probably worth trying...
Can you provide a test case where the easy solution fails, so that I can understand your point?
>_>
Try it yourself in practice, that'd be better. If there was a "the" easy solution, it'd be the one when you assume exactly and only people for whom you answered "sit" or "unsure" sit down; it fails on samples. Then, you can assume that people sit down in a fixed order, I guess? I didn't spend so much time on the problem that I'd be able to list a tree of bad decisions.
I agree it was hard to solve, on the other hand it was easy to hack :D. Without hacks on 500 I wouldn't be in the top 40, so I'm glad it was there.
Btw., a good hack for 500 is
I think low accept rate is OK, but the problem was just too difficult. Also, I used ad-hoc methods to solve/pass the 1000 pointer, which was also bad for the contest.
I must note here that I liked the problem a lot, despite being still unable to solve it.
As for this problem appearing at TCO: it sure has depth (and some beauty too), so is a good fit for an important contest. Perhaps it broke some expectations: in rounds 2A and 2B, the advancers were mostly people who solved at least Easy and Medium, while today, a semi-decent time on the Easy sufficed. But I don't think the large amount of wrong submissions was expected by the authors.
I did sort of like it as well, but the depth of a problem has little to do with how well it fits in; how many people can solve it under conditions of this contest vs how it'd be if the conditions were different (say, three more fairly strong systests among the samples?); since just solving the problem gives a large advantage over hackers who didn't solve it, a reasonable number of advancers (10? 20?) really should solve it for the problem difficulty to be properly balanced. This was a competition on one problem and around 60 additional hacks. More on that in a while.
Any greedy solutions for 250?
I submitted a greedy solution in the practice room. (But I didn't prove its correctness and I can't come up with a DP solution with time complexity less than O(n^5) >_<)
Here is my code.
I've submitted dp solution in the practice room with complexity O(V*N^3), V — max card value, N — number of cards. The idea is the following:
merge 2 arrays to one sorted vector<pair<int,int> > (first element card value, second 0 — petr, 1 — snuke).
Now we iterate this array from smallest element to greatest.
At each step we can add current element to the pile or eat it.
If we add element to the pile and previously added element also from the same person then another person should eat at least one 1 card (because we take cards from the same person twice or more in a row). So, dp array:
Dp step obvious. I know it is over-killed, but it works and clear for me.
It seems tests are weak, because debt_petr and debt_snuke could be negative and this approach passed all tests. Please, don't read my weird solution. :(
Actually, I just get rid of the negative value problem, by increasing debt_petr and debt_snuke to 101 and adding offset 50 to initialized values. Test passed again.
Actually, you don't need last_taken_value, and without it complexity becomes O(V * N2).
You are right, thank you! Just implemented solution without last_taken_value and got AC with O(V * N^2).
The trick is that if we put some card into the pile, we have to eat all the rest cards with the same value.
Mistake.Sorry.
Could anyone explain how to solve 250 please?
We have dp[top][move] which equals to longest possible stack of cards after move moves with top card leq than the number top.
We begin with dp[i][0] = 0 for i = 0, 1, ..., 100. and when we perform move (check who is "on move", by taking move mod 2, wlog Petr is "on move") we do
dp[petr[j]][move] = max(dp[petr[j] - 1][move - 1] + 1, dp[petr[j]][move - 1], dp[petr[j]][move])
for each j. After that we just update dp[j][move] = max(dp[j][move], dp[j - 1][move]). for each j
The complexity is moves·maxCard.
Thanks a lot!
The problem looks so easy after someone explain it to you :)