Just a reminder that GCJ Round 3 is about an hour away. I don't think there was a reminder email and I only just realized this, hopefully this will save some of you too :-)

EDIT: Round is over, can discuss now.

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3567 |

3 | Um_nik | 3527 |

4 | ecnerwala | 3458 |

5 | maroonrk | 3409 |

6 | 300iq | 3317 |

7 | Petr | 3272 |

8 | LHiC | 3229 |

9 | Benq | 3226 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 198 |

2 | antontrygubO_o | 188 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 167 |

7 | Um_nik | 164 |

8 | tourist | 163 |

9 | McDic | 162 |

10 | Monogon | 161 |

Just a reminder that GCJ Round 3 is about an hour away. I don't think there was a reminder email and I only just realized this, hopefully this will save some of you too :-)

EDIT: Round is over, can discuss now.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/04/2020 18:05:48 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve problem C: Pen testing ?

Way to increase probability: We want to find an empty pen. Let's try pens in random order. Empty one will be approximately in the middle. After that choose 2 pens that you haven't tried.

I got accepted 2 subtasks with looking for pens 0, 1, 2, 3.

I got the first 2 subtasks by a sort of iterative deepening search.

I roughly simulated the percentage of success, and stopped when percentage was high or I found ~4 or 5 pens. These parameters were somewhat trial and error.

Got me to around 62.4%, couldnt get to 63.3% for the last subtask.

How to approach Problem B?

Who knows what happened to the standings? The hidden verdicts were shown for a little period of time and now they are invisible again.

Now it's good. Seems to be a short-timed issue.

The unofficial list of finalists:

GO POLAND!!!

If nothing will change, it will be the first time in the history of Google Code Jam (since 2003) with 0 finalists from Poland.

Is KalininN KAN?

Yes.

Is saketh.are saketh?

Yes!

SnapDragon 's name is Derek Kisman. A veteran that nowadays only competes in Google Code Jam. He has a youtube channel

Thanks, added.

Thanks for the shout-out. :) My screencast of Round 3 is here.

You made all Candidate Master proud lol

Just curious: what was MiFaFaOvO's handle?

And Um_nik's handle?

More information here.

MIFAFAVO didn't take part in codejam

he did

Dlougach is me.

Can you please move gs12117 into correct (5-th) place? It seems their last second submission took some time to evaluate, and the first-released standings were incorrect.

Done, thanks for pointing this out.

Thanks for the interesting problem C in particular.

And a separate thanks to Petr for problem C analysis! In addition to showing a few approaches to the problem itself, the analysis contains a detailed writeup on judges' considerations when setting a probabilistic problem.

Had a roller-coaster with C after the contest.

Conclusion: after all those years I still haven't learned to read problem statements.

I think there is a (very minor issue) with the editorial of C-small:

The last sentence is false, since the path through XXXXXXYYYYYY has length 12 whereas the answer is 6. As mentioned in the first sentence, $$$d(P, Q) \leq \max(|P|, |Q|)$$$. So the longest string $$$L$$$ that we could visit in any optimal solution has satisfies $$$(|L|-|P|) + (|L|-|Q|) \leq d(P, L)+d(L,Q) \leq \max(|P|,|Q|)$$$ or $$$2|L| \leq |P|+|Q|+\max(|P|,|Q|)$$$. So for the input limit of 6 this means no optimal solution visits a string longer than 9 characters.

EDIT: For AAABBB and BBBCCC, a valid output would be AAABBBCCC.

Problem A is fun when one has levenshteinDistanceAndPath in the standard library, doing half the work.

For example, in the first case

`XYZZY ZZYZX`

, it gives distance and path as`Tuple!(uint, EditOp[])(4, [insert, substitute, none, none, remove, substitute])`

.Didn't ultimately help though, as I was too bad at all the other problems.

Fun fact: MiFaFaOvO, whose GCJ ID is "xll114514", failed B large only because his "x" array is not "ll"(=long long according to his typedefs).

No #define int long long? Typical rookie mistake

I'm curious how tmwilliamlin168 didn't clear this round, he is so fast and precise as seen in previous rounds of codejam.

kickstart*

Does anyone know what was Eva's handle?

numb

I haven't participated

Hey are you some sort of famous person? I have seen many people talking about you idk why.

I am some sort of famous for being a woman person

and for being a jerk person in comments

anyone else miss the round?

Don't know about others, but I really felt very sad after watching Errichto 's GCJ stream :( .

Huh, B was solvable in O(n^2)? Seems weird that they decided to set $$$n \le 100$$$ in that case. I had $$$O(n^3 \log n)$$$ (could be optimized to $$$O(n^3)$$$ with a little hassle). Possibly they were aware of it and decided to let it pass, but no mention of that in editorial. My solution was in style "we can assume that some object is in one of interesting positions and there is finite number of them". Let's consider a solution and shift some thermometer and ones that are "connected" with it through sequence of symmetries up to the furthest possible point where structure doesn't change. That is, so that for some thermometers it holds that its position is either $$$x_i-1$$$ or $$$x_i+1$$$ (I multiply coordinates by 2). Points that become if interest are results of consecutive symmetries of such points through given points and there are $$$O(n^2)$$$ of them in total. I fix position of one thermometer on one interval in $$$O(n)$$$ possibilites and for each of them I consider simple dp with $$$O(n^2)$$$ states (implemented on map). There is one special case — when n is odd and the answer is n. Fortunately it was featured in samples which was life-saving.

My solution is $$$O(n^3)$$$, but I think it can be solved in $$$O(n \log n)$$$. I don't want to verify this though.

SpoilerConsider this problem in an interval, and moreover say that we only determine if answer = $$$n$$$ or not. We should find positive real solution $$$x_1, x_2, \ldots x_{n + 1}$$$ such that $$$x_i + x_{i + 1} = len_i$$$. This is $$$O(n)$$$. In a circle, you can do similar things to see if answer is $$$n$$$ or larger.

Let's say the interval is

validif such a solution exists. If you can divide the circle to $$$k$$$ valid circular interval, then you can solve the whole circle with $$$n + k$$$ thermometer. If you solve each interval case with $$$n$$$ thermometer, the issue only arises where different intervals meet. At that point you can put one sentinel, to "pull" the result in the desired direction. This immediately gives $$$O(n^3)$$$ solution which I passed.Now from here, I didn't verify with AC. For each starting point $$$l$$$, you can find maximum $$$r$$$ such that $$$[l, r]$$$ is valid. They are monotonic in every way ($$$[l, r] \rightarrow [l + 1, r], [l, r - 1]$$$), so if you find such valid $$$r$$$ for all $$$l$$$, you can use sparse table (jump pointer) to simulate greedy in $$$O(n \log n)$$$, possibly with easier way but who cares.

So the hardness lies in where you have to find the interval is valid or not. The simulation of procedure reveals that the answer does not exists if some term of $$$len_i - len_{i - 1} + len_{i - 2} - \ldots \le 0$$$. You can take this as a minimization problem, write DP form, and use segment trees.

I just got accepted in practice with O(N) actually. If you read their solution it basically says to pick each of the N intervals as a starting interval of positions for the first thermometer and mirror the interval / reset the interval & add 1 to the count until you get back to the start — which is O(N). However, you are guaranteed to reach a valid solution as long as you pick a starting interval that works if you only put one thermometer. Combine this with "you don't need 2 consecutive intervals with 2 thermometers" and you only need to check 2 consecutive intervals as starting points.