Good

As a participant, I will participate in this round.

As a tester, I tested this round.

I am a participant if and only if I am a participant.

As a participant

ok

i hope so too

spoilerforces moment

penaltyforces

^^ If a protagonist with "the power of friendship" had a CF account

you can start solving problem D , Have a nice Day

Good luck

Everyone can participate in every contest. The only issue is that if your rating is too high, your rating will not be affected by participating in lower-difficulty (higher Division number) contests. But since you're grey, your rating will be affected by all contests. In fact, if your performance is better than what is expected of your low newbie rating, you will very likely have your rating increased. I highly recommend participating in ALL contests.

“Thank ilaburkov for existing”……

ok

Hope I will get some more brain after this contest.

Me too! I got specialist today, and hope I'll get Expert after this round

you're so cringe kid

How about Wrong_answer_on_pretest2 ?

Either that or an extremely easy one, I'm hoping for the latter to allow me to get close to 2100 mark again after AK in Div2. :D

I don't think sharing true info would be fair though, as some participants may opt to do/skip round if the answer favors them.

Yes, Div1 A is Div2 D. We think that this will make our round more balanced.

lol

I'm quite sure the Div2D = Div1A exactly. I doubt there is much to be gleaned from the discrepancy in how the scores are distributed. The Hard version is treated like a Div1A problem (which oranges/reds should be able to solve), with the Easy version being worth exactly half. But for Div2 participants, it's treated as a D problem, which isn't as accessible, especially since ABC would take up some time at first, so it's a little harder to achieve the Hard solution for this Div2D. I guess that may justify giving it slightly more score than the Easy version in Div2, despite being identical to Div1A, and I don't think anything could be inferred by the relative difficulty of the two subtasks beyond the estimate that they're roughly equal.

me too

you know, my rating is not 1200

Can't agree more

Problem B: For k%2==1, just take (1,2), (3,4)... (n-1,n) For k%4==2 again take (1,2), (3,4).... ,but for pair (i,i+1) if (i+1)%4==0, take (i,i+1) else take (i+1,i) For k%4==2 there is no solution

Detail B solution is: look at n%4 and k%4. Then look at pairs mod 4: for example n%4==0, so numbers%4= 1, 2, 3, 0, 1, 2, 3, 0. If k=0 its impossible, k=1: a=3, b=1 and a=2, b=0 — 2 pairs. (so 1st pair a%4=4-k%4, second pair b%4=0)

First of all, lets do k %= 4. If k == 0 there is no answer, idk why.

You can solve this problem from each group of 4 independently:

1000 2

• 2 1
• 3 4

• 6 5
• 7 8

• 10 9
• 11 12

And so on...

Now just some case-work for each k value

Btw, i got B 10 seconds before contest ended (01:59:50 Pretests passed [pretests])

I didn't have time to implement it, but I think D1 can be done using 2D DP.

The key observation is that there is never any benefit to selecting a range of more than 2 elements, since the time taken for a block of size k + 2 is the same as the time taken for doing the block of k and the block of 2 separately. So to zero out an element whose current value is $$$v$$$, you would have to XOR it with $$$v$$$, but you can also choose to drag the next element to be XOR'd with $$$v$$$ (without costing additional time). There is no point in considering a longer range for this XOR.

For an array of size $$$n$$$, consider the last element. You can either zero out the first $$$n - 1$$$ elements (DP) and then zero out the last element by itself, OR you can zero out the first $$$k$$$ elements, and then start an XOR chain from the $$$k + 1$$$-th element, where each element becomes 0 while XORing its next element as well. Depending on where you start the chain, the residue at the end varies, so you can check all possible values of $$$k$$$ to determine which of these XOR chains will zero out the last element and then choose the one with the shortest time.

This takes $$$O(n^2)$$$ time, so it obviously wouldn't work with D2, for which I have no clue whatsoever.

Problem B solution:

For k%4==0 we have that (a+0)*b=0(mod 4) => a*b=0(mod 4), so if a is odd than we have that b must be divisible by 4(we have n/2 odd nubmers from 1 to n and n/4 numbers divisible by 4 from 1 to n), so we have that for k%4==0 there is no solution.

For k%4==1 we have that (a+1)*b=0(mod 4) we can see that we can just print pairs that contains one even and one odd number(like {1,2},{3,4}, etc.)(same approach is for k%4==3(k%2==1))

For k%4==2 (a+2)*b=0(mod 4) than we can split all odd numbers from 1 to n in 2 groups. First group is 1,3,5,7,n/2-1 and the second one is n/2+1,n/2+3,...,n-1. Odd numbers from first group is gonna be first numbers of pairs(a) and the second numbers of that pairs(b) will be numbers that are divisible by 4(than we have pairs like {1,4},{2,8}, etc.). In other half of our pairs second group of odd numbers is second number(b) and the first number(a) is the numbers that gives rest 2 divided by 4.

nichke u can see my approach here

same i guessed a and b

thats true however, its easy to verify the validation of the solution by bruteforcing the solutions however, i feel like the test cases are too weak i forgot to use long long instead of int when calculating ((a + k) * b) % 4 would it pass? ps : never mind i also made k long long ( however a and b is int) thats too an accident ( what a good accident)!

at least you didn't lose your mind optimizing the wrong solution for C lol

idk, D1A1/A2 are quite simple with one observation, I missed A2 only because of i<=n in place of i<n in my code which gave me undefined behaviour :(

I mean, A might have been a bit tricky (maybe too tricky for an A), but crazy hard is definitely an exaggeration

I'm just the same as you. And I solve 1C in 1h51m, and don't have time to implement 1B. Haha

sum of alternating fib numbers is bounded by the next fib. So if u have multiple things > the biggest fib, then not taking the biggest letter u have means that there will not be enough space to use it.

Insn't it just simulate n fights and collect the wins foreach fighter? What edgecase?

what corner cases?

In Div2C I did simulation of the first $$$n-1$$$ fights while answering queries. I sorted the queries by $$$k$$$.

It is indeed DP. First it's easy to see that one either changes a[i] to i^x or changes a[i] to a[i]^x and a[i+1] to a[i+1]^x. So let's say that dp[i][j] stands for the minimum cost of changing the first i-1 elements to 0, and the i-th element becomes j. You can try to read my submission if you want: https://mirror.codeforces.com/contest/1719/submission/168590571

Always do operation on a subarray of size 2. Go from left to right and maintain all possible values current element can have. If any one of them is zero then pass otherwise one more operation.

I thought that B >>>>> A = C and that having subtasks in A was completely pointless, so your order is very surprising.

I had $$$O(nm \min(n,m))$$$ which passed the tests in 670ms, I think it was the intended or they would increase limits to make ti TLE. However, Um_nik managed to get it in 140ms. Maybe he found a better solution?

Added

#pragma GCC optimize("O3")

And it now passes in 1400ms

1
7 1
1 2 3 6 5 4 7
4 2

Expected : 0 Your output : 2

if i=1,print 0+min(k,j-i-1)

code

Fun fact: you can use bitsets to get a smaller total number of operations.

I believe if you analyze my algorithm carefully, it is $$$O(q C log(log(C)))$$$, still too slow of course (somebody uphacked me), but closer to passing than you might think. I was aware that it could be too slow, but roughly quadratic for $$$10^5$$$ is worth a shot.