u shold pay attention in learn learn rather than code code

I hate you all

Someone Plz explain, does it mean that Southern and Volga Regional contestants will be in Top of Standings (As they have Seen and Know all of the problems) ? How are problem setters sure that there is no Editorial of the problems in Internet already ?

These 2 things are pretty enough to Ruin the competition for everyone.

The participants of Volga Russian Regional Contest are said to avoid the contest.

nice

All solutions are going to be retested with test data from successful hacks. So a successful hack influences the final standings by kicking off some solutions.

best of luck

I'm able to see a difference.

Why there is no impact in the standings even after unchecking the show unofficial box?? Is this with me only or with you also??

It's written in the problem statement that you can't move the lid more than once

if it was possible to move more than once, the task turns into output the sum of the top k elements, this should have alerted you

It would have been nice If they mentioned in bold For C, no lid can be moved more than once.

First, identify the leftmost 1. The suffix from here has the longest bit length (excluding leading 0s) you can get, so this suffix should be your first substring (impossible to reach this bit length with any shorter substring).

Now, identify the first non-leading 0. Making this 0 into a 1 will always be better than any alternative where this 0 remains as a 0. But to make this into a 1, we need the second substring to start sometime before this 0 (otherwise, it would be too short to reach this 0). Therefore, the second substring must begin sometime between the first 1 and the first non-leading 0, and its length should be exactly enough that the first 1 in the second substring covers the first 0 of the first substring.

We can try every possible choice for the second substring, and pick the one with the largest result. The worst-case runtime is $$$O(n^2)$$$, BUT the problem states that the strings are generated randomly, so the expected number of 1s before the first non-leading 0 is in $$$O(1)$$$, so we're not likely to get a huge number of 1s before the first non-leading 0, leading to $$$O(n)$$$ expected runtime overall.

Video Solution for Problem D and Problem C.

Brute force solution works because of the given probability condition.

I used a lazy propagation in segment tree

Sorry I thought you are saying F as it mentioned about segment tree with lazy propagation. For F, You could do it with some observations, by considering the operations done on last set to the first set.

Dynamic programming of the form $$$dp_x$$$ — the minimum amount of time required to deal exactly $$$x$$$ damage to the enemy so that the last shot was a double one (i. e. both lasers have just fired).

I did. And this mistake will cost me a massive loss of rating points.

i guess the problem is u have solved very less problems of higher rating (>=1200).

just keep trying, somedays you will be pupil, maybe expert, cm, master,.. just keep trying.

Don't take it serious man. Just practice as much as you can and try to solve harder problems. Like if you want to reach pupil, solve problems with difficulty from 1300-1600. I have been newbie for 11 months but never left hope. Be courageous. Select some handles and while the contest, try to beat them. You will improve :) .

Best of luck,

Daniyal.

One of subarrays is of course all array without leading zeroes. So check as second subarray only subarrays that have length of n — first 0 index after first 1. This don't give tle because that length can't be < n — 60 (chance is too small).

1) One of strings (s1) should be longest started with 1. It is unique and starting with the first 1 in the string

2) You want to cover zeroes in s1 from left to right with 1 in s2. It doesn't make sense to have leading zeros in s2. So we even know its length — it should start with 1 and this 1 should cover the first 0 in s1. Random guarantees a rapid decrease in the number of best candidates when processing more and more zeros. If some of them can cover another 0 — we leave only these as candidates and move on

Solution for F:

First,use sweep line.Enumerate $$$x=0,1,...,3*10^5$$$,and record current segment set containing $$$x$$$.

Now let's calculate the number of operation schemes so that after operations,the segment set contain $$$x$$$.

($$$i.e.$$$ contribution of $$$x$$$)

Define clear operation $$$op_i S_{i+1}$$$ as:

• $$$op_i==∪$$$ and $$$S_{i+1}$$$ contain $$$x$$$,or

• $$$op_i==∩$$$ and $$$S_{i+1}$$$ not contain $$$x$$$.

Consider the last clear operation $$$op_i$$$,

for $$$op_1,...,op_{i-1}$$$,which do not affect the results,there're $$$3^{i-1}$$$ schemes.

for $$$op_{i+1},...,op_{n-1}$$$(contain $$$k=(n-1)-(i+1)+1$$$ number of operations),

• if there is $$$S_j(i+2 \leq j \leq n)$$$ which contains $$$x$$$,there're valid $$$2^{k-1}$$$ schemes in total.

• if there is not $$$S_j(i+2 \leq j \leq n)$$$ which contains $$$x$$$,there're valid $$$2^k$$$ schemes in total.

The total number is $$$3^{i-1}*2^{k-1}$$$ or $$$3^{i-1}*2^k$$$.

Enumerating the last clear operation $$$op_i$$$ costs $$$O(n^2)$$$.But we can optimize it using prefix sum trick,which costs $$$O(n)$$$.

There are two subproblems to solve here.

First, for each coordinate x determine which segments it belongs to. This is classic sweepline: loop over x, at x=l[i] turn on S[i], and x=r[i]+1 turn off S[i], then process x. Sort l[i], r[i]'s together with bits of information what to do as you encounter them, and iterate over this sorted list together with x.

The second problem then is: given a fixed coordinate x and bitmask S from previous step (indicating which segments contain x), calculate number of ways to put binary operators between S[0], S[1], ... S[n-1] so that the whole expression evaluates to 1. The final answer is the sum of this count for all x.

One obvious way to calculate that is with dp, maintain dp[pos][result] = number of ways to get 'result' after choosing operators and evaluating the expression up to S[pos]. It's a bit too slow due to constraints on n, but observe that dp[pos] (as a vector of 2 elements) depends only linearly on dp[pos-1] and S[pos], so you can actually express it as a matrix multiplication: dp[pos] = dp[pos-1] * <some matrix>, where there's one matrix M0 for S[i]=0 and another M1 for S[i]=1. You can calculate these transition matrices by hand or with a bit of code. The whole dp then is a product of matrices: initial state [0,1] or [1,0] depending on S[0], multiplied by M[S[1]] * ... * M[S[n-1]]. You can use segment tree to efficiently evaluate it and support updating matrixes in the middle of it, as S[i]'s are turned on and off during your sweepline.

Actually, you probably don't even need matrices as this comment suggests, just focus on dp[pos][1] counts I guess. But it's a neat trick in general to know that if your dp transitions are linear, then you can speed it up by thinking of it as a matrix multiplication. For example, closed form derivation for fibonacci numbers starts from such matrix multiplication reformulation.

Actually the version where you can move the lid multiple number of times is at least more classic than the current version (I also think it is easier but that's subjective)

In that other version you just insert elements from left to right in a priority queue and for each $$$1$$$ you extract the current maximum and add it.

However in the current version, you need to look for every substring of the form $$$011 \ldots 110$$$ and then take everything except the last element and the minimum of the other ones.

Agree ._.

It's important to always have some problems that are very easy to solve. It's not a div1 contest with limitations on user's lowest rating, everyone should be able to solve at least 1 problem. And also, for me, C was easier than A or B and took less time because I'm an idiot and tried using combinatorics in A instead of bruteforce ^D

A is supposed to be easy, even in Div2. If it's not too easy, many participants might quit if they don't solve it quickly, which can really skew over the ratings of those who participated, as well as the problem ratings. Please do not encourage problemsetters to make Div2A too hard.

I do agree that B is a bit easy for its position though.

debugmode() is working

Hint : How to compute answer if string is 011111110?

Yeah, I was quite smiling when I read FTL :)

Use spoilers for code.
Your comment is literally taking up 30% of the blog's scroll-space.

For Problem D, your mistake was in considering the left shift. A left shift does not form a valid substring. For example, consider the following test-case:

10
1000011111

The answer should simply be 1100011111, where the second substring is the prefix without the last character (so it's equivalent to a right shift). But your code answers 1111111111, because it assumes the 1s on the right can be left-shifted to cover the 0s on the left, but there's no way to actually pick a valid substring that would cover all the 0s.

Wrong answer on test 1 = no penalty (the rules. the same for every problem)

WA on TC1 has no additional penalty on any contest.

Educational rounds follow extended ICPC rules. Here you won't get a penalty for WA on test 1. You can read about it here: https://codeforces.com/blog/entry/105575?#comment-939387

Each password is of the form XXYY. The number of ways to generate permutations of this is: 4! / (2! * 2!) = 6. Now, there are 10 numbers in your hand [0 — 9] and some are excluded. So the remaining numbers left are 10 — n. Let's call that size K. You need to pick 2 numbers from these remaining K numbers. The number of ways to do that is KC2 = K*(K-1)/2.

Therefore, your answer will be KC2 * 6 [Choosing 2 numbers from the available set, and generating permutations of them]

All the non-example tests are generated randomly,so it is nearly impossible to let your code get wrong answer in 40 test cases.

Could you please explain why checking only first 100 shifts work? Is it because getting the first 100 characters as 0's is not probable so we always get the best answer in the first 100 shifts?

You are only half right. Notice in your third condition, you explore a a different option.

Take example the string 0111. Your code considers, 011, 101, and you notice that 110, is also possible (swapping the first and third element). However, take a look at this string: 0111111. Your code will only consider, 1011111 and 1101111. However, these are also possible: 1110111, 1111011, 1111101, and 1111110. Basically, when you have one zero followed by n 1s, you can swap any of the 1s with the 0. But you only consider the first 2 1s.

It could be done by greedy tho. Just by considering continuous segments of 1's. But dp solution shouldn't be really complicated in this case.

The problem has a greedy solution too. It seems that dp solutions are getting hacked now (Or Only Memoization one) ;)

I did C purely through greedy

or FFT :D

Can you please elaborate a bit

The solution highly relies on randomness.

Well, your logic needs extra 0 at the end of s.

Do look into this and conduct a plag test, as there are hundreds of submissions with the exact same code, just with the variables changed. Removing 100s of such users from the leaderboard will be very good, especially for those with ranks>5000. Kindly look into this MikeMirzayanov

I want to cry. I would have never thought to extract that conclusion out of that detail. Everything bold is bold for a reason.

Try eliminating all ones that are not last in the sequence of ones after zeros. Then you shall see how to solve this in O(n). For example

10001111110110 = 10001010 (lits) 12221234342322 = 12224222 (mags)

https://www.statisticshowto.com/multinomial-coefficient/

There are 10 numbers b/w 0-9, you are given n numbers, remaining 10-n numbers you have to pair.
So, (10-n)*(10-n-1)/2 are the number of pairs. Then, multiply by 6 because 6 permutations.
The above is just the simplified version of this

Basically, it's just the same as kC2*6, 6 is the number of permutations when all the conditions are satisfied according to the question. Where k is (10-n), so, k*(k-1) is eventually (10-n)*(9-n) which explains the statement.

Same as my submission

Apologies Huehuehue277353

Hacks are unrated in edu rounds

10110 1011 11111

We are doing the OR of the binary substrings so we start from right to left

thats what she said

i feel like using bitsets can pass the $$$O(n^2/w)$$$ (cuz TL is 4 secs). But u'll need to implement ur own comparison that is also avx fast.

Actually solution that uses randomness is also expected O(n), because expectation value of number of process is constant complexity.