I think NBAH posted it on his blog by mistake. It should be fixed soon.

You were finally heard.

Good luck!

Good luck!
It helped to my friend bktl1love on his last comment ... )

yes that sucks. 1-3 minutes is ok but 15-20 is too much

let's hope so.

Wish you can get high rating!

It's asked You had better ask "Is it DATED?"

Did you see NBAH's wish "_High ratings to everybody!_" in the last line of the announcement.**???**

if(yes){

Why couldn't you realize that this contest is rated.

}

else{

Read again!

}

B as well.

typical Div 1.5

I would agree. The problems were way too difficult, especially B and C. Goodbye rating :(

DP[position in permutation][is current permutation already grater than a flag (0 or 1)][is current permutation already less than b flag (0 or 1)].

Consider a function f(stringx, 26 - numbers) which returns number of strings s constructed with characters which is given in the input, that s < x

f(x, 26numbers) can be solved using the first position that you said and the answer is f(b, (a - characters)) - f(a, (a - characters)) - 1

I'm agree with you

I think it is because you are always propagating and you only have to do it when it is necessary(i.e. lazy[nodo] != 0)

You need to think about the case k = 0

I was also stuck on the 8th pretest. It has k == 0, which may lead to WA for some programs if you don't take care of the case.

Even I got wrong answer on 8th pretest. I just handled the special case for k = 0 and the pretests passed

You need to choose subarray not subsequence.

Because segments have to be continuous

It said "continuous" pieces......I didn't catch that "continuous" first and was hacked at 1:30 ..........

Why 2^N? I think N^2.

In E, notice how the update affects any particular value. Assume we store the expected value at each index at current time. Now we have to deal with an update.

Consider any value in the left subarray. Let size of left and right subarrays be S1 and S2 respectively.
final_value = (S1-1)/S1 * previous_value + (sum of values in right subarray)/(S1*S2)

Similar argument can be used for all values in the right subarray as well.
Simulate these operations using a segment tree and lazy propagation.

Code

The number is perfect square iff all prime degrees are even. So you can do dp with bitmask since there is only 19 primes until 70.

edit:wait nm this is too complicated lol

If some number is prime and >35, then it's only prime is itself.

Otherwise, it can be decomposed into the first 11 primes (up to 31). Build a bitmask for each number where mask[i] = the parity of number of times the i'th prime divides the number.

Now do dp(first i numbers, xor value of j) dp (it's like knapsack). Use the sliding window thing to save memory. This takes care of first 11 primes. Take ans = dp(n,0)

For the rest of the primes, they need to occur an even number of times in a subset. So if there are count(p) occurrences of prime p, p>=37, then you can do this 2^(count(p)-1) ways (it's p choose 0 + p choose 2 + ...). So just multiply this together for each prime p, 37<=p<70, and multiply by res and subtract 1 for the empty case.

Nope! Great problems. I've never failed at B so hard tbh... but C was a lot of fun, only if I could finish my dp in time. Great problems.

Sad! I forgot that "sectors should be continuous" and submitted something useless :(

Select a continuous subsegment such that the difference between the sum of the selected slices and the sum of the unselected slices is as small as possible.

The problem gives you N pieces of pizza, with sizes in array 'a'. The sum of all these sizes add up to 360. Now, the problem is asking for the minimum difference between 2 section if we split the pizza into 2 contiguous sections. We can start from position 1 and iterate through, keep track of the sum before called 'SUM'. Since we know the total sum is 360, we can find the sum of the other piece by doing 360 — SUM. We then take ans = min(ans, abs(SUM — (360 — SUM)). The pizza is circular, so we can start from all possible starting positions (1...n) and do the same thing. The answer is then the minimum over all starting positions.

In problem A you can use dp, or just calculate the minimum sum, by(pseudo) cyclic shift. More in my code: Click

How to solve C?

i also used map.. but i used map<long long,long long>. i'm not sure it will pass or not :(

got ac bro :D

Handle k = 0 and duplicates in the array.

6

70 20 50 50 80 90

9

5 3 1\n 1 2 3 4 5 ans is 9.your code prints 31.

You have a double for loop from 1 to n, so the code runs in O(N^2) time. Since n = 10^5, you need O(NlogN) or similar. (In general, less than 10^8 or 10^9 operations is safe)

Afaik distance works in o(n) with std::set.

std::distance works in O (N) . So your code works in O (N^2).

P.S. std::distance is same as using 'it++' several times.

I got WA in pretest 8 because I was taking a subsequence (not consecutive values).

Why don't announce this change? NBAH

That's a huge error, they have to address it.

Spent the whole contest in this problem ...

It should've been announced.Even I solved the earlier version until i reread it in the last few minutes.

Solving for the number of unordered pairs is no different from ordered pairs since if (i,j) fulfills the condition Ai <= Aj then (j,i) doesn't, unless of course i is equal to j

Yes, That should pass.

If we use naive bitmask dp for each prime, it is O (N)*2^19 (because there are 19 primes between 1 and 70) which results time exceed. The idea is if the number is a prime which exceed 35, it must be grouped with a same number. So it can be pre-processed. Since there are 11 primes between 1 and 35, this solution is O (N)*2^11 which gives AC. P.S.Be careful of using % while implmenting it -it gives TLE