Thank you ScarletS for carrying

rfpermen will win COMPFEST 15!

Thank you Pyqe for carrying

The round is based.

It's Javanese (a local language in Indonesia) meaning "good luck and have a good score" :D

"good luck and have a good score"

Isn’t that the same thing?

There is still some time left to reschedule the icc world cup, let them know.

haha same

Just iterate over every maximum value $$$g$$$ from $$$1$$$ to $$$10^5$$$. Then, let's say $$$x$$$ = "count of indices that needs to be colored black to get a maximum of $$$g$$$" and $$$y$$$ = "count of indices that when colored black gives a maximum value less than $$$g$$$". Then, the contribution for $$$g$$$ would be $$$c_g = 2^{x + y} - 2^y$$$. Answer is the sum of $$$c_g \cdot g$$$ over all $$$g$$$.

You can use the following formula $$$\sum x*freq[x] = \sum freq[ \gt =x] $$$. RHS means for given x, frequency of elements which are greater than or equal to x.

It will be quite hard to explain. Wait for an editorial.

If we select any index i to make it black we can replace arr[i] with the maximum value at any index j, such that i is a factor of j (because we would always be marking all such j green).

Then we can sort the resulting array, and now for the maximum element to be Kth from this array, we have 2^(k-1)*arr[k] possibilities, we can just calculate this sum for all the elements from 1 to n in the sorted array and take the remainder which would give the ans.

I'll explain my solution, maybe not most efficient. Basically, for each idx we go to the right with step idx to find the maximum value that this idx can lead to after coloring. It is similar to how we use of sieve of eratosthenes, although in our case we do it for every idx, not skipping already visited before. (Let's say idx == 2, we're going to check idxs 2, 4, 6, 8,... and store max value of them. For idx == 4 we're going to check 4, 8, 12,...)

After that we create dictionary value -> amount of idxs (that lead to that value after coloring them with black)

And starting with greates value to lowest, you have value: amount of idxs. Let's say v: k. And let's say amount of possible numbers to choose from is n (it's n in the beginning). Amount of subsequences which contain at least one of numbers from those k numbers is 2 ** n — 2 ** (n — k). (total — amount of subsequences that don't contain at least 1 of those numbers). You multiply it by value v and add it to result. Then you do n -= k, as we don't want to consider those anymore. MOD at the end

fact[now] / (fact[i] * fact[now - i])

Suspicion... I'd rather multiply by inverse of fact[i] * fact[now - i], because fact[now] not necessary dividable by fact[i] * fact[now - i]

I couldn't debug within time, but my approach was:

Consider the usual directed edges (i, A[i]).

If in-deg of a vertex = 0, then it cannot be circled. And so it's out-child has to be circled. And if we know that if a vertex is circled, it cannot circle its out-child, so decrease in-degree of its out-child (and if its in-deg becomes 0, mark it as not-circled, and push into the process-queue).

Keep repeating the above two points, until you end up with no vertex with in-deg = 0. So, in-deg of all 'active vertices' >= 1 and we already know that out-deg = 1 for all. So, in-deg = out-deg = 1 for all active vertices. So it's just a bunch of cycles. Iff all cycles are even, there's a soln.

given graph is cycles with tentacles

first — delete tentacles:

if there is no edges to a[i] ("end of tentacle") — it shouldn't be chosen -> a[a[i]] should be chosen — remember, delete them, decrease in-edges count for a[a[a[i]]] do this while you can — you can keep vertices with 0 edges in the set and add them when some vertex becomes 0 in-edged

ether everything is deleted or there is still untouched cycles

if there is cycle with odd length — cout << "-1". You can understand this from a cycle of length 3

if each cycle has even length — color them 1 0 1 0 1 0

First of all we will try to identify what indices or elements are mandatory to come and what are mandatory to not to come. For this we can make a frequency array and if freq[x]==0 , x as an index can never come in p and because x can never come a[x] must come in uncircled elements and as an index too and a[a[x]] must not come as uncircled elements and so on .... considering all these facts, first of all we need to identify mandatory presence and absence.

After this if there are any a[i]==i pairs or there are odd numberof indices left ans is -1 else an ans always exist.

Yes, that's basically the solution. The only additional thing is that cycles have to be handled carefully.

Process each component of the functional graph individually, for each hanging tree, do subtree dp ($$$dp_{u, 0}$$$ stores if its possible to not pick node $$$u$$$ after picking/not picking nodes from only its subtree and $$$dp_{u, 1}$$$ stores whether its possible to pick it). The transitions are the same as what you have written (its possible to not pick a node if all of its incoming edge nodes are picked, and possible to pick a node if atleast one of its incoming edge nodes are not picked).

Now, we need to check if a valid set of choices for the nodes on a cycle exists.

Pick any one node on the cycle to be the starting node. Fix the choice (not pick/pick) for this particular node, and go along the cycle, maintaining similar dp states (note that these dp states must take into account two things: the last node on the cycle, and the hanging subtree). The transitions are almost the same as when we find dp values for only hanging trees. Check whether there is a valid set of choices for both choices of the starting node.

Finally, you can just store backlinks and find the unpicked nodes to get the final answer. Unfortunately, my implementation is cancerous and belongs on r/EyeBlech.

Nice profile photo.

No answer for cheaters

if k > 3 answer always 0

if k = 1 answer always 1

and you have only to find what if k = 2 and k = 3

if $$$i != n$$$ then $$$a[i] \lt a[i+1]$$$

answer <= 3

True, I had the same feeling.. thought either I am missing some simple observation or most of the submissions are copied.

No, it was comparatively easier also today.

My solution was like this:

If we could find sush uncircled elements such that:

1. for every uncircled element with value x there is circled element with index x

2. for every circled element with index i there is uncircled element with value i

Then it would be easy to find a solution

We can also see that this conditions are neccesary Now we just need to add our conditions to 2sat We will have 2n variables Variables i, 1 <= i <= n will be : 0 — if we doesnt circle element with index i 1 — if we circle element with index i Variables i, n < i <= 2 * n will be:

0 — if we circle all elements with value i

1 — if we doesnt circle all elements with value i We can see that adding clauses is easy now

Correct. Only after System tests.

Yes you'll be able to submit after system testing is completed.