Round starts at 14:00 UTC today and 25 participants will advance to final round in Dublin.
→ Обратите внимание
До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2024 02:45:52 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Now I finally feel old. I opened the problem C, and the first thing that came to my mind was "Oh, this problem may be solved with the same idea as in the problem K from NCPC 2010".
Thanks for the contest! Problems B and C were great, problem A made me lose some time on it and it wasn't a pleasant time, and I'm not sure about problem D if it has a solution that does not require lots of coding.
What were your solutions to problem A? I couldn't think of one.
We need to find the number of nodes that can reach our node in a graph (of size (L + 1)L). If the sum of digits of a number is > L, it can't be reached from any other node. Thus we may only consider the numbers with sum of digits <= L, and there are only about 50000 when L=9.
Precompute everything using bruteforce. (My program ran in 4m51s on A-large, and my penalty was 1m35s too high for 26th ;_;)
Well, I tried to do this as well but my shitty computer kept crashing :( Don't understand why such problem was including in GCJ...
26th, my ass.
Did you read "There are a total of 26 spots in the Finals, including Gennady.Korotkevich's spot. So, if he places in the top 25, the top 26 contestants will all advance to the finals. Otherwise, the top 25 plus Gennady.Korotkevich will advance." ?
tourist is ahead of you, so I think you have a spot. On the other hand, I'm 27th :(
So, mnbvmar will be on internship in Google, you also got sure spot.
Let's keep going like that, only 53 more people on internships or something and I'm going to the finals!
I'm 28'th. Do you have one more?
I have no more tricks up my sleeve ;p. However I have heard that one year ago participants up to 32nd place were allowed, so there is still a big chance for you :). On the other hand, Dublin is much more convenient place to go for most participants than USA (closer and easier to get visa if necessary), so who knows.
From 2009 to 2016, even 30th place was always enough. You have a very good chance.
Do you have stats for each year? It would be interesting to see the distribution
I did it manually but I lost the data — if my memory is correct, it distributed around 31-37th.
why can't he take part? Can't he just take leave for the contest?
Google employees are not allowed to take part in GCJ. And he will be a Google employee (intern) at the time of the final.
I would resign from internship in such a case. In my opinion GCJ final is worth much more than internship.
Edit: Or at least postpone it after the finals.
if you postpone it, you would probably only have 1 month left for the internship...
Maybe if you are P___ then it would be unique opportunity, but if you are mnbvmar then it is not :). And internship can make for a living of whole family for 2 years in Poland which is not a case with GCJ ;p.
but if you are mnbvmar, you can easily find 10 other internship as good as google :)
Man, you mast feel angry!
mast ? :|
LOL, it was a mistake.
Seeing as in 2:08 I was 18th and watching scoreboard for next 22 minutes as I fall to 41st place before judging larges and 36th after was really painful :(. Stupid A xdd
This year the number of late submissions was exceptional. Usually we can estimate the cutoff from first AC time. At 40 minutes, I was confident that fast 50 points is enough. The cutoff of 74 points was surprising.
Editorial is already posted. How unusual for them.
For each special cell, draw a horizontal line and a vertical line through that cell. We have O(n) lines that divide the grid into O(n2) rectangles. For each rectangle the problem boils down to the following:
For each of four corners of the rectangle we know the minimum allowed value there (computed in O(n) by iterating through all special cells in the input and checking their distance to this cell). Knowing these four values (the sizes of the rectangle), we can forget everything else from the input.
For each cell we can determine to which corner it should go (i.e. when we get the minimum value in this cell). It turns out that the rectangle is divided into four regions of shapes like this:
We can binary search all the split-lines.
Yeah, I had a similar idea, with rectangle splitting done by trying all possible initial values as giving the optimum; that gives O(N3) regions constrained by x, y, x + y, x - y being in some intervals (can be determined in O(1) with some precomputation since there are just 9 types of inequalities for x, y) with linear function to sum up over those regions, which is somewhat more annoying but doable e.g. by further splitting of this region into rectangles and triangles.
I'd have tried to code it, but A was stupid and I killed so much time on it.
CF was down for a while after GCJ, finally connected :)
It reminded me your problem from Codechef Lunch.
To other contest organizers: It is still possible in 2017 to have original and interesting problems in online rounds, huh?
Yes, I still see lots of new interesting problems, but the probability of collision is higher now.
Does it mean that GCJ succeeded on it or not? As for me, their problems were pretty original (even though I knew the key idea of problem C, but I'm sure this idea is not very popular) for all rounds. Of course, not 100% of the problems were really interesting (today's problem A, for example, or R2's 2sat problem), but overall I liked problemsets of GCJ pretty much among all the contests I participated this year.
Yeah, GCJ is known for having good problems every year. AtCoder and TopCoder problems are focused on new ideas instead of known ideas and just time consuming stuff — which should reduce the probability of collisions.
In many years of solving TopCoder contests can't remember many reused problems. But I can remember that, for example, there was a pretty difficult ICPC World Finals problem some years ago that was exactly the one from old TopCoder.
I was joking with a friend before some other online contest that if I see any problem having usual "answer these queries efficiently" style I would not participate and surprise — last 3 problems had similar statement :)
Not if you have two such contests in a row
I can't understand why a bridge existence makes a solution impossible to exist in B. Can someone clarify, please? Thanks :)
Consider a bridge that connects two components A and B. Define the difference between the ingoing and outgoing edges in the vertex as its value. Suppose that the flow through bridge is non-zero and remove it from graph: the total value of all vertices in A is now different from zero. On the other hand, sum of all values of vertices in a connected component should be zero since each edge is accounted twice with opposite signs, i.e. we can not fix the disbalance in component A. That leads us to contradiction.
Got it. Thanks for the explanation.
I got 32nd in HackerCup this year, and got 32nd again :(
and
It's not funny!
Investing in this.
What a fractal!?
end.
Con...Ti...Nue!
Problem B has a very large range. It is known that you can solve it even with range of [-5, 5] (search "nowhere-zero flow" on Wikipedia). A reasonably simple algorithm can do it on range of [-7, 7].