My Rating is dead.

I got stuck o B, please help!!

my laptop is on fire send the firefighters

Just a small thing, sir!

become specialist in this one, canon event

Thanks, But i think is about how dramatic is => how enjoyable the contest ARE?

You can talk when you become master.

When did Nemanja or I gain the reputation of being "that guy"?

As a tester, NemanjaSo2005 Riblji_Keksic orz for being Serbian!

Contestants with aot profile pictures have +200% chance to have positive delta on the rounds I author.

Yeah, it is actually NP hard, so if you solve it you prove P=NP.

Thanks for pointing it out. I corrected it.

rainboy round :(

Seems like F > A + B + C + D + E

Почему

We made just small changes to make problem more understandable. If you knew what problem A was originally you would understand what testers are for.

In which way exactly it is obvious for you if you do not know the theory? Can you please explain the "obvious main idea?"

How is b related to that puzzle?

Per-leaf approaches can die vs. trees shaped like long-handled brooms. Your early-out will only work if the earlier answers are better than the ones that come afterwards. Otherwise, it's possible to get stuck traversing the treetrunk/broomhandle repeatedly as you improve your overall answer for each leaf.

To avoid this, you can use the return/post portion of a dfs, or you can do a full topological sort. Basically you want to avoid repeatedly processing vertices, but you also want to make sure a vertex is processed after all of its children.

i got stuck on this for a whole hour lol ;-;

Bassically, first get the mod 2 of them, if they are all equal the answer is "1 1 1", else, the answer is the number with a different mod of the other two.

sorry for bad english.

why this works? i don't now, proved by AC

i don't know if it an intended solution but u can solve it with dp: https://mirror.codeforces.com/contest/1900/submission/234459457

Isn't my solution at most works in O(2 * (10 ^ 7))? Shouldn't it fit in the time limit?

It took me ages to even understand C :/.

I just read it and it doesn't seem in any way similar, unless I don't know actual solution. However, i don't think that comparing the trick used in solution/solution itself is best way to describe similarity of two problems.

Still, I may miss something, so could you please elaborate about what exactly they're similar in? =)

Yes, I think N choose 3 < long long max

$$$\binom{80\,000}{3}\cdot100\,000\approx8.5\cdot10^{18}$$$

$$$2^{63}-1\approx9.2\cdot10^{18}$$$

I thought of this too. There can be multiple longest paths in a DAG

This method is correct, at least I have temporarily passed it

1->2 1->3 2->4 3->4 There are two logest paths in a DAG 1->2->4 and 1->3->4

The graph may not necessarily be connected, therefore there might be multiple paths with the same longest length but different weights.

Yes. Then you can store dp as pair {length, sum} and update it as the statement requires it.

Кстати, стоимость просят минимизировать т.к. у тебя может быть более одного множества вершин формирующих путь максимальной длины и соответственно на этом и строится задача, хотя ограничение довольно искусственное, но без него задача была бы слишком стандартной наверное)

i think its something along the lines of:

• figuring out that at most O(logn) operations will be done on an array A
• do the operations on the whole array and memorize the array after every query, lets call A_k array A after k operations
• to solve queries [L,R], if you consider just the elements of A_1 in [L,R], lets call the array of those elements B, you can see at most 2 elements(one from the front and one from the back) should be added to B
• then you can just simulate the queries(smartly) only looking at the left and right boundaries and maintaining the left and right boundary in A_k that corresponds to the array that is left after simulating k operations on the array in interval [L,R] in A

UPD: you will also have to add O(logn) elements to the front and the back of the array that you are maintaining in the query while simulating the operations(because some elements from the begining and the end of your query interval could have been deleted by the rest of your array)

I saw someone solve it with mobius, although i know nothing about it. Do I really need to know mobius to reach expert, I solved ABC in 19 minutes?

I solved it without mobius (hopefully :)

Hint: iterate over all possible GCDs

problem D was a combination of number theory(gcd), combinatorics and inclusion-exclusion principle

problem E was a combination of graph theory(for SCC compression) and simple DP on DAG(to calculate maximum length of a path and its smallest value)

Did you end up solving it using mobius?

Do you really need that for D?

Calculating the sum of (gcd) of the two smallest numbers in all three-member subsets of a given set.

Problem D is pretty like to this 1884D - Считалочка problem. There we should use a trick with inclusion-exclusion in dp for calculating all pairs of integers, that have fixed gcd. But these two problems are different from classical problem and we should modificate this dp.

Pass the string s in dfs() by reference too. Solution Accepted

I think you got a bit unlucky, pass the string by reference in dfs and you should get AC. Creating a linear copy of string in each dfs call made it $$$O(n^2)$$$.