By riadwaw, history, 4 years ago,

Round starts at 14:00 UTC today and 25 participants will advance to final round in Dublin.

• +118

 » 4 years ago, # | ← Rev. 3 →   +89 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.
 » 4 years ago, # |   +22 What were your solutions to problem A? I couldn't think of one.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » 4 years ago, # ^ |   +22 Precompute everything using bruteforce. (My program ran in 4m51s on A-large, and my penalty was 1m35s too high for 26th ;_;)
•  » » » 4 years ago, # ^ |   +23 Well, I tried to do this as well but my shitty computer kept crashing :( Don't understand why such problem was including in GCJ...
 » 4 years ago, # |   +118 26th, my ass.
•  » » 4 years ago, # ^ |   +139 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." ?
•  » » 4 years ago, # ^ |   +134 tourist is ahead of you, so I think you have a spot. On the other hand, I'm 27th :(
•  » » » 4 years ago, # ^ |   +77 So, mnbvmar will be on internship in Google, you also got sure spot.
•  » » » » 4 years ago, # ^ |   +109 Let's keep going like that, only 53 more people on internships or something and I'm going to the finals!
•  » » » » 4 years ago, # ^ |   +121 I'm 28'th. Do you have one more?
•  » » » » » 4 years ago, # ^ |   +20 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.
•  » » » » » 4 years ago, # ^ |   +19 From 2009 to 2016, even 30th place was always enough. You have a very good chance.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +10 Do you have stats for each year? It would be interesting to see the distribution
•  » » » » » » » 4 years ago, # ^ |   +18 I did it manually but I lost the data — if my memory is correct, it distributed around 31-37th.
•  » » » » 4 years ago, # ^ |   +9 why can't he take part? Can't he just take leave for the contest?
•  » » » » » 4 years ago, # ^ |   +26 Google employees are not allowed to take part in GCJ. And he will be a Google employee (intern) at the time of the final.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 4 years ago, # ^ |   0 if you postpone it, you would probably only have 1 month left for the internship...
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +84 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.
•  » » » » » » 4 years ago, # ^ |   +21 but if you are mnbvmar, you can easily find 10 other internship as good as google :)
•  » » » » » 4 years ago, # ^ |   0 That's an interesting point, could you elaborate on that?
•  » » 4 years ago, # ^ |   +7 Man, you mast feel angry!
•  » » » 4 years ago, # ^ |   -9 mast ? :|
•  » » » » 4 years ago, # ^ |   +3 LOL, it was a mistake.
 » 4 years ago, # |   +28 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
•  » » 4 years ago, # ^ |   +76 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.
 » 4 years ago, # |   +33 Editorial is already posted. How unusual for them.
 » 4 years ago, # |   +57 not so hard solution of DFor 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.
•  » » 4 years ago, # ^ |   +10 my solutionYeah, 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.
•  » » 4 years ago, # ^ |   +13 CF was down for a while after GCJ, finally connected :)It reminded me your problem from Codechef Lunch.
 » 4 years ago, # | ← Rev. 2 →   +46 To other contest organizers: It is still possible in 2017 to have original and interesting problems in online rounds, huh?
•  » » 4 years ago, # ^ |   +23 Yes, I still see lots of new interesting problems, but the probability of collision is higher now.
•  » » 4 years ago, # ^ |   +38 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.
•  » » » 4 years ago, # ^ |   +33 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 :)
•  » » 4 years ago, # ^ |   0 Not if you have two such contests in a row
 » 4 years ago, # |   0 I can't understand why a bridge existence makes a solution impossible to exist in B. Can someone clarify, please? Thanks :)
•  » » 4 years ago, # ^ |   +13 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.
•  » » » 4 years ago, # ^ |   0 Got it. Thanks for the explanation.
 » 4 years ago, # |   +83 I got 32nd in HackerCup this year, and got 32nd again :(
•  » » 4 years ago, # ^ |   +15 and
•  » » » 4 years ago, # ^ |   +28 and
•  » » » » 4 years ago, # ^ |   +11 It's not funny!
•  » » » » » 4 years ago, # ^ |   +16 Investing in this.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +16 What a fractal!?
•  » » » » » » » 4 years ago, # ^ |   +21 Why everyone is doing this?
•  » » » » » » » » 4 years ago, # ^ |   +11 Gotcha
•  » » » » » » » » » 4 years ago, # ^ |   -37 end.
•  » » » » » » » » » 4 years ago, # ^ |   -63 Con...Ti...Nue!
 » 4 years ago, # |   +40 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].