yAs iT iS rAtEd

Old way to get downvotes man be creative like me! I'm the master of downvotes in CF you can see my blogs or my comments to learn more about downvotes

Mind = blown

That too with two Div1 contests in two days. I was sad that I was unable to give yesterday's round, but seems fine now.

Can't compete this contest :(

So?

I think so.

why?

Their history also shows that no scoring has been ever announced.

yes

You are still waiting for somebody to explain you the puns? You could have already started learning Russian!

Are you considering the contest TooNewbie?

Make sure you are not overcounting the subarrays. Try this test case: n = 3, a = [2, 4, 4].

First, convert princes to nodes, and princesses to edges. You can show if the set of edges is a valid solution if and only if it is a psuedoforest (https://en.wikipedia.org/wiki/Pseudoforest ). So, it suffices to find the max weight pseudoforest.

It turns out this is a matroid, so adding edges greedily works. All we need is an efficient way to check that each connected component has at most one cycle.

Lewin is absolutely correct, though this approach may be described from a different point of view without matroid theory.

Consider a princess that is the best match for both of her princes. In an optimal solution this princess should be covered with an edge (otherwise we may force one of her princes to marry her and it will be at least the same profitable).

It turns out that we may remove such princess from a graph (adding her value to the answer) and contract two her princes into a single super-prince having the union of edges of the original princes. It's easy to prove that it is an equivalent transformation.

It leads to exactly the same solution that uses DSU to keep contracted princes.

Hint : What is the number with maximum sum of digits?

Note that numbers up to 10^9 have at most 9 digits. So the maximum we can add to a number is 9x9 = 81 (putting 9 in every digit).

Therefore we can just bruteforce 100 numbers (just to be safe) from n-100 to n checking if each one of them + the sum of the digits equals n.

My incredibly overcomplicated approach is this:

We can represent any number x as a₀ + 10a₁ + 10²a₂ + ... + 10ⁿa_n. If we add a number's digits to itself, we will obtain a number k = 2a₀ + 11a₁ + ... + (10ⁿ + 1)a_n.
Let's fix a₀, a₁, a₂, a₃, a₄ = 0, and try all possible combinations of (a₅, a₆, a₇, a₈), generating all 10⁴ integers k = (10⁵ + 1)a₅ + (10⁶ + 1)a₆ + (10⁷ + 1)a₇ + (10⁸ + 1)a₈ and storing them in a map. Then, we can fix a₅, a₆, a₇, a₈ = 0, then try all combinations of (a₀, a₁, a₂, a₃, a₄) in the same way. For every integer k generated in this step, we can just check if n - k exists in the map we created before.
Complexity: O(10⁵log(10⁵)).

Let consider sum(x), sum(x) is the sum of the digits of the number x

x + sum(x) = n

x = n - sum(x)

it's mean that you can just do bruteforce by the sum of the digits.

Let maintain current sum as cursum, if sum(n - cursum) = cursum, we add n - cursum to our answer

Complexity O(log(n) * max_sum)

I did it too, much easier to code :P

After 2 wrong submisssions, I give up greedy and solve A with DP.

me too.

You're not alone :D

I was hacked on the case when I tried to set to some letter that it should be capitalized don't paying attention that this letter can be already marked as a letter that cannot be capitalized.

I failed in test case 62 31410790

4 5
2 1 5
2 1 4
2 2 3
2 2 5

I reduced 5 to satisfy 5->4 but did not reduce 3 so 3->5 became unsorted. My solution got accepted by running the recursion twice 31414586.

I think the accepted solution is still incorrect. If there are three items I need to be reduced instead of two then I need to run the recursion 3 times. I guess there are no test case of such scenarios.

Maybe the author just wants to see if there is anyone doesn't see the f problem from beginning to end

Unrated contest :P ?

div1b was pretty easy . maybe like div2b

I too used a SegTree. Not Binary seaching though. Was really blown when I saw the actual solution!

why binary search? I maintained the rightmost position of zero in one segment tree and count of ones in an interval in another segment tree. So, the answer is just 1 plus count of number of ones present before the rightmost position of zero.

I used BIT+binary search

I thought it would fail as number of iterations were > 1e8,but it still passed in 218 ms :D :D

I just keep tracking on the rightmost consecutive X's and my solution passed in 156ms :)

Build a graph on letters which should be updated together. If the strings are different, there is only one pair of letters, which decides that the previous string is lex smaller than the next one.

123

124

Add edge 4->3 to the graph, which means, that if you capitalize 4, you have to capitalize 3 too.

125

124

You must capitalize 5 and you can't capitalize 4.

In the end run dfs from every letter you must capitalize. Check that the letter which can't be capitalized, was not capitalized.

I also checked special case

1245

124

Which gives no immediatelly.

2-sat.

That's me!

Magolor orzzzz

access denied, fix pls

Can't tell for Gleb and Michael, nontheless, I should have participated in that contest as a training around 2013. Of course I didn't remember this problem until this moment, otherwise we wouldn't have taken it in Codeforces round :)

Almost 6 years is a long time period. Not sure if it is possible to remember all problems since you have started participanting in a programming contest. This problem in particular was suggested for a contest as an easier version of wilwell course work.

PS so to me seems like a notorious coincidence.

because (a — b) % m = (a % m) — (b % m) (and + m if it is negative). We save numbers (a, b) which have same remainder (x). a % m = x and b % m = x => (a — b) % m = x — x = 0 (that's we need). And it works for all pairs {a, b} if they have same remainder.

Editorial will appear soon, but you can refer to this comment tree right now.

start placing the numbers in decreasing order on the array now for each number that you put find out how many new intervals you can choose which contains this number . now its obvious that these intervals cannot include any of the already placed numbers (you can find the bound easily by std::set) now for each j that the current number & pow(2 , j) = 0 find the first place after and before the current place that number y & pow(2 , j) = 1 . now you have two intervals . just some conditions and AC

I solved it in almost the same manner as from the recent 1418G - Three Occurrences. My code here : 95019408