My Rating is dead.

I got stuck o B, please help!!

my laptop is on fire send the firefighters

Just a small thing, sir!

Hope we'll enjoy the round.

become specialist in this one, canon event

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

RIP

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.

ref.1
ref.2

same here

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?"

omg penguin in your avatar looks so much like me:P

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.

How to optimise O(n^2) solution is the better question

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

Let the total sum of all 3 numbers be X. Now if we exclude 1st number i.e X-a1. if this number modulo 2 is 0, we can remove pairs i.e two numbers from the other 2 numbers and we can get all numbers with color a1. Similarly check for other 2 numbers

B was kind of tricky for me at start but the approach that i come up with while giving contest was let a,b,c be the no.'s if any two of them have diff%2==0 then other one will be marked as 1 if all three are having even diff then all will be marked as 1

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

I used a method using even/odd. I solved some test cases of my own and found out that when theres 2 evens the one that is odd is the only one that can be the result any way u solve. same if theres 2 odds. also found that it can never result in 2 of them being 1's.. and the last scenario that remains is that if all are even or odd. then its ( 1 , 1 , 1 )

input -> a(1) b(2) c(3)

//consider a

if (abs(b-c)%2 == 0) print 1 else print 0

//consider b

if (abs(a-c)%2 == 0) print 1 else print 0

//consider c

if (abs(a-b)%2 == 0) print 1 else print 0

because we can tranfrom all of other two numbers to the number we consider -example we consider A

1.we operate B and C to A(tranfrom B,C to A) the remaining of this operate is abs(B-C)

2.we operate a remaining with A and operate again with a remaining then we get A (this operation need two remainings and we can do this until we run out the remaining)

3.so if the remaining of abs(B-C) is even,array will not have a remaining.

sry for bad english

BEST EXPLAINATION EVER :P

Let's solve for digit $$$1$$$.

If there is atleast one $$$2$$$ on the board, u can use that to delete one $$$3$$$ and add an extra $$$1$$$ on the board. Using this extra $$$1$$$ and one more $$$3$$$, we can create the lost $$$2$$$ back on the board.

So, if u see the pattern, we can use one digit of some type (in this case digit $$$2$$$) to reduce the other type (in this case digit $$$3$$$) by $$$2$$$ in each step, so all it remains is the remainder with $$$2$$$ i.e., $$$c \% 2$$$

Similarly if there is atleast one $$$3$$$ on the board, use it to reduce the $$$2$$$ to $$$b \% 2$$$.

Now, that both have been reduced to their remainder with $$$2$$$, it is only possible to completely erase them if both are either $$$0$$$ or $$$1$$$ i.e., $$$b\%2==c\%2$$$.

Similarly, you can do for digit $$$2$$$ and digit $$$3$$$ as well. Here is my code.

no of 1 = a no of 2 = b no of 3 = c

if you want to remove 2s and 3s completely you have to make b = c. This is only possible if |b-c| is even. Ex: let a = 25, b = 9, c= 19. Apply operation to 2s and 3s Five times. You would get a = 20, b = 14, c = 14. Apply operation on 2s and 3s 14 times and you will be left with only 1s. Check this with |a-c| and |a-b|.

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