Let's discuss solutions here. I know I'd be curious to hear other peoples approaches.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:18:49
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:18:49
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 11:16:12 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Well, that was one of the shittiest qualification rounds I've ever seen. You know you screwed it up when even full score doesn't advance you through.
So we have simple A, and then B, where the only task is to see the trick. The trick is nice (output the numbers appearing odd amount of times), sure, but you can just get stuck on that problem easily, which isn't the task you want to put in your set if you require 100% to advance. And then there is an actual Round 1 task, C, although also not too difficult in my opinion (especially with N = 1000 instead of bigger ones even the implementation is simple) and in no way capable of differentiating the top 1000.
I don't think my opinion of the round would've changed if I didn't get stuck on B. The only thing that would've is me not wasting 2.5 hours during the night.
I also got stuck on problem B. I spent about one and a half hours working on a constraint-based approach before I shoved aside all my complicated code, looked for an easier approach, and found it. I'm angry at myself, not at the problem authors. I think it's perfectly legitimate to write a problem in which a single "Aha!" insight leads to a compact solution.
In fact, aren't those among the most satisfying problems to solve? I like a problem that rewards creative thinking rather than prior knowledge. I was pleased with this problem set even though I didn't manage to solve the hard variant of problem C in time.
Let me also point out that only 55 people who scored 100 failed to make the top 1000. That seems close to optimal, doesn't it? In other cases there are many more people who fail to make the cut-off even though they scored the same number of points as the last person who did make it. Here only the bottom 5.2% of people with the same score failed to make it.
I got bit by problem B too, couldn't find the trick. How did you guys approached problem C, I wasn't able to find solution in time.
Note that I didn't say anything about the tasks. I enjoyed the beauty of B after I learned its solution. It's quite possible to create a shit round with good tasks, as we just saw.
In qualification rounds I consider any round where there is any must-have problem to be quite bad. Good qualification rounds, in my opinion, are those where even if you fail to solve one task for various reasons, you can make it up by solving different (and usually harder) problems. Here there weren't even hard tasks, in my opinion. I think this is a safe thing to say considering the results. They even simplified C by allowing quadratic solutions. Not even solving everything was enough.
The organizers have avoided a massive shitstorm by having this failure as 1A, where from past experience, the results have been weaker, as most of the Europe is asleep (stupid me). I fear to imagine the cutoff if this was round 1B or 1C.
And I sincerely hope that there weren't any naive brute-force solutions which just managed to pass the test data. Mine brute-force TLE'd on a single test and I wonder if a bit more pruning would've solved this problem.
For B, I couldn't realize the trick during contest however my bruteforce with pruning passed. Though didn't expected but i submitted for both small and large tests in the last minute and it just worked (phew). Code: http://ideone.com/cj02mr
Me too. I wasted about an hour on B and was angry at myself after realizing the trick. Anyways, I still think it is a fun contest. I need to try harder next time.
Is it that important to qualify when there are three round 1s? Judging from your performance here you still have more than 99% chance to qualify.
As I said, my performance on the round wouldn't really impact my opinion on the round. The bad round doesn't magically become good if I'd qualified. I hoped that no one would interpret my comment as "I didn't qualify, this round is shit" type of comment, but looks like it was inevitable.
So, let me clarify. I didn't qualify because I failed. As simple as that, and quite unrelated to the matter, which is why my performance is never mentioned in the original comment, with the exception of a remark at the end, in hopes to prevent people from thinking about this as "I didn't qualify, this round is shit" type of comment.
What I'm against about are qualification rounds (by which I mean any rounds where some amount of contestants qualify for something) where a single mistake can doom one. Should one get penalized for failing one task for whatever reason? Of course. Should there be a way for them to bounce back by solving other (and usually more difficult) tasks? I believe so. Sometimes this doesn't happen though, because organizers misestimate the difficulty of tasks and either run out of tasks completely or the remaining ones are way too hard for the qualification level. In these cases I don't consider rounds as good ones, no matter what my performance was.
Do I antagonize the problem setters? No. Creating a balanced problem set is hard, and mistakes happen. However, do they consider this round a problem? Doesn't look like it from the analysis, where they say "To be in the top 1000, you needed a perfect score and a little bit of speed. However, there are two more chances to qualify for round 2"! And this is what worries me the most. But how do problem setters learn about problems if not from the feedback? Which is why I believe similarly to "Great round!" comments when they are appropriate, "This round was bad, here's why" comments are also as important.
Well, I agree that it's not good if a single mistake leads to disqualification, but in order to avoid that they have three round 1s. You have to make at least three mistakes to disqualify in round 1.
Agreed about the feedback part. I would not comment here either if the official overview showed a hint of concern.
I got stuck on B as well, and never quite got the trick, went on to C and made quite a bit of progress, after seeing the contest analysis I just changed a few lines of code and it was done, what I needed was a bit extra mathematical analysis of the graph, realizing that it was (what is apparently called) a pseudoforest, that there'll only be one cycle per connected component etc. I was nearly there, I was just trying to do a more complete search of the graph from all the points that had cycles of length 2 (and compare with the longest cycle for the final answer) I was just worried about all kinds of cases that mathematical analysis would've shown to be impossible
Problem A was quite easy — although I made a harder approach which wasted my time like 10min. For all alphabet, place the alphabet in the front or back, and simply pick the lexicographically smallest. This is the most intuitive approach and we can prove it's correctness by induction. Both part was fun and it was my favorite.
I have no idea why problem B was created. The solution was really trivial (print element with odd occurence), and usually it means that I read the statements wrong. But it was not.. I checked the english again and again after clearing the problemset.
Problem C was also interesting. I first thought that the answer is longest cycle, but after analyzing sample input more, I found something interesting happens when there is a cycle of length 2. We can find two longest root — leaf path, which roots at two cycle vertice, and insert it into a circle.
I felt that GCJ problems are very tricky and that makes me nervous. I had a sad memory of failing R1B/R1C last year, (I was still 2000+ then) and today's problem B reminded that sad memories..
Problem B was created for people who like to make things complicated. Here is my solution: http://pastie.org/private/qqdg5cnchgtffvnkdcn7w#5,98 . I was so proud I found it (and proved, by induction!), This took me more than an hour.
They don't know what a circle means apparently. At least they could've said they're redefining a circle.
Can I ask you what is the problem with their statements?
Isn't a circle supposed to be a cycle without extensions?
The kids are sitting in a circle. That has nothing directly to do with the graph where you find disconnected cycles with extensions and add them together in a circle.
I don't get it but okay if you say so.
Hi, ko_osaga could you give more insight as how to solve Problem C? I went through the problem analysis and got kind of confused Thanks
First observe that it's a graph, and it's special. it looks like a tree hanging in the vertex of disjoint cycles. https://en.wikipedia.org/wiki/Pseudoforest#Graphs_of_functions
Now, it's clear that the cycle can be inserted into circle. If we insert a cycle there, we can't insert other vertices, unless (size of cycle) == 2.
What can we insert more, if (size of cycle) == 2 ? If we insert those cycles, there are some extra spaces (left / right) to insert a single path. Also, we can append other subgraph with (size of cycle) == 2 as lot as we can.
cycle detection can be done with various ways, (I used the way simillar to topological sort) and simple dfs will be enough for finding a single longest path to insert.
Download my source for implementation : https://code.google.com/codejam/contest/4304486/scoreboard?c=4304486#vf=1
I got the trick of B as soon as I wrote the grid of sample test on paper. And after the contest, I found out that many of my friends with a high rating (purple, almost orange) could not solve B.
I remember seeing some math problems those looked pretty hard but if you give them to a little kid who just started schooling, he will solve it in an instance. Perhaps this was like one of those :v
Me too ! Hi5 :D
This would have been a better round overall if it featured a fourth problem. The points for subproblems did not actually have any meaning for the cutoff, and there was no tolerance for errors. These flaws are not fatal since it was just the first of three sub-rounds, but they are serious flaws nonetheless.
It would be nice if Google allowed all people who got perfect score to qualify.
However, this would not remedy the two specific flaws I mentioned.
Frustrated about GCJ Round 1A? Wondering if lack of Ahmed Aly did this :|
Sad story. Woke up at 2am, solved 3 problems, realised that submitted wrong code for the first problem, asked organisers to resubmit the source, they refused. Outcome 89 points, 1059 place, and sleepless rest of the night thinking what a hell...
Does the code not only using for finding cheaters?
Hey my friend also submitted wrong code in 1st problem but his output was correct ,, and he got full marks,,
Well, he didn't ask to resubmit... He might be caught though when source code has been verified.
With regards to problem B — has anyone ever seen a problem based on a similar idea before?
One that comes to mind is this — http://acm.timus.ru/problem.aspx?space=81&num=5. It's also based on the parity concept and has an elegant solution. You can also think about the minimum number of steps required to find the artefact for any N.
Thanks though apart from parity this seems to be quite different/unrelated?