Best of luck bro

What F*ckhead created problem C ?

XD

it's more related for problem C

same, but expert instead of pupil

I am hoping to become pupil for the first time.

haha

good luck

We wish you will. Good Luck!

Wait I think I have seen it somewhere :)

We wish you will. Good Luck!

You just used this in real life by making this meme

You couldn't solve it doesn't mean the problem was bad.

I've just simulated it; iterating through from k = 100 to k = 0, if Alice wins then print out the k and return

Binarysearch, with greedily picking Alice the biggest less than or equal to k-i+1, and Bob picking lowest left value. Storing values in multiset.

To win a game with k turns, the array must have at least k '1', and at least 1 number that is smaller or equal to 2, 3, ..., k. This is because Bob can use a strategy to lock the final move out by adding to each '1' once. Therefore, Bob can lock at most (k-1) '1', so the array must have k '1' to compensate. From there, just search out for the solution!

C can also be solved in $$$O(n)$$$ time without using Binary Search. The important observation to make here is that during the $$$k^{th}$$$ stage Alice must remove an element $$$1$$$ from the array. Thus, the optimal strategy for Bob is to always remove $$$1$$$ (by adding $$$k-i+1$$$ to it) at every turn. If the count of $$$1$$$'s becomes zero before the $$$k^{th}$$$ stage is reached, Bob automatically wins.

Hence, we store the frequency of every element $$$a[i]$$$ in an array $$$cnt$$$. Note that the answer is zero iff $$$cnt[1] = 0$$$ else the answer will be $$$\geq 1$$$. Now, we iterate over every $$$k$$$ from $$$2$$$ to $$$n$$$, while maintaining a counter $$$cur$$$ which stores the number of elements $$$\geq 2$$$ and $$$\leq k$$$ which have not been deleted yet. In every round, Alice must delete a number $$$\leq k$$$, so if $$$cur > 0$$$ we decrement $$$cur$$$, otherwise we decrement $$$cnt[1]$$$. We then decrement $$$cnt[1]$$$ to account for Bob's move. Now, if at this point $$$cnt[1] \geq 1$$$ then Alice can always make her final move and win if she chooses to play $$$k$$$ rounds. So we update $$$ans$$$.

Submission: 177175786

UPD 1: Why is a move by Bob equivalent to removing an element from the array?

Claim: Any element modified by Bob in the $$$i^{th}$$$ round cannot be removed by Alice in any further round.

Proof: Let Bob modify the element $$$a[j]$$$ in the $$$i^{th}$$$ round. Therefore $$$a[j]$$$ changes to $$$a[j] + (k - i + 1)$$$. Note that in the following rounds, all the elements Alice removes are $$$\leq {k - i + 1}$$$.
However, from problem constraints,

Hence, the Claim is proved, and we can say, for the purposes of the solution, that the element has been "removed" from the array.

Binary search

bob can win iff he can destroy all 1 in the array while alice kept choosing the largest possible option, then simulate with two pointers

Video Solution for Problem C and Problem D

Yeah, I tried many examples for last 30 mins but couldn't really figure out the counter example. I wish I could see the test 2 now...

UPD: this was invalid testcase. Look at the comment just below it for a test case

I think C is just a C, as always

The issue is the range of m. For example, you multiply by m/2. Use (m/2)%MOD instead.

It's a shortest path problem, you need to find a path of '#' connecting the left side of the grid to the right side. All cells on the path must have the same color if we colored the grid like a chess board. Also you can't have 2 '#' beside each other, so some cells are "banned" of ever becoming '#' (because of the initial placement of '#'). After coding these constraints, it becomes simple dijkstra or 0-1 bfs.

no

Maybe this bad will be fixed

6 6
.#....
#.#...
...#..
..#...
...#.#
....#.

ll nam = (m * (m/2)) % MOD;

Doesn't it overflow?

Why is this true?
In a non-ambiguous array, the ith element must be divisible by the product of all prime numbers <= i let say ith is 6 and element is 8. gcd(8,6) is 2 but 8 is not divisible by 3.

array here is 1 1 1 1 1 8

Also you can check for such overflows by compiling with the flag -fsanitize=signed-integer-overflow. Helped me debug the exact same error

It's optimal for Alice to always pick the largest valid number, while Bob always picks the smallest number. This means Bob will eliminate the smallest $$$k - 1$$$ numbers. Therefore, if Alice can win, she can win by picking only the $$$k$$$ numbers that are after the first $$$k - 1$$$ numbers in sorted order. In other words, she can pick the $$$k$$$-th number when her upper bound is 1, she can pick the $$$(k + 1)$$$-th number when her upper bound is 2, she can pick the $$$(k + 2)$$$-th number when her upper bound is 3, and so on.

We can binary search to find the largest $$$k$$$ that fulfills this condition. My submission: 177165675

With how small $$$n$$$ is, a simple linear check for each $$$k$$$ should work too (instead of binary searching).

In Line 16: curr=(curr*m)%MOD; can overflow, since $$$m$$$ is so freaking huge. You should apply the MOD on $$$m$$$ first, before multiplying.

Changing it to curr=(curr*(m % MOD))%MOD; passes the fourth test case, and will probably be Accepted.

Exactly man! Now I too made the same observation, now just see that since the product of first $$$12$$$ primes (upto $$$37$$$) is greater than $$$1e12$$$ $$$(m < 1e12)$$$, so any array of size > $$$37$$$ must contain an element $$$a[i]$$$ which would not be a multiple of some prime $$$p \le i$$$. So, any array of size > $$$37$$$ must be ambigious

In an un-ambiguous array, the $$$i^{th}$$$ element must have $$$gcd>1$$$ with all $$$2\leq j\leq i$$$. This means it should be divisible by all primes $$$\leq i$$$*. The count of values $$$\leq m$$$ that are divisible by all primes $$$\leq i$$$ is $$$\lfloor \dfrac{m}{\prod_{j=1}^{j=i}{j\cdot isPrime(j)}}\rfloor$$$.

*Why the $$$i^{th}$$$ element should be divisible by all primes $$$\leq i$$$: In an un-ambiguous removal sequence, the $$$i^{th}$$$ element's position will decrease by $$$1$$$ after each removal. So, it will hit all the prime positions $$$\leq i$$$, and any composite position $$$\leq i$$$ is just a combination of primes $$$\leq i$$$.

keep the largest b value greedy. ur right

To throw you off??

we will calculate it until lcm<=m (m<=1e12) .if lcm>m there will always be ambigous solution.

so there wont be overflow

You add to both neighbors if it has two neighbors. Also, to get 242, u remove the left 3 then remove the right 3 and then remove middle.

remove the elements in this order 7 5 6 1 2 3 4

you will get 242

we should add its strength to both neighbors

The answer is the sum of all $$$a[i]$$$ and $$$b[i]$$$ minus the largest $$$b[i]$$$.

This is because you can always kill an enemy who is currently at either the left end or the right end, so the $$$b[i]$$$ gets added only to one enemy, and never to two enemies. The last enemy you kill will not have their $$$b[i]$$$ added, so the optimal choice is for the maximum $$$b[i]$$$ to be the last enemy to kill.

So one solution here is to kill the first three from left to right (each $$$b[i]$$$ gets added to only one enemy), then the last three from right to left (again, only added to one enemy), and then finally kill the remaining element (which has the maximum $$$b[i]$$$, but it is not added to anyone's health, due to being killed last).

after getting WA on test 3 *

Was A really a good problem? All you had to check was n == m.

You are pretty close. Just think about is there any array with zero or one removal sequence?

At least two is equivalent to excluding zero and one.

Copied from my other post:

D. Counting Arrays

That's a number you're outputting; it's not from the input.

Never post code like this way. You should use link of the code.

.

Is there a way to see the editorial or others submissions for this contest?

What are you say?Fuck you................................

are you sure????

It is the correct solution.