I have difficulty logging in.

When I finally logged in, I cannot log out.

I have to publish this blog, as it can easily fall into deadloops. Users who fail to log in cannot seek for help. In turn, I cannot log in until trying about 20-30 times without your help. Do you modify your anti-DDoS or anti-proxy configurations?

Here is my code: 194975604. I think my solution is $$$O(s_n logn)$$$ but it gets TLE on pretest 5.

When I slept soundly last night, a dream took me back to the times when I was taking my college entrance contest. I was given this problem:

Let $$$n$$$ be a positive integer and $$$S$$$ be a multiset consisting of numbers from $$$\{1, 2, ..., n\}$$$. Integer $$$i\,(1 \leq i \leq n)$$$ appears $$$a_i \geq 0$$$ times in $$$S$$$. Also, I was given a positive integer $$$k$$$. A partition of $$$S$$$ into multisets, namely $$$\cup_{i=1}^t S_i$$$, is valid iff all of the following three conditions hold:

(1) $$$\cup_{i=1}^t S_i = S$$$.

(2) $$$\forall 1 \leq i \leq t$$$, the size of $$$S_i$$$ is less or equal than $$$k$$$, i.e., $$$|S_i| \leq k$$$.

Find the minimum possible number of distinct multisets in the partition of $$$S$$$.

For example, if $$$k=2$$$ and $$$S=\{1, 1, 1, 2, 2, 2\}$$$, the answer is $$$1$$$ because you can decompose $$$S$$$ into $$$3 \times \{1, 2\}$$$, so you should answer $$$1$$$ because the problem asks for the distinct multisets.

When I wake up, I find this problem looks easy but I cannot solve it even if $$$k=2$$$. Is this problem greedy or related to the maximum flow? How about $$$k>2$$$?

Given an $$$1$$$-indexed integer array $$$a=[a_1,\,a_2,\,a_3,...,\,a_n]$$$ and a fixed windows size $$$k$$$，define sliding window $$$I_{j,\,(j \geq k)} := [a_{j-k+1}, a_{j-k+2}, ..., a_j]$$$. For each $$$j \geq k$$$, we need to answer a query:

How many sliding windows in $$$\{I_k, I_{k+1}, ..., I_{j-1}\}$$$ are less or equal than $$$I_j$$$ in the alphabetical order?

For example, $$$a=[1, 2, 1, 3]$$$ and $$$k=2$$$:

(1) For $$$j=2$$$, we should answer $$$0$$$.

(2) For $$$j=3$$$, we should answer $$$1$$$ as $$$[1,2] < [2,1]$$$ in alphabetical order.

(3) For $$$j=4$$$, we should answer $$$1$$$ as $$$[1,2] < [1,3]$$$ in alphabetical order.

Suffix array + LCP array can solve it in $$$O(nlogn)$$$ offline. But how about solving online? For example, what if $$$a$$$ is an unbounded datastream instead of an array? In the datastream case, you have to process $$$a_j$$$ and $$$I_j$$$ before reading $$$a_{j+1}$$$.

Will the contest time be shifted to 02:35 UTC+8 from next month?

That is possibly not a friendly time for Asians. Is that a permanent shift?

MikeMirzayanov

Problem: Rectangle Shrinking

Part 1: Notations

$$$x$$$: A brick. $$$x_i$$$ denotes the part of $$$x$$$ belonging to the $$$i$$$-th floor. For example, if $$$x.u=1,\,x.d=2$$$, then $$$x_1.u=x_1.d=1$$$, $$$x_2.u=x_2.d=2$$$, and $$$x_1.l=x_2.l=x.l$$$, $$$x_1.r=x_2.r=x.r$$$.

$$$A_i,\,i=1,2$$$: The set of bricks whose $$$u=d=i$$$.

$$$B$$$: The set of bricks whose $$$u=1,\,d=2$$$.

$$$\texttt{Remove}$$$: Remove a brick $$$x$$$.

$$$\texttt{Shrink}$$$: Shrink a brick $$$x$$$ to another non-empty brick.

$$$\texttt{Keep}$$$: Keep a brick $$$x$$$ unchanged.

Note that in our solution we may operate on a part of brick. For example, for a brick $$$x \in B$$$, we may $$$\texttt{Keep}\,x_1$$$ while $$$\texttt{Remove}\,x_2$$$.

Part 2: Idea

$$$\texttt{Shrink}$$$ing $$$x \in B$$$ is troublesome. If you shrink $$$x_1$$$, you have to shrink $$$x_2$$$ in the same way, i.e., $$$x_1$$$ has to be aligned with $$$x_2$$$. So is there a solution that only performs $$$\texttt{Remove}$$$ and $$$\texttt{Keep}$$$ on every $$$x \in B$$$? But that is impossible, because the bricks $$$x, y \in B$$$ may overlap themselves even with considering $$$A$$$. So what if $$$B$$$ are pairwise non-overlapping (because we could perform some pre-$$$\texttt{Shrink}$$$ and pre-$$$\texttt{Remove}$$$ to make $$$B$$$ pairwise non-overlapping)? [Pre-computation]

In that case, we can consider each floor independently. Let

$$$C_i := A_i \cup \{x_i \mid x \in B \}$$$.

For example, if

$$$A_1 = \{[u=1, d=1, l=2, r=5], [u=1, d=1, l=7, r=10]\}$$$,

$$$B=\{[u=1, d=2, l=2, r=2], [u=1, d=2, l=4, r=7]\}$$$, then

$$$C_1 = \{[u=1, d=1, l=2, r=2], [u=1, d=1, l=2, r=5], [u=1, d=1, l=4, r=7], [u=1, d=1, l=7, r=10]\}$$$.

We sort $$$C_i$$$ w.r.t $$$l$$$, and traverse $$$C_i$$$ like $$$\texttt{for(auto x: C_i)}$$$.

Case 1 ($$$\texttt{Keep}$$$): If $$$x$$$ is not overlapping now, then we add $$$x$$$ to the answer, no matter if $$$x$$$ is from $$$A_i$$$ or not.

Case 2 ($$$\texttt{Remove}$$$): If $$$x$$$ is fully contained in the union of other rectangles, then we always remove $$$x$$$, no matter if $$$x$$$ is from $$$A_i$$$ or not.

$$$\texttt{Keep}$$$ and $$$\texttt{Remove}$$$ are relatively easier, no matter $$$x \in A_i$$$ or $$$x \in \{x_i \mid x \in B \}$$$.

Case 3 ($$$\texttt{Shrink}$$$): If $$$x$$$ is partially overlapping with other bricks.

Case 3.1: If $$$x \in A_i$$$: $$$\texttt{Shrink} x$$$. Move the $$$x.l$$$ to the right to avoid overlapping.

Case 3.2: If $$$x \in \{x_i \mid x \in B \}$$$: $$$\texttt{Shrink}$$$ all bricks that overlap with $$$x$$$ by moving their right endpoints (i.e., *.r), to the left.

It is guaranteed in Case 3.2 that every brick overlapping with $$$x$$$ is from $$$A_i$$$ because we have already performed pre-calculations in $$$B$$$ to make them non-overlapping. The complexity is not an issue, by amortized analysis, each $$$x \in A_i$$$ will do $$$\texttt{Remove}$$$ at most once and $$$\texttt{Remove}+\texttt{Shrink}$$$ at most twice (keep/move left endpoint+keep/move right endpoint).

Part 3: Implementation

First I copy a range-set implementation from nok0. Basically, it maintains a set of intervals using $$$\texttt{std::set}$$$. When inserting/erasing a range, it can merge/split/erase intervals automatically, using binary search (Yes, stop learning useless algorithms, go to learn binary search!). It has many APIs, here are some useful APIs in our implementation:

(1) $$$\texttt{Insert(l, r)}$$$: Insert an interval $$$[l, r]$$$.

(2) $$$\texttt{covered_by(l, r)}$$$: Return an interval covering $$$[l, r]$$$, if not exists, returning $$$(-\infty, \infty)$$$.

(3) $$$\texttt{covered(l, r)}$$$: Return a bool variable indication whether interval $$$[l, r]$$$ is fully covered.

(4) $$$\texttt{right(x)}$$$: Return $$$\min \{y|y \geq x, y \text{ is not covered}\}$$$. Note that API could calculate the $$$\texttt{mex}$$$, so it is also useful for calculating the Sprague-Grundy (SG) number. SG number is irrelevant to our topic.

(5) $$$\texttt{left(x)}$$$ (added by me): Return $$$\max \{y|y \leq x, y \text{ is not covered}\}$$$.

There are also APIs that we don't use in this implementation, but they are also beneficial:

(6) $$$\texttt{Erase(l, r)}$$$: Erase $$$[l, r]$$$. That may lead to interval splitting, for example, if we erase $$$[2, 3]$$$ from $$$[1, 4]$$$, we get two intervals remaining: $$$[1, 1]$$$ and $$$[4, 4]$$$.

(7) $$$\texttt{size}$$$: Get the size of intervals.

(8) $$$\texttt{dump}$$$: Output all intervals for debugging.

So, we implement the pre-computation step (first paragraph in Part2) as follows:

sort B w.r.t l (left endpoint).
Initial a range set named rs.
for(auto& x: B){
    int rightl = rs.right(x.l), leftr = rs.left(x.r);
    if(right <= rightr){
        rs.insert(rightl, leftr);
        for(int i = 1; i <= 2; ++i)  {
             Ci = Ai; Ci.push_back({x.u, x.rightl, x.d, x.leftr, x.id}); //push into Ci
        }
    }else{
        //Case 2, fully contained, remove it!
        //We actually do nothing here
    }
}  

Then, how to calculate $$$C_i$$$ from each floor independently? We need another set that is sorted by $$$r$$$ in the ascending order, let's call it $$$\texttt{sortbyr}$$$, to maintain rectangles in $$$A_i \subseteq C_i$$$. If Case 3.2 happens, we need to find such $$$y \in \texttt{sortbyr}$$$ quickly by $$$\texttt{sortbyr.lower_bound(x.l)}$$$, i.e., find an interval $$$y \in A_i$$$ quickly, using binary search, such that the right endpoint of $$$y$$$ ($$$y.r$$$) is greater or equal than $$$x.l$$$. Note that when we find such an $$$y$$$, you need to iterate to the end of $$$\texttt{sortbyr}$$$, that's why my previous submissions WA at test15--I only handle one of them. Here is the sketch of the implementation:

for(int i = 1; i <= 2; ++i){
    Initialize sortbyr; //Remember to initialize because we handle each floor independently!
    sort(Ci.begin(), Ci.end());
    Initial a range set named rs.
    for(auto x: Ci){
         bool lcovered = rs.covered(l), rcovered = rs.covered(r);
         if(!lcovered && !rcovered){
             //Case 1, Keep
             if(u == d){
                sortbyr.insert({x.u, x.l, x.d, x.r, x.id});
             }
             ans[x.id].insert(node{j+1, x.l, j+1, x.r, x.id}); //No matter u == d or u != d, we only consider one floor here!
             rs.insert(x.l, x.r);
         }else if(lcovered && !recovered){
             if(u == d){
                 //Case 3.1
                 int rightl = rs.right(l);
                 ans[x.id].insert(x.u, x.rightl, x.d, x.r, x.id);
                 rs.insert(rightl, x.r);
                 sortbyr.insert(x.u, x.rightl, x.d, x.r, x.id});
             }else{
                 //Case 3.2
                 auto y = sortbyr.lower_bound({-1, -1, -1, x.l, -1});
                 while(y != sortbyr.end()){
                     //Here, we should deal with all overlaps! That's why my previous submissions WA on test15
                     auto [u2, l2, d2, r2, id2] = *y;
                     //Here l2 <= l because we sort Ci by l. So sortbyr only contains elements whose left endpoint <= l!
                     //By lower_bound, we have r2 >= x.l
                     ans[id2].erase({u2, l2, d2, r2, id2}); //We erase it from our answer
                     sortbyr.erase(y++);
                     ans[x.id].insert({j+1, x.l, j+1, x.r, x.id}); //We never shrink the splitted ones
                     rs.insert(x.l, x.r); //Although [l, r] overlaps with [l2, r2], range set will merge them automatically!
                     if(l2 <= l-1){ //Be careful! r2 may <= r, so y after shrinking may be empty!! 
                         ans[id2].insert({u2, l2, d2, x.l-1, id2});
                         sortbyr.insert({u2, l2, d2, x.l-1, id2});
                     }
                 }
             }//Case 3.2
         }//Case 3
    }//for
}

In the above implementation, it is not possible that $$$\texttt{!lcovered && rcovered}$$$, otherwise $$$[l, r]$$$ is covered by some $$$[l_1, r_1]$$$ which $$$l_1 > l$$$. But we have already sorted $$$C_i$$$ by $$$l$$$. And, if $$$l$$$ and $$$r$$$ are both covered, we just ignore and $$$\texttt{Remove}$$$ this segment.

Finally, we need to output the answer, for this part please refer to the code. Note that due to the implementation, we may insert two parts of bricks for $$$b \in B$$$. I mean, for $$$x = \{1, l, 2, r, id\} \in B$$$, the implementation might insert both $$$\{1, l, 1, r, id\}$$$ and $$$\{2, l, 2, r, id\}$$$ into $$$ans[id]$$$, so we need to merge them manually, that is dirty work.

Here is an advertisement for CFStress: Although my previous submission WA on case5 of test15, CFStress could still find a very small counterexample in a very short time! As mentioned here, My debugging ability is really poor, so I don't use CFStress very frequently, as I often debug myself to improve my debugging ability. However, CFStress has saved me many times from insomnia. Thanks, variety-jones!

Which data structure supports the following four types of queries？

Given an undirected graph $$$G=(V, E)$$$, there are four types of queries, and these queries may be asked in an arbitrary order:

(1) Add an edge $$$e$$$ to $$$E$$$. It is guaranteed that $$$e \notin E$$$ before this query.

(2) Delete an edge $$$e \in E$$$. It is guaranteed that $$$e \in E$$$ before this query.

(3) Query the number of connected components in $$$G$$$.

(4) Check whether vertices $$$u$$$ and $$$v$$$ are in the same connected component.

I strongly rely on my "intuition". If my intuition is correct I can solve the problem very fast. Otherwise, I will fall into some solutions that seem right (but actually wrong). The worst thing is debugging takes too much time and upset me (affects other problems). It seems that I am the kind of guy that has strong "thinking inertia". Do you face a similar issue? How to improve? Would you please help me?

Take https://codeforces.net/contest/1779/submission/187786889 as an example. Is it just because I am stupid?