The rounds are open and rated for everybody.
Mentioned in the second line ...

Codeforces: 20 T-shirts randomly distributed.

Me: Pretending to calculate the probability when I know answer is 0.

But scientific studies also show that its_Atrap

The statements are concise, sold it

PurpleCrayon orz

I hope to become Purple after this round :)

I vote only after contest.

Very original meme

Woaahhh, Directly trying to defeat red coders. Nice MEME!!!

OK I guess global rounds are really hard this was my first codeforces contest I guess i shouldnt be demotivated because i didnt even submit a single thing right just got close on phoenix and puzzle(failed test 2 lol)

omg :O

And a very good opportunity to boost it down, too =)

lol no. for the same performance you get much more rating in div2 than in global/div1. Not that it should matter but that's not the point here.

I have observed there's a lot more cheating in global rounds than normal rounds. Honest participants usually suffer in global rounds imo.

as long as you include "As a tester" in your msg, its fine :)

I like the strategy which has a possibility that we don't solve anything in the contest XD.

by the time I solve it, it would be worth a negative amount of points.

You guys are solving 5000 pts problem :(

All the best bro.

They're both americans with a chinese name, i guess

Daily reminder that Google exists

Same here brother, me too suffering from covid, I can feel your pain. T_T :(

Same situation. Tested positive yesterday. Unlike others I am having a headache, so decided to take some rest.

If you are not well, I advise you to do the same.

Hmmm, I was imagining a closet full of segment trees, linked lists and a few queues. Never thought of the struct t_shirt. Hmmm..

Maybe you have to do the same thing after 2 hrs in this contest(considering the difficulty of global round).

I worked like two hours on d but didnt get it :/

And it can pass the pretest.

Note that there cannot be more than one consecutive light that turns on automatically. So, our final answer will have some segments of $$$1$$$'s (lights that are turned on manually) separated by exactly one $$$0$$$ (lights that are turned on automatically). We need to find the number of ways to make such an arrangement.

Let's take this one step at a time.

In how many ways can we turn all the lights on manually?

You can only choose one starting light in a segment of n lights, then at each step you can either go left or go right. For better visualisation, consider n points coloured red. Pick a starting point and colour it blue. In each step, you can move from a blue point to an adjacent red point.

Number of ways to do this = $$$(L + R)! / (L! * R!)$$$ , where L is the number of steps to the left of the starting point that one can take, and similarly, R is to the right.

To meet the constraints, we will be precomputing these answers till $$$n$$$.

Now, coming to the main solution.

Let $$$dp[i][j]$$$ = number of ways we can arrange the first $$$i$$$ lights such that the $$$i$$$ $$$th$$$ light is manually turned on and a total of $$$j$$$ lights were turned on automatically among the first $$$i$$$ lights.

Let $$$k...i$$$ be the last segment of $$$1$$$'s. This means that at position $$$k-1$$$ we will have a $$$0$$$ and at position $$$k-2$$$ there will be a $$$1$$$. If there are exactly $$$j$$$ $$$zeros$$$ in the segment $$$1...i$$$ then there are exactly $$$j - 1$$$ $$$0$$$s in the segment $$$1...k-2$$$.

Let's define an operation, as we turning a light manually on (or placing a $$$1$$$). So in the segment $$$1...k-2$$$ we have to place $$$k - 2 - (j - 1)$$$ ones, and in the segment $$$k...i$$$ we have to place all $$$i - k + 1$$$ ones. This is similar to the question we answered above for placing all ones. We have to tell the number of permutations of $$$(L + R)$$$ items, in which the order of the $$$L$$$ items and $$$R$$$ items are fixed.

Therefore, the ans for $$$dp[i][j] = dp[k - 1][j - 1] * nCr((k - 2 - (j - 1)) + (i - k + 1), (i - k + 1)) * ways$$$ $$$to$$$ $$$arrange$$$ $$$(i - k + 1)$$$ $$$ones$$$

PS: I know it's a little too verbose. But hope you can understand the solution.

You can simply let computer $$$i$$$ in $$$dp[i][j]$$$ be turned on automatically.

so you just have to enumerate the last automatically turned on computer before computer $$$i$$$ for $$$dp[i][j]$$$

Video Explanation for Problem D

For b check the if number is divisible of 2 or 4 and the remaining number should be a square number.

In C, keep assigning the block to the tower with minimum current height. Can be done using set <pair<int, int > >. Also the answer can never be NO,

For C, just sort by block lengths and assign to each stack.

For B, divide by 2 and 4, and see if number is a square.

B — If I don't FST, if dividing by 2 or 4 gives you a square (number) its a yes C — no idea I kept WAing

Assuming that I will not fail system tests.

Problem B: Notice that we can only form squares using 2 or 4 isosceles triangles. So just check if the given number of triangles is divisible by 2. If it is, then check if (n/2) is a perfect square. (We can form a square of size sqrt(n) considering 2 triangles as a single block). Now, if this fails then check if n is divisible by 4. If it is, then repeat the process above. The answer in any other case is NO.

Problem C: I have done this greedily. Using a priority queue, I always select the tower with minimum height and add the blocks in decreasing order after sorting. After adding all the blocks, I check if the difference between the minimum and maximum height is smaller than or equal to x.

Best Explanation for Problem B

• Remove all the already matching pairs as they do not affect the overall answer.

• Now, check if number of left socks = number of right socks, then the answer is simply the number of left socks (this happens because we have already removed matching socks and hence we can just change the color of socks from any one leg to match it with the other leg)

• Now, we know that we have to transfer some socks from one leg to the other.

• • Observation: It is always better to transfer socks which form a pair.
• • Example: Consider we have Left: 2 2 1 3 Right: 4 5 Now, we know that we have to transfer one sock from Left to Right, and it will be best if we transfer sock 2 from left to right, as it then forms a pair with the one sock 2 which would remain in left.

• Now, after transferring greedily, we again remove the matching pairs of socks in left and right. Now, if the remaining number of socks in left and right are same, then the answer is simply number of transfers we made + number of left socks (we change the color to match the right socks as we already have removed the pairs). If the number of socks are still not the same, then we can simply transfer any socks from the pile having greater number of socks to the other and then change the colour of the remaining socks. In this case, the answer becomes the number of transfers we made earlier(greedily) + greater pile size.

Explanation for Problem D

Just a few couple thousands...

Explanation for Problem D

As long as initially $$$\sum_i a[i] \geq (n-1) x$$$ and the graph is connected, there is always a road you can build, no matter which roads you build and in which order. This means you can discard all edges but some $$$n-1$$$ that form a tree.

Then, start doing arbitrary possible operations. Maintain in every component the values $$$a[j]$$$ for the components $$$j$$$ of children of the component, and in a priority queue the maximum current value $$$a[i] + a[j]$$$ over pairs (component $$$i$$$, component of child of $$$i$$$).

Complexity is $$$\mathcal{O}(n \log^2 n)$$$ with small-to-large merges.

what is the FFT solution?

No need for FFT. You work with segments of manually toggled computers, with single automatically toggled ones in between. Then DP states are (first $$$i$$$ computers toggled, the last one is automatic or right endpoint of a segment, number of manually toggled computers up to computer $$$i$$$), and there are just $$$O(N^3)$$$ state transitions.

You can solve this task without FFT.

We can see on array as blocks set of consecutive computers.

Let write the 1st DP f[len][cnt] — answer for on first len computers, where cnt computers we turned on themselves. Calculating DP looks like f[len + bs + 1][cnt + bs] += f[len][cnt] * fullblock[bs] * C[cnt + bs][bs], where fullblock[bs] — number of permutations for turned on by hand bs computers among bs computers.

For fullblock[bs] we need in the 2nd DP. dp[len][last_pos][flag] — number of permutations with len computers, there is computer with index len stay in position last_pos, flag = 0 when position of index len — 1 stay to the left of last_pos

lol same :D

damn, you have crazy expectations for problems..

Very shit contest for div2 participaants indeed (seeing most of them usually do upto D). Stupid problems, just stupid

It uses union-find to track connected components of the graph, augmented with the amount of asphalt in each component (stored at the roots of the union-find data structure).

I used dp to find all the possible combinations of switches that we manually turn on. For example, X_XXXX_XX_X, XX_X_X are some valid sequences. The gaps represent switches that automatically are on. It is easy to see that the size on contiguos gaps will be atmost 1.

Now, for each such combination we've to find the number of permutations to fill the X's. To do that I used 2 more states, {position, continuos X's till pos, number of skips}. I use skips to calculate how many were manually ONed before the contiguos Xs until pos.

Now another important thing to note is that, The number of permutations to arrange r numbers such that theres no gap between them is 2^(r-1). (Try to prove it)

After that we just have to use some more combinatorics to combine 2 contiguous segments of X's in our dp. There will only be 2 transitions, pos->pos+1 and pos->pos+2 (skip->skip+1). Rest of the details should be clear in my code

Submission

This may be helpful

No it was based on mega ultra shit algorithm

It felt like programming some robot to jump, move, etc in a game using too many if else statements.

Seems like someone is trolling

EDIT: Ah, seems like a bug lol

This is not the first time I think this is a bug

Stop bullshitting everywhere. Contest was good, maybe your ass got burned with D. So keep your shitty opinions to yourself, ultrashitposter.