As a not tester and not participant and shin chan supremacist, gimme downvotes.

surprising

Don't hope for easy A. Hope for surviving hard A's. Hope for becoming strong.

lol

That definitely not the toughest. But yeah it was on the harder side for sure.

+1

C and D are like leetcode mediums

how to do B ?

Where can I get the solution please

do you mind sending me code for A,B,C? can you do that or that will violent the rules?

Let's say there is an edge from $$$x$$$ to $$$y$$$ iff $$$a[i][x] \lt a[i][y]$$$ for all $$$1 \leq i \leq m$$$

Building the graph can take $$$O(mn^2)$$$ time, but we can optimize it with bitset $$$O(\frac{mn^2}{64})$$$.

The graph we have is DAG, so you can do dp.

use bitset

A looks cool isnt it?

actually, A was a different task when i tested, and probably a harder one.

I feel both are fine for div2A though....

I think it's quite balanced for div2

A lot of testcases with big n, m should hint to you to think of a math solution. if m == 1, we can just print("YES"), otherwise,

Notice that if n can divide any number from 2 to m, the worst strategy is to always choose the number of boxes that divide n, that way it will repeat forever. If not, you can never choose suitable boxes as they will all not divide with n.

Therefore, we can just check if the prime divisors of n are all > m, if so, we print "YES" else print "NO"

For C, do casework for m and n.

For D, try to write the answer function in a different way.

C: how to make a tie? when it's possile to tie?

D: Look from middle to both left/right sides.

Codeforces problemset section

And just after that you got TLE on the same test. Really cool.

What is the proof of C ?

Well it's less complicated than DP.

Hint: look from middle.

Yes it is dp problem.

Till index i, suppose u have taken 2 values, what is the best you can do, => dp[i][2]

and suppose till index i, u have taken one value, what is the best you can do => dp[i][1]

fill in the DP from above state.

I solved i5 using DP, let dp[i][j] be the max sum that can be made using the first i light where we have picked j lights till now. j can be 1,2 or 3. Code

Enumerate possible answers and verify them one by one.

Bonus: you can do better than pure brutal-force. Although it's not needed given the data scale.

We can brute force on the number of liars. lets call this number x. We go from x = 0 to n

So lets check, is 0 liars possible? 1 liar possible? is 2 liars possible? and so on. We run through the array, checking if arr[i] > x, that person is lying for that value of x, because they are saying that there are at least arr[i] liars. We increase the liar count

Now, if the liar count == our projected value of liars x, we print x. Otherwise, we cannot determine the liars, so we print -1.

https://codeforces.me/contest/1826/submission/204635985

Yea this A was a complete shitshow. Since it's been solved by less than 5000 people, I think this problem A takes the reward for the hardest A since America was discovered.

after spending more than hour and 3 Wa the solution is very easy , you can just brute force all possible number of liars from i = 0 to i = n and count every one who said that there is a bigger number of liars as a liar(cnt++) if the counter of liars == i then thats your answer

I looked at your submission and you found primes up to $$$10^6$$$ when you only need to find primes up to $$$10^3$$$.

This is because you only need to find the lowest prime factor, and the lowest prime factor of a number $$$n$$$ is at most $$$\sqrt{n}$$$

As a result, in the worst case, you need to check every single prime up to $$$10^6$$$ for each test case. And there are roughly $$$8\times 10^4$$$ primes that you need to check in that case. Given that there are $$$10^5$$$ testcases, this is far too slow.

congrats :)

What I tried was, first sort all people by the first city. Now we have permutation [0,1,...N]. I sort this permutation by every city, while ensuring that inversions are always created and never destroyed. This is because for some person X > person Y, this should hold in every city. So inversion created in any one city always stays. After sorting by every city we can simply take LIS. But I didn't get AC

I mis-implement the biset so it OOM for me... rather than solve the OOM issue, I chose to sqrt-decomp it but failed to finish before deadline. With sqrt-decomp it should get O(mnlogn, n^2, m*n*sqrt(n))~=O(m*n*sqrt(n)).

It may seem obvious, but in problem A you can get non-brut force solution if you sort all numbers in non-ascending order and without loss of generality assume that liars told the first k numbers, and try to find maximum possible k.