ilyakrasnovv's blog

By ilyakrasnovv, 4 months ago, In English

Hello, codeforces!

We deeply apologize for the weak pretests in the problem 1642C - Great Sequence. Anyway, we believe that you liked at least one problem from the contest :)

Thanks to Mangooste for the problem 1641E - Special Positions!

Tutorial is loading...

Solution: 147513897

Tutorial is loading...

Video-tutorial by ak2006

Solution: 147513934

Tutorial is loading...

Video-tutorial by ak2006

Solution: 147513962

Vector solution: 147513974

Tutorial is loading...

$$$\mathcal{O}(2n^2)$$$ insertions solution: 147514019

$$$\mathcal{O}(n^2)$$$ insertions solution: 147514028

Tutorial is loading...

Solution: 147514055

Set solution: 147514064

Tutorial is loading...

Solution: 147514090

Bitset solution: 147514108

Tutorial is loading...

Solution: 147514167

Tutorial is loading...

Solution: 147662463

 
 
 
 
  • Vote: I like it
  • +363
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

It doesn't allow to show the solutions

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

So sad I cannot access to the submissions !

»
4 months ago, # |
Rev. 4   Vote: I like it +101 Vote: I do not like it

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

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

    Thanks for the solution!

    But I have a question: "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."

    But in your submission in line 124 we have this: if (pos < n) ans = min(ans, w[i] + w[pos]);

    Shouldn't it be if (pos < r) ans = min(ans, w[i] + w[pos]);?

    I changed $$$n$$$ to $$$r$$$ and it's also AC.

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

      That line only affects the behavior on the last batch. On any other batch you will never get pos outside l..r-1 range because of the check that the mask is not full.

»
4 months ago, # |
  Vote: I like it +63 Vote: I do not like it

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?)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    vector<int> least_enemy;
    

    In your submission using DSU, what does the least_enemy vector represent ? Also your written code is really clean. very easy to read. Thank you.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If x is a root, then the component of least_enemy[x] is the leftmost component after the component of x which is known to be disjoint from the component of x.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just changed int to double and added fixed setprecision before output the answer. It passed. Here is the submission

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The ans must be an integer, so don't use double for precision loss.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh nevermind. I wrongly understand the statement. It means "keep deleting the lower_bound until we find a value greater than $$$r$$$"

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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'

»
4 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    (sure, I do understand how the problem had weak pretests, but may I at least know why these solutions got TLE'd on the main tests only? I don't think there would have been an edge case that would make the runtime so long either.)

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

      it's because many people used unordered map to solve the problem. umap in c++ generally has constant insertion and lookup times, but there are values that can cause collisions in the hash, thus causing a worst case time complexity of O(n^2). you can read more about it here https://codeforces.com/blog/entry/62393

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        will it be okay if i use map instead everywhere? can map give tle in cases where umap would not? if yes then how to tell?

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

          yeah, it can, just because there are some scenarios where a map's log(n) lookup and insertion are slower than umap. I havent come across many problems where its a big deal though, you can probably just go off of intuition if you're not sure if your code will tle with map. (but typically, it's a better idea to use map than umap if it doesn't make a big difference)

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Cnacu6o for weak pretests of D( ya nje ljubju FST

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

»
4 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I got a different solution for Div. 1C just after contest ended. (https://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.

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

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.

»
4 months ago, # |
  Vote: I like it +67 Vote: I do not like it

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

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

Great contest!

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

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

https://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)
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi,

    I tried to hack your solution with the case that you have described (Hack #788603). Your solution runs in time.

    Generator Used:

    Spoiler
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to experiment your solution in my local machine. It only TLE (runs > 1s) if I turn optimization (-O2, default in Codeforces) off. The compiler is smart enough to optimize out such inefficiency. :)

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

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).

  • »
    »
    4 months ago, # ^ |
    Rev. 6   Vote: I like it +7 Vote: I do not like it

    Never use unordered map in codeforces (or in any other contest). Always use ordered_map (map in c++).

    The reason is the worst case time complexity for both unordered sets and maps is O(n). And you can bet the testers would have created a test case just to exploit exactly that.

    There is no downside to using ordered maps or sets, since the worst case time complexity is O(logn) which is almost never a problem. (log2(10^5) ~ 17, so your search is complete in nearly 17 steps. Running 17 steps is a joke for cf servers and other online judges.)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer is just above. Just scroll up. https://codeforces.com/blog/entry/100249?#comment-889850

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks :) I thought it's almost impossible to get O(N) using unordered_set/map. I don't know properly how it works behind the scenes

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

        It is almost impossible to get O(N) using unordered_set/map in the real world. You are not wrong. It's just that cp is not the real world and the testers happen to know about the weaknesses of each data structure much more than we'd like :)

        There are testers who specialise in creating adversarial test data just to break the hashing strategies of unordered map/set and force it run in O(n). Thankfully such kind of test data is ineffective against an ordered map.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 3   Vote: I like it +10 Vote: I do not like it

          Guys if you are going to downvote my comment, at least explain why. I tried to explain something to the best of my ability, if I am wrong let us know why.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It took me 7 min to load the full picture of problem 'A' and 10 min to post this comment :(

(NO more than 1 comments in 10 minutes)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2C i used map to store all elements count [my submission].(https://codeforces.com/contest/1642/submission/147490681)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

However,unordered_map has shown its great convenience when solving problem C.

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

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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +40 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    I have similar randomized solution.

    Let $$$W=13$$$, then we can produce randomized function $$$\varphi$$$ that maps bits from 0 to 12 to each natural number. Next, we can match each array with a bitmask equal $$$\Phi = \varphi(a_1) | \ldots | \varphi(a_m)$$$. Thus, in one iteration, it is enough to consider pairs of arrays whose masks do not intersect in $$$O(N + W \cdot 2^W)$$$ time. We have to do about 100 iterations of this algorithm for the correct answer.

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

    I tried same approach but always got WA. Maybe my implementation has big constant factors. If we do $$$1000$$$ iteration in TL, we will have about $$$0.98$$$ probability to get a correct answer. But it's not enough to get AC. With $$$0.98$$$ probability per test, we only have $$$0.13$$$ probability to get a AC(pass $$$100$$$ tests), which is still need some good luck.

»
4 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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

Spoiler

should be:

Spoiler
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 you help me? Thanks in advance.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      Otherwise, we can use a segment tree to store such index $$$j$$$ that there is a query $$$0 \ i \ j \ 1$$$ and store it in the i-th slot of our segment tree.

      When we understand that the i-th person might be ill, 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$$$.

      The above two ideas describe exactly the use of segment tree in this problem. The second idea say that $$$l$$$ and $$$r$$$ are the two integers that appears first in the left and the right of $$$i$$$ using our set. Therefore everyone whose index is in the segment $$$[l+1; i-1]$$$ or $$$[i+1; r-1]$$$ are not ill. Hence we can conclude that the i-th person is ill if there exists a query $$$0 \ a \ b \ 1$$$ where $$$l < a \le i$$$ and $$$i \le b < r$$$.

      Since $$$l < a \le i$$$ we can find the minimal element on segment $$$[l+1; i]$$$ and that element would be $$$b$$$ according to the first idea. We can see that the value of $$$b$$$ cannot $$$< i$$$ because if so, there must be no ill person on segment $$$[a, b]$$$. That's why the editorial say that we can just check that $$$b < r$$$ or not to determine whether the i-th person is ill or not.

      Have a good day!

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

“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

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

for problem div2 D can someone elaborate what's with sorting after making a tendem repeat of size 2k and having sequence of size k + some leftover. What's with bringing some elements in-front and sorting.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can also do it by using deques and it is much simpler by using deques. You can see my submission for clarity.

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

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?

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

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).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Can anyone tell me what is the expected rating of problem div 2 D?

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Can anyone tell me in problem Div2 D for this testcase
6
1 3 1 2 2 3
why this answer is not valid
3
3 3
2 8
2 9
3
4 6 2
my solution

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because after printing the number of operations you need to print the no of numbers after which you perform the operations and then the inserted number. Here you have done the printing in the other way around.

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

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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's easy to understand that : if there exists a segment [x,y](when x in [l+1,i], y in [i,r-1]) , the i-th person is ill. Then let's consider the segment [x,y] whose x is in [l+1,i]. There is no ill person in [l+1,i), so y>=i. So "if there exists a segment [x,y](when x in [l+1,i], y in [i,r-1])" is equal to "if there exists a segment [x,y](when x in [l+1,i], y<r)"

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you SO MUCH for your help, after your explanation I started experimenting and finally understood what they meant in the editorial. Sorry for my late response.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

div2 F's solution is so cool!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me, why my code got WA in tC-2 ,no-37. I did without sorting ,just used HashMap and chek if(a[i]*x) || if(a[i]/x && (a[i]/x)*x==a[i] ) GOT WA

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B:

It is given that vertices of a triangle cannot be in a single line. But the graph shows two vertices on the same horizontal line. Can someone kindly explain.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it means the triangle's three vertices won't be in a single line, that's why it's a triangle.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I participated this contest virtually. for problem D, my observation was that: 1. we can reverse a substring s[l:r] by inserting s[r] to s[l] to the front. 2. we never reverse two substring which one is contained in the other. So I tired to solve it with dp[i][j][0/1] which means for s[1:i], the last segment was s[i — j:j], 1 stand for it was reversed, and vice versa. after I calcatuled this dp array, I will construct the operation sequence. But I failed at dp processing, and wondering if this method is resonable.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dang! I forgot that according to bubble sorting, if we can swap two adjacent element, then we can sort the whole segment! why I rushed to implement my bad fragil 'solution' without further thinking, so sad.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

1642B — Power Walking https://codeforces.com/problemset/problem/1642/B Example: 1 6 1 1 2 2 3 3 output:3 3 3 4 5 6 ???? I don't know how to achieve this result ? k= 1,{1 1 2 2 3 3} find the minimum sum of strengths of a team of k children Sam can get. is 3。 k = 2, {1}{1 2 2 3 3} find the minimum sum of strengths of a team of k children Sam can get. is 4??

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Example:
    1 
    6 
    1 1 2 2 3 3
    output:3 3 3 4 5 6 ????
    
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      k = 2, {1 1}{ 2 2 3 3} is 3

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      for k=1 {1 1 2 2 3 3} answer=3 because there are three distinct elements. for k=2 {1 1 2 2} {3 3} answer=3 because sum of distinct elements in two groups is 3. for k=3 {1 1} {2 2} {3 3} answer=3 because sum of distinct elements in three groups is 3. for k=4 {1} {2 2} {3 3} {1} answer=4 because sum of distinct elements in four groups is 4. for k=5 {1} {2} {2} {3 3} {1} answer=5 because sum of distinct elements in five groups is 5. for k=6 {1} {2} {2} {3} {3} {1} answer=6 because sum of distinct elements in six groups is 6. hence the required answer is 3 3 3 4 5 6