awoo's blog

By awoo, history, 2 years ago, translation, In English

1721A - Image

Idea: BledDest

Tutorial
Solution (BledDest)

1721B - Deadly Laser

Idea: BledDest

Tutorial
Solution (awoo)

1721C - Min-Max Array Transformation

Idea: BledDest

Tutorial
Solution (adedalic)

1721D - Maximum AND

Idea: BledDest

Tutorial
Solution (Neon)

1721E - Prefix Function Queries

Idea: BledDest

Tutorial
Solution (awoo)

1721F - Matching Reduction

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +41
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Definitely not intended, but simply storing the answers for all queries you processed worked for E too
(Feel free to hack it)
Submission

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This same solution gives MLE for me though

»
2 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Brute force can AC problem E because of the too small $$$|t|$$$. AC Submission.

That's too bad. I think problem E is really a bad problem.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How should they avoid that? Does $$$| t| \le 15$$$ for example help? Since then your hash wouldn't work, right? I'm not very familiar with hashes so I'm curious.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      Hack the hash is one of the way to hack this solution. When $$$|t|$$$ is small, the hash can't be hacked.

      Another way is let $$$s=$$$aa...aa, and then generate some different string $$$t$$$ with prefix aa...aa. If $$$|t|$$$ is large enough, this solution will get TLE.

      Sorry for my bad English :(

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My generator code is like below:

        Code (C++)
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I think $$$|t| \le 100$$$ is large enough.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        If $$$s = $$$ aaa...aaa, then this is $$$O(26 \cdot |t| \cdot |s|)$$$, where $$$26 \cdot |t|$$$ are the times you have to compute the prefix function and $$$|s|$$$ is from the bad case of that $$$s$$$, right?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I do exactly the same but used trie instead of hash.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      You can also sort the queries and start from the LCP.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        How to show that this is fast enough? I know that this order does minimize the total number of operations that the KMP algorithms will make.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please explain what does tilde "~" mean in C++

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's a negation. Google "negation in bitwise operator"

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am i the only guy who tried to solve D using Divide and Conquer approach with lengthy code.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My Divide and Conquer solution does not work since it has a flaw. Anyone who has the right implementation for D using Divide and Conquer

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      I tried writing it with a strange msb binary radix sort. I failed during the contest, but the approach should work in O(log max * n). Basically what you do is:
      Sort both subarrays according to ith msb.(in O(n) with a quicksort-like method)
      Reverse the second subarray.
      If the ith msb is in the solution split the array where the ith bit changes (this means each subarray looks like this if you watch only the ith msb:
      Subarray of a: 0..01..1
      Subarray of b: 1..10..0)
      Now you can repeat the sort, check, maybe split until last bit.

      This is really bad for a contest, but maybe it can be nice to implement (didn't manage to debug it yet)

      edit : it works 170011092

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is problem D solution using trie

169864432

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Seeing who came up with the ideas, I came up with this conclusion about this round.

Spoiler
»
2 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Can anyone please explain the (Ai & mask) ^ (Bi & mask) = mask in problem D ?

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    You want to pair $$$A_i$$$ with a $$$B_i$$$ such that $$$(A_i ⊕ B_i)$$$ & $$$mask = mask$$$, and the left side is equal to $$$(A_i$$$ & $$$mask) ⊕ (B_i$$$ & $$$mask)$$$ (distributivity, similar to $$$(a+b).c = a.c + b.c$$$)

»
2 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

My approach to Problem D.

Let’s call an optimal pair the pair ($$$a_i$$$, $$$b_i$$$) after reordering $$$b$$$ to get the answer.

Initially the answer is $$$0$$$. At first we will try to make the highest bit in the answer into $$$1$$$ (I think this doesn’t need a proof). If we want the $$$i-th$$$ bit in the answer to be $$$1$$$, we need for every element of $$$c$$$ the $$$i-th$$$ bit to be $$$1$$$ and for this in every optimal pair we need $$$(a_i$$$ $$$\And$$$ $$$(1$$$ $$$\ll$$$ $$$i))$$$ $$$\oplus$$$ $$$(b_i$$$ $$$\And$$$ $$$(1$$$ $$$\ll$$$ $$$i))$$$ $$$= (1 \ll i)$$$. In other words, $$$($$$the $$$i-th$$$ bit of $$$a_i)$$$ $$$\oplus$$$ $$$($$$the $$$i-th$$$ bit of $$$b_i)$$$ $$$= 1$$$.

We’ll keep a vector $$$va$$$ of pairs of vectors. In each pair of $$$va$$$ there are elements of $$$a$$$ in the first and the elements of $$$b$$$ in the second element, such that the second elements of the optimal pairs, in which first elements are the elements of the first vector, will be the elements of the second vector (i.e. the elements of first and second vectors will construct an optimal pairs). Initially $$$va$$$ will contain only ($$$a$$$, $$$b$$$).

The algorithm is following : for every bit from $$$29-th$$$ to $$$0-th$$$ (let’s say $$$i-th$$$), we will do this: go threw the $$$va$$$, and for every pair of vectors, divide the first into $$$a0$$$ and $$$a1$$$, and the second into $$$b0$$$ and $$$b1$$$. In $$$a0$$$ there are all elements of the first vector, the $$$i-th$$$ bit of which is $$$0$$$, and in $$$a1$$$, the elements, the $$$i-th$$$ bit of which is $$$1$$$. $$$b0$$$ and $$$b1$$$ are constructed with the same way. Now there are two cases:

  • If for every pair in $$$va$$$ the size of $$$a0$$$ is equal to the size of $$$b1$$$, and the size of $$$a1$$$ is equal to the size of $$$b0$$$, we will change $$$va$$$ into a new vector, consisting of all ($$$a0$$$, $$$b1$$$) — s and ($$$a1$$$, $$$b0$$$) — s (don't forget to check whether $$$a0$$$ and $$$b1$$$ ($$$a1$$$ and $$$b0$$$) are empty or not). And we’ll make the $$$i-th$$$ bit of the answer $$$1$$$.
  • Otherwise, we will not change $$$va$$$ for the next bit.

Time Complexity is $$$O(30 * n)$$$.

My code

My idea is not very different from the idea in the editorial, but my implementation is another.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    My approach is similar, but it uses partitioning instead of a vector of pairs of vectors.

    Our goal, as before, is to prioritize the highest bits to be $$$1$$$. We can know that it is possible to make a certain bit number $$$j$$$ 1 in our result by checking whether the number of values of $$$a_i$$$ such that the $$$j-th$$$ bit is $$$1$$$ is the same as the number of $$$b_i$$$ such that the $$$j-th$$$ bit is $$$0$$$.

    This allows us to match $$$b_i$$$ with a $$$j-th$$$ bit of $$$0$$$ with $$$a_i$$$ with the $$$j-th$$$ bit of 1 and vice versa. We'll move both such values to the very front of their respective arrays using Hoare's Partition Scheme. For future less significant bits, we can use the same algorithm to rematch values within their partitions to preserve the higher bits we have already used. If we discover that any individual partition for a certain value of $$$j$$$ cannot be matched, we advance to the next value of $$$j$$$.

    Now all we need to do is to keep track of the order of the partitions as we make them, which can be done with a set.

    Code

    Total Complexity: $$$O(N*log(N)+30*N)$$$.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Awesome !! Tsovak I had the same idea but couldn't find the right data structure for it. Your implementation clarified it completely.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tsovak Can you check my implementation once? i am getting TLE although I tried to code the same idea as yours 170072227

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You forgot to check if $$$a0$$$ and $$$b1$$$ are empty or not when adding it to $$$temp$$$. Same with $$$a1$$$ and $$$b0$$$.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can I ask why we have to check whether a0 and b1 are empty or not when adding it to temp. I thought it won't affect the time complexity. Thanks!!!

»
2 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

D can be done with trie as well, however it is much harder to implement.

»
2 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

The partitioning and matching in D can easily be maintained through simple built-in sorting, without requiring any additional maps or data structures.

To check if the most significant bit can be 1 in the answer, we can simply sort $$$a$$$ and reverse-sort $$$b$$$, and then check if this bit position is different between $$$a_i$$$ and $$$b_i$$$ for each index $$$i$$$. If yes, then we set this bit to 1 in the answer, and check the next position. The sorted order already extends naturally to the next bit (values in which the highest bit position are equal will be sorted based on the next highest bit position), so checking this next bit position like this will automatically account for the partitioning of the earlier bit positions.

The only issue is when the check fails for some bit position, i.e., there is some bit position where some $$$a_i$$$ is the same as the corresponding $$$b_i$$$. This means we can't have 1 in this bit position for the answer, and also that we should not allow this bit position to restrict the sorted ordering for later bit positions. To deal with this, we can simply set this bit position to 0 for ALL values in $$$a$$$ and $$$b$$$, and then sort $$$a$$$ and reverse-sort $$$b$$$ again (where the rearrangement will NOT modify the ordering within higher bit positions).

My Submission: 169955540

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my approach for solving D. May someone explain why it does not work?

Start with the MSB. Check if the number of elements with that bit set (1) in A is equal to those in B with that bit not set (0). If they aren't, proceed to the next bit. If they are equal, rearrange A and B such that the elements in A with that bit set precede those with that bit not set. Also rearrange B such that the elements in B with that bit unset precede those with that bit set. This way, that bit would look similar to this in A and B:

A: 1 1 1 1 1 0 0 0
B: 0 0 0 0 0 1 1 1

And hence after XORing the corresponding elements the result is n elements having that bit set. Now that A and B are partitioned into two sections, solve each section separately for the next bit.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It should work, in theory. But how exactly are you maintaining these partitions?

    When you mentioned solving each section separately for the next bit, note that the check needs to succeed for all partitions corresponding to the current level. So we first check the entire A and B together until we find a bit position that works (first successful position), causing each of A and B to be partitioned into 2 sections each. So for the next bit position, we check each section separately. If we eventually find a second successful position where the check succeeds for both sections, then we again rearrange the values (in a manner that does not disturb the values of the bits from the first successful position), and each section is further partitioned into 2 sections each, resulting in 4 sections for each of A and B. For the third successful position, we need the check to succeed for all four sections, and again rearrange in a manner that doesn't disturb the values from the first and second successful positions, and so on. Note that the partitions are only fixed for successful bit positions, and not for unsuccessful bit positions (where the check fails).

    If you're confident that your implementation fulfills these conditions all the way until the end, then it should work.

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Probably, problem E 1721E - Prefix Function Queries can be solved with sorting of all queries in lexicographical order and processing of them strongly in this order. We need to revert changes only to largest common prefix of given query and previous one. My AC submission: 170039416

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And why this solution is fast enough?

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone find out why on earth this code got RE? thks in advance.

Code (C++)

Edit: solved. (found that sort got an infinite loop. :( )

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

(Copy-pasted):

Here's an interesting solution I found for E, not sure if it's new. Implementation here, featuring enough spaghetti to feed a family of five for a week.

We do some precomputation first. Use a map<int, int> m, where values are hashes of a substring of $$$S$$$, and the corresponding value is the maximal number $$$i$$$ such that the length $$$i$$$ prefix and suffix of $$$S$$$ are the same. To calculate this, we iterate $$$i$$$ independently of the substring, and check if the prefix and suffix have the same hashes in $$$O(1)$$$ time. If so, we add update m on substrings $$$S[i+1..i+1+j]$$$ (technically their hash values). As we'll see later, we only care about $$$j \leq 10$$$, so this takes $$$O(|S|\log |S|)$$$ time which is fast enough (we can use an unordered_map or gp_hash_table as well but time is not an issue). Note that if we double-check our hash equality by directly comparing the substrings, we TLE on TC 36 which is all a's, since comparing strings/generating substrings is linear in the length of the string so our program runs in $$$O(|s|^2)$$$ in that case.

We consider every $$$|S|+i$$$ more or less independently (I will use uppercase letters). Let $$$T_i=T[1..i]$$$ denote the length $$$i$$$ prefix of $$$T$$$. Suppose we have some prefix string $$$x$$$ of $$$S+T_i$$$ that's also a suffix string. There are three possibilities:

(1): Both the prefix and suffix strings lie in both $$$S$$$ and $$$T_i$$$. In this case, we can break $$$x$$$ up into $$$x_1,x_2,x_3$$$ (in that order) defined as follows: $$$x_1$$$ is the portion of the suffix string lying in $$$S$$$, $$$x_3$$$ is the portion of the prefix string lying in $$$T_i$$$, and $$$x_2$$$ is the remainder of $$$x$$$. To check if any $$$x$$$ of this type work, we iterate over $$$|x_3|:=j$$$, checking if the length-$$$j$$$ prefix and suffix of $$$T_i$$$ are the same. If so, then $$$x$$$ works if and only if the rightmost occurrence of $$$x_2$$$ in $$$S$$$ is as far right as it can be (i.e. occupies starting position $$$|S|-|x_2|$$$). In this case, the length-$$$|x_1|$$$ suffix of $$$S$$$ is also $$$x_1$$$, so we can use our precomputed m. There are at most $$$10$$$ values for $$$|x_3|$$$, so iterating over them is fast.

(2): The prefix string lies entirely in $$$S$$$, but the suffix string does not lie entirely in $$$T_i$$$. This is more or less a simpler version of (1). We split $$$x$$$ into $$$x_1,x_2$$$ such that $$$x_2$$$ is the portion of the suffix string lying in $$$T_i$$$, and $$$x_1$$$ is the remainder. Since $$$x_2$$$ must be $$$T_i$$$ by definition, $$$T_i$$$ must appear in $$$S$$$ as a substring. Further, $$$x_1$$$ must also be the suffix string of $$$S$$$ when this happens. We can use m for this as well. Note that there's only one possible value for $$$x_2$$$.

(3): The suffix string lies entirely in $$$T_i$$$. If $$$|S|\geq i$$$, then that means the prefix string lies entirely in $$$S$$$. There's at most $$$10$$$ values for $$$x$$$, so we can iterate $$$j$$$ from $$$1$$$ to $$$i$$$ (inclusive) and check if $$$S[1..j]=T_i[i-j+1...i]$$$. Otherwise, we have to join $$$S$$$ and $$$T_i$$$, since the prefix string could partially lie in $$$T_i$$$ as well, but the actual check is the same. Since this case only occurs when $$$|S|\leq 10$$$, joining $$$S$$$ and $$$T_i$$$ is quick (if you join $$$S$$$ and $$$T_i$$$ no matter what, you should TLE). Either way, you iterate through at most $$$10$$$ possible values for $$$x$$$. Ignore the comment at the top lol

To find the final answer, we iterate through all $$$O(1)$$$ cases and update our maximum value each time. The final time complexity should be $$$O((|s|+q)\log |s|)$$$ which works if you're not being stupid.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does F have to be online? I mean, is there any other way to solve it if one can do it offline?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess it is because the author wants to prevent solutions that run bipartite matching on every type $$$2$$$ query.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain why rank2 tute7627's submission works? The idea is using kmp to optimize mp. I see there are several this kind of submissions so I wonder if the time complexity of this approach is correct and we can use it as a model solution.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone uphack my solution to D?

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I want to share my ultra elegant solution for 1721D - Maximum AND. Look: 169910079

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Solution of D, why (&ans) is used instead of (ans^(x&ans))? I know they are apparently the same, but how can this formula come up in mind? If it is something obvious , please tell me the trick. BledDest

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wasn't the one implementing the model solution, but I guess that it was done for the shorter code. In fact, x & ans represents the mask of the number that x should be matched with (which should be done for one of the arrays nevertheless), and for the array $$$b$$$, the value of ~x & ans is exactly the same as ans ^ (x & ans) you were mentioning. So, since exactly one of the arrays was analyzed without flipping the bits, elements that have the same value in their corresponding bit operations should be matched. If you use ans ^ (x & ans) for both arrays, you should match the value v from the first array with the value v ^ ans from the second array.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does my D TLEed on #15? 169888012

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone please have a look at my submission 170673948? The basic idea is that the longest prefix of s+t matching some suffix of s+t will either have length (1) >|t| or (2) <=|t| . For the >|t| part, some (proper)suffix of s will match some suffix of s i.e the z value(wrt the z algorithm) of the index i from which the suffix starts will be n-i (0-indexing assumed). For the <=|t| part we can just brute force to obtain the answer in O(|t|^2) (to obtain prefix function values of s+t for its last |t| characters). So I first precomputed the z values of string s and then wherever z[i] was n-i, I considered all substrings, {(i+1,i+1),(i+1,i+2)...(i+max(|t|),max(n-1,i+10)) and update the 'score' values of each of these substrings. (score value of a string s1 being the prefix function value of s+s1 at the last index, considering only the case when the prefix length is larger than |s1|.) This can be done in O(max(|t|)) per i using a trie structure. Now while processing the queries, I first computed the prefix functions for case (2) as listed above using brute force in O(|t|^2) and for case(1), I just used the score values calculated for all the prefixes of t and updated the prefix function array (by taking max of answers obtained in both cases for each index). This can also in total be done in O(|t|^2) using the trie structure mentioned above. Hence the total complexity of the solution must be O(n.max(|t|)+q.(max(|t|)^2) ~ 2e7 operations which should comfortably pass in 2 seconds, however it TLEs. So can someone find some operation in my algorithm or its implementation which might be the bottleneck time complexitywise?

P.S- n is |s|.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D was very helpful for me to learn bitmasking

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone stress test my submission 175562002 of D or tell me where i am wrong?

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My approach for E:

First, look up all prefixs of s which equals to the suffix of same length. They can be find by calculating the prefix function of s in O(|s|). Then, for a certain prefix s[0...j-1], we store the result of s[j], s[j...j+1], s[j...j+2], ... , s[j...j+9] into a HashMap (where I used key of type int64, because |t|<=10 and number of smallcase letters is 26, which is smaller than (1<<5)=32, so we could use 5 bits for a letter and 50 bits for encoding a string t, which would not cause any collision, and the process can be done by bit operations otherwise may cause TLE). Also we should not let the value of the same key being smaller in the process.

Then for any query of t, we look the value of t[0...i], if we find the value, it will be outputed directly. Otherwise the value must be <=10, then we can find it by brute force.

The time complexity of preparation is O(|s|*|t|), and for each query is O(|t|^3). Total time complexity is O(|s|*|t|+q*|t|^3), which is at most about 10^8, fits the time limit.