TL in H is so tight. I have $$$O(nm2^k)$$$ solution but it doesn't pass :( Guess it's because of using stack.


It can be solved using centroid decomposition and some hardcoding but we don't have enough time to finish the solution.


Is there any info about prize distribution?

On eatmoreGoogle Code Jam 2021, 3 years ago

You can't make submissions.

You need to place '#' at (0,0), (h-1,0), (0,w-1), (h-1,w-1) and you will get AC because we can go there from any position.

From König's theorem we know that number of vertexes in minimal cover equals to number of edges in maximum matching. So total number of vertex is sum of vertex in minimum cover and maximal independent set so we have this equation.

Maximum independent set = total vertexes — edges in maximum matching



IgorI orz

Spent two and a half hours figuring out that a fake eulerian cycle edge can be between vertices in the same component. :(

98219728 and 98220972 . There are two same codes, that are not trivia, so maybe you used ideon of smth.

You can try to google translate this adamant's blog

Oh, I checked your code and you have changed

if(k&(1ll<<i) == 0)


if((k&(1ll<<i)) == 0) {

First one is bad, because C++ will do == first and only then &.

For sure, you have overflow with (1ll<<i)

On maroonrkACL Contest 1 Announcement, 4 years ago

What is "doubling" from problem D's editorial?

One of them is me) Actually I would be able to finish with full solution, if I know that my approach passes first subtask, but anyway I'm happy with 6th place)

There was one more day later :)

There are no hacks at Codejam so you can't solve this problem like this

On BledDestKotlin Heroes: Episode 4, 4 years ago

I wish to have at least one more round summertime

Got 457 lines of code in F)

It's actually the same because $$$\binom{n}{k}=\binom{n}{n-k}$$$

Observe, that if you pick set of numbers, there can be only one possible array, so you just need to count number to choose n elements from 1 to m, it is exactly $$$\binom{n+m-1}{n}\le 92378$$$

On hmehtaTCO20 Round 1B, 4 years ago

1e10 I guess, because you need to pass at least 1e8 numbers (to get out from 99XXXXXXXX and 100XXXXXXXX)

Yours cool too!

More participants make pretests weaker

Sorry, I forgot what the taks is, I counted all the subsequences that equal to given string

24 I guess

There was systesting

Let dp[k][i][j] will be number of valid arrays with length k and with a[k]=i and b[k]=j; So to get dp[k][i][j] we need all the dp[k-1][l][r] with l<=i and r>=j. How can we calculate it fast? Let's do 2*D prefix sums on dp[k-1][i][j] for all possible i and j. So formula is: dp[k][i][j]=pref[i][n]-pref[i][j-1]. Where pref[x][y] is sum of all dp[k-1][i][j] where i<=x and j<=y.

Am I the only one who did C with 2-D prefix sums?)

I guess bfs from all vertixes has O(n^2) complexity, because we have linear number of total edges. (Each vertex has no more than 4 edges, so there are no more than 2*n edges)

It works only for tree

On touristAtCoder Grand Contest 041, 4 years ago

Very sad, that the only wrong answer of my solution for C is n=5 :(

Can you, please, open test's verdicts

String's beauty is number of minimal balances, if balance of all string is 0; (Balance is number of '(' on prefix minus number of ')' on prefix)

If y=k*w+r and x=x0 — solution, so: y=r and x=x0+k*d — solution too, because: r + (x0+k*d)<r+x0+k*w<=n (This thing reminded me about Pell's equation xD)


string *_*

1 2 3 6 8 -> 1 2 3 0 2 -> 1 1 2 0 2 -> 0 0 0 0 0 // done

On Um_nikRound #576 Editorial, 5 years ago

Solution got TL on tests with large input, so the problem is how to read a lot of data fast. You can read how the thing above optimizes the time here: (Using of printf and scanf usually fixes all the issues connected with input/output, so by using them you can protect yourself from stupid TLs)

On Um_nikRound #576 Editorial, 5 years ago



Hey, I have one strange question for problem D. Is it not ok that my solution doesn't submit because it prints -0 instead of 0, or i should remember this feature of C++ for the next time? Here is the code: (Please rejudge it if it was unexpected mistake)