I trust u.

This round will be rated for the participants with rating lower than 2100

And I've been banned for crawling...

What's crawling?

I hope you reach Cyan in this contest

i hope too

I hope you reach it :)

why unrated? trust yourself

click to see all of the contest registrants, and there is a button for changing to unrated

click to see all of the contest registrants, and there is a button for changing to unrated

agree with you. To me, E1 is much easier than D.

Can u give me some hints for E1? I don't know I made some observations but feel stuck now.

Looks like I found you again mate while scrolling, keep trying man you will make it to green. Also try to solve problems in an organized matter like do usaco they have cf problems and ones from other sites organized in every category. Like for example c was just dp nothing else as simple as that you just have to do some for a long time in the usaco

Just iterate on all $$$x \leq 3e5$$$.

you could consider every element in array, and check how many of its multiple exists in arrray. worse case array is [1,2,...,2e5] so 1st element takes N iterations 2nd element takes N/2 iterations so on, its just O(NlogN) now just check which x is optimal.

example: 50 150 450 x = 3 is optimal since 50*3 exists, and 150*3 exists, so you could get 2 items for free just maintain some freq array where fr[i] tells how many if x = i, how many items you get free

Hi there, this is my solution for D. So you will try all X, if you have X, there 200000/X value that you can potentially keep. Now let say one of these value you can keep as J.If you divide all C[i] by X.All C[i] that has value from (J-1)*X+1 to J*X will become J.And the number of sign you can save is MIN(C[J],Number of sign from (J-1)*X+1 to J*X. Now that we have a solution, how do we know this can run in allowed time constraint. Let's say our complexity is 2e5/1 + 2e5/2 +...+2e5/2e5. This sum shall be equal to 2e5LOG. Hope this help.

Because Scanner is slow.

There is always a solution, so the minimum answer is 2. First, create a valid solution for both arrays, then see if you can swap any position. If you can, just multiply by 2 each time. 338832246

dp[0][1] would be 1, no?

dp[0][1] = 0; is wrong i guess it should also be initialized to 1

You are doing modular arithmetic wrong first and third additions are wrong while second and forth are correct

NOOOOOOOOOOOOOOOOOOO (it's so over I can't even write the compilation command right)

I think changing the position of -o will fix the problem: g++ E.cpp -o E

Consider some final price, p. Now for some i, p = ceil(c[i] / x). Now, it's easy to see that we will get the same price p for not only c[i] costs but for a range of costs. Suppose x = 5, then ceil(50 / 5) = ceil(49 / 5) = ceil(48 / 5) = ceil(47 / 5) = ceil(46 / 5) = 10. So, a good idea is : we can find the range and work on how many times the elements in that range will appear in the original array.

p — 1 < c[i] / x <= p -> c[i] ∈ [(p — 1) * x, p * x]; x ∈ [2, max_cost]

We can simply store the frequency of each cost in a frq array and make another prefix sum array called pref such that pref[j] — pref[i — 1] = Number of occurrences of elements from the range i to j. Then iterate over all x and get the new sum of the array of costs. For each value of x, we'll get a result = sum — y * (n — cnt); where cnt = Number of elements in the range [x * (p — 1) + 1, p * x], p is calculated for the corresponding x. Finally maximize the ans. ans = max(ans, result); Time Complexity = O(max * log(max));

you are not stupid, you just make it too hard sometimes

you just have to look at the problem from a different angle

also A is 1000 in my opinion!

try to solve the problem in O(n)

very simple

for each ai , bi or there is either 1 way or there are 2 ways (you can swap)

try greedy

What does $$$2^{dp[j]}$$$ mean here? It seems too big.

• For each position i, we have two choices:

1. Do not swap: Keep (a[i], b[i]) as is.
2. Swap: Make it (b[i], a[i]).

• We must ensure that after all decisions, both arrays are sorted.

• We need a DP-based solution since trying all 2^n subsets explicitly is too slow.

dp[i][0] = number of valid ways to reach index i where we do NOT swap a[i], b[i]

dp[i][1] = number of valid ways to reach index i where we DO swap a[i], b[i]

dp[1][0] = dp[1][1] = 1; At the first position, both swap and no-swap are allowed.

Transition for each i = 2 to n:

- if (a[i] >= a[i - 1] && b[i] >= b[i - 1])
    dp[i][0] += dp[i - 1][0];

- if (a[i] >= b[i - 1] && b[i] >= a[i - 1])
    dp[i][0] += dp[i - 1][1];

- if (b[i] >= a[i - 1] && a[i] >= b[i - 1])
    dp[i][1] += dp[i - 1][0];

- if (b[i] >= b[i - 1] && a[i] >= a[i - 1])
    dp[i][1] += dp[i - 1][1];

Each transition checks if the current pair (either swapped or not) can maintain sorted order from the previous state (either swapped or not).

After processing all indices, the answer is dp[n][0] + dp[n][1].

Submission : 338809665

me too...

me too..

Wasted whole hour proving $$$O(N\sqrt{N})$$$ solution, but just realized that effort was in vain.

could you explain how we do in O(N * sqrt(N))?

me too... I thought that it's solved by dividing $$$x$$$ by $$$\frac{A_i}{x}$$$

I got it completely wrong...

Also, i didnt get the point of having 10 test cases per test without any limit on the sum of n. That can allow 2e6 input elements with 2 sec limit