Pfff, is that really a problem for you?

Sometimes I even write three contests per day!

You can do both the contests but say goodbye to sleep. I did that once and still got a good score.

I think I was wrong... a perfect 'L' is possible...not 'T' :3

As usual: English and Russian.

Maybe because that rounds are based on some contest(#606 : Technocup 2020 Elimination Round 4, #607 : ICPC Manila 2019, #608 : Municipal Stage of All-Russian Competitions for Schools, Saratov).

Of course not

Yes, I plan on uploading the full set in the gym in the future, along with some past ICPC Manila problem sets too.

Ye, for graphs jngen is really awesome, but in general it's pretty uncommon for tests to have hard structure. Like the said connected graph is just a spanning tree (which is easy to generate) with some more edges on top of it.

kevinsogo is the chief judge of ICPC Manila, that's why he has "early access."

so funny,me too：D

answer can be 0

Maximum — for each edge estimate upper bound of pairs which ways can contain this edge (it will be min(size_of_left_tree_if_we_erase_this_edge, size_of_right_tree_if_we_erase_edge). Answer — sum of upper bounds multiplied by weight of edge.

Minimum — it can prooved that each edge must be taken at most once. Lets make tree rooted and count size of each subtree, we take an edge only if size of corresponded subtree is odd.

What ever it was, it was the death of me xD Had like 15 submissions xD

My code failed BANANA APPLE :(

for test case : IA GOG why AI is not the answer?

My code failed on BAA AABA. My code produced ABA and told me that it's impossible since it is smaller than AABA. smh

As a grey, I solved A in 4 mins then stuck on B until contest ended. Still got positive delta.

Try

EBB BBF

What was pretest 2?

For which case?

wrong :/

That’s the upper bound and we just need to show a way to achieve it. Think about the edge that maximizes the smaller components. Pair the nodes based on that edge and the pairings should work for future edges.

Suppose the removal of the edge splits the graph into sets $$$S$$$ and $$$T$$$ with $$$|S| \le |T|$$$. If $$$ ( i, j ) $$$ is a pair within $$$S$$$, then there must exist a $$$(u, v)$$$ pair within $$$T$$$. Then you can show that pairing $$$(i, u)$$$ and $$$(j, v)$$$ is always better (try and draw a diagram to see why). Hence, each vertex in $$$S$$$ must be matched to something in $$$T$$$.

Centroid can help you prove this

Well now I think about it I think I can just use "<" in python to compare the strings... I think that's how python compares already...

BUT ITS FINE! Next competition in an hour! Hope I promote :)

EDIT: FUCKKKK I GOT 2C WRONG OMG

How? What made it so easy after reading constraints? Did you get to know why your solution was failing on pretest 2?

n^2 solution passes

This is one of my submissions, which should be correct as far as I could think of : 66909918.

Try AMGMG,AGM

As far as I know it is a number where if you don't MOD correctly it fails. Thats how I fixed it, I implemented standerd MOD methods.66924381

For me, on replacing $$$x \% p$$$ by $$$(x \% p + p) \% p$$$, I got AC.

what dp in D? I hardcoded the cases of ans = 4/3/2/1/0, and that seemed to pass..

Looking at the scoreboard, D doesn't seem so standard.

Although, in my opinion the problem statement is really bad. It's so long for an actually very natural problem. The definitions slowed me down so much especially because they use silly names like "village".

How you solved D with dp ?

Shouldn't an hour be enough to code up a "super standard dp problem"? :P

Yeah, D is trivial once you notice that combining the DP for the left ($$$L$$$) and right ($$$R$$$) subtrees in time $$$\mathcal{O}(|L| |R|)$$$ is $$$\mathcal{O}(|T|^{2})$$$ work for any tree $$$T$$$.

Just calculate for every subtree the values $$$DP[k]$$$: The maximum pair $$$(c, s)$$$, where $$$c$$$ is the amount of other villages in the subtree with more wasp than bee voters, and $$$s$$$ is the sum of the village the current node is in, when we have exactly $$$k$$$ villages in the subtree.

$$$\mathcal{O}(n^{2})$$$ is fast enough, as then we do in the worst case around $$$3000^{2} \cdot \frac{10^{5}}{3000} = 3 \cdot 10^{8}$$$ work.

Can somebody help me why my submission to Div2 C that is Div1 A is getting TLE on test 6 when I am using similar thing as antontrygubO_o

https://codeforces.net/contest/1281/submission/66931104

Same. In one case check I used r instead of c and vice versa and during whole contest trying to find a case where my solution is wrong.

Does it matter?

Yeah, I got TLE for using mod.

Can I ask for rejudge or something like it? If yes, how?

just construct the minimal word you can and compare with the target.

It's system testing now...

because System testing ~

I think separating linear walk in a tree work for Min case . For Max case take edge which separates tree into two parts and get answer as the sum of subtree size * edgeWT , for all edges ;

Can you share the approach to Div1 C? And also links to similar problems..

Only implementation. I literally just implemented the operations, except the fact that if string length (which is always increasing very quickly) becomes $$$>x$$$, I didn't actually update the string, rather just updated the $$$length \% MOD$$$ of the string. And as the MOD-ed length can be less than $$$l$$$, be careful of that. My submission if you want: 66928873

Cut and paste until the string length is equal x.

suppose, x = 7 and given string is "231" then construct the string it doesn't reach "2313113".

Then iterate the whole string and increase the length if necessary.

initially, length = length of the given string and we can assume that first index of the constructing string is 0 and last index x-1.

For every character,

If the character is '1' then length remains the same.

If the character is '2' then length = i+1 + ((length-i-1)*2);

If the character is '3' then length = i+1 + ((length-i-1)*3);

Don't forget to use modulus.

My solution — > https://codeforces.net/contest/1281/submission/66937956

In theory of course, but it depends on how your solutions works. If you have a general algorithm that handle any weight min/max is just the same.

In this particular case my two solutions (for min and max) work for positive weight only, and I believe it was intended, so the answer to your question for this problem is no.

Were you able to solve it in O(N)?

If there are no A's then you can not convert the matrix, so answer for this case is 'MORTAL'. otherwise, check for each row and column whether you can convert this row or column into all A's. If yes, then using this row or column you can convert entire matrix into A's. Take minimum at every step.

but predefined substr string function also takes O(n)...