It doesn't allow to show the solutions

So sad I cannot access to the submissions !

I guess most participants would consider the bitset solution to D cheese, but I'd like to point out another way to optimize it.

Naturally, the bitset solution would be like:

• sort the arrays by $$$w$$$;
• compress the numbers, for each number store the bitset of the arrays it appears in;
• iterate over the first array, OR the bitsets of the numbers in it, then take _Find_first() of its complement.

The only issue is that you can't store all bitsets, it takes $$$O(n^2m)$$$ memory. The authors overcome this by solving the problem separately for numbers that appear less than $$$T$$$ times and more by choosing $$$T$$$ carefully.

But there is a common problem, where we encounter the same issue. (As memed as it is) It's called "count the number of pairs of reachable vertices in DAG" or something along these lines. How do we deal with it there? Well, we process vertices in batches of $$$64$$$.

Let's do the same. Process arrays in batches of $$$64$$$. Consider the first batch of arrays from $$$1$$$ to $$$64$$$. For each number, build a bitset of size $$$64$$$ (also known as an unsigned long long) with arrays from the batch it appears in. This is done in $$$64m$$$ operations. Then iterate over all arrays and do the same OR thing as in the initial solution (find first becomes __builtin_ctzll). With this, we only consider pairing each array with some array from the batch. We have to process $$$\frac{n}{64}$$$ batches, and it takes $$$O(nm)$$$ to process each one. So we get the solution with the same complexity but with just $$$O(nm)$$$ memory.

Code: 147454534

I think it's worth mentioning that 1641C - Anonymity Is Important can be solved with a DSU, which quite a few people did. The way I thought of it is that we consider the prefix sum array of the number of ill people (so for example, a segment of healthy people corresponds to a segment in this array where the value is constant). The DSU stores collections of indices which are known to have the same value (these components are always segments) as well as a pointer to the next position that is known to be in a different component. The time complexity is $$$O((n+q)\alpha^{-1}(n))$$$ which is better than the editorial. (Maybe it could be improved to $$$O(n+q)$$$ if we account for the simple structure of the components?)

Can someone help me find error/mistake in my submission for A ? Thanks ! Code

For problem div 2E, there's this statement

find the next one and do the same thing until we find the first index greater than r

I don't quite get it. If l r 0 is given, why do we need to remove the first index greater than $$$r$$$ ? Shouldn't it be "remove the last index with the value at most $$$r$$$"? Cmiiw

Please help me in understanding the editorial of problem div2E (1641C - Anonymity Is Important). Or share some alternate approach that is easy to understand.

I am totally confused about why my submission at problem C got WA at 42nd testcase in case 2

I get '18' while the Jury gets '17'

May I know how so many people got TLE'd on 1642C - Great Sequence, especially on the systests? I am suspecting that people went for adding numbers instead of erasing and that added to the runtime, but I am not quite sure.

Cnacu6o for weak pretests of D( ya nje ljubju FST

Figured out the solution of 1642D - Repetitions Decoding during the contest but can't put it into code in time... so sad

Why I got MLE at Problem C at the 10th testcase? I used map to count the numbers, the total memory complexity may be O(n). 147431101

I thought of the same thing in prob D but failed to come to the point that by doing this we can sort it

I got a different solution for Div. 1C just after contest ended. (https://mirror.codeforces.com/contest/1641/submission/147504174) Let's call each query's index as its timestamp. Basic idea is to find out the earliest timestamp the status of each index becomes determined. First, process all t = 0 && x = 0 queries. Record the first time each index becomes 0. Maintain a segment tree with point update min. Second, process all t = 0 && x = 1 queries. We know that for a query with l and r, if and only if there are r-l 0 indices inside it, the left one is determined to be 1. So query the previous segment tree for range sum could find out this. Notice also need to find out the largest timestamp of all 0 indices. The maximum of 0 indices and this 1 query is the timestamp of this 1 index. Notice that, there might be more than 1 queries making this index determined, and we need to pick the minimum one. Last, process all t = 1 queries. if the index has determined status, and the timestamp is earlier than the query, then result is YES or NO, otherwise N/A.

For Problem A, if I try using long double, I get a wrong answer, but if I use long long, then I get correct answer. Why does this happen? My logic is the same as the editorial.

Using long long.

Using long double.

d1D can be solved in $$$O(\frac{n^2m}{\omega})$$$ using bitset.

d1E can be solved in $$$O(n^2)$$$ using Ofast.

Great contest!

I am a idiot. I forgot to printf the answer in problem E so that I can't solve it.

Div2C seems to have weak tests guys. The following submission should TLE.

https://mirror.codeforces.com/contest/1642/submission/147435078

But its AC. I used a multiset with count, which is slow (linear time complexity). Sample input used

1
200000
1 (100000 times) 2 (100000 times)

Can someone please help me understand why I am getting TLE for these submissions in Div2-B. I have used unordered_map and unordered_set. (147532491 and 147456652).

Can anyone explain me why unordered_set or unordered_map gets TL for the problem B but set/map doesn't get TL? submission 1 : 147535731 submission 2 : 147535959

ilyakrasnovv correct me if I am wrong, but this line in explanation of Div1C -

we can find the first elements to the left (l) and to the right (r) of i, which might be healthy using our set. The i-th person is ill when the minimal element on segment [l+1;i] is <r.

should be

we can find the first elements to the left (l) and to the right (r) of i, which might be ill using our set. The i-th person is ill when the minimal element on segment [l+1;i] is <r.

I'm a freshman ,i used multiset in 1642C,but i got TLE , can it be solved used by multiset only? can somebody help me , thanks a lot! It's my submission 147572794

I think i've found a nice randomized solution to D1D.

First compress all the values. Now generate a random permutation and replace the corresponding values with it. Now lets check all the pairs such that the minimum value in one array is bigger than the maximum value in the other. This works with probability of $$$1 / C_{2m}^m$$$, which is $$$1 / 252$$$ for $$$m = 5$$$. So now all we have left to do is process this in linear time ($$$O(nm)$$$) and fit into TL:) I would consider the total time complexity to be $$$O(n\cdot m\cdot C_{2m}^m\cdot log(error)) \approx O(n\cdot m\cdot 2^{2m}/\sqrt{2m} \cdot log(error))$$$.

Solution: 147616242

Correct me if I am wrong, but this line in explanation of Div2E/Div1C:

should be:

“when the minimal element on segment [l+1;i] is <r.” In problem C of div1 ,I failed to solve this problem only because I simply thought that ：exist a segment on [l+1;i] ,[i,r-1]; What a pity

In Div 2, C 1642C - Great Sequence why does the editorial solution have an if statement for when x is 1, if it is specified in the problem statement that x is at least 2?

in div2 problem C, I got it wrong at first then it felt right to sort the array and got it AC. the thing I myself am not fully convinced why sorting was necessary. can someone explain or some proof of thought(not any formal proof, just the idea of correct thinking).

Problem 1642E — Anonymity Is Important. I didn't understand the last (segment tree part) part of the editorial. How can we find a person is definitely ill using seg tree? Can someone explain? Thanks in advance.

Can somebody explain why in div.2 E the observation that "$$$i$$$ is ill when minimal value in our segment tree on interval $$$[l + 1; i]$$$ is smaller than $$$r$$$" is working?

div2 F's solution is so cool!

I'm trying to solve div-1 C with O(n*(log n)^2), is there any way to optimise it a bit so that it wont tle?

https://mirror.codeforces.com/contest/1641/submission/192119258