When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

awoo's blog

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

1093A - Dice Rolling

Tutorial
Solution (Vovuh)

1093B - Letters Rearranging

Tutorial
Solution (Vovuh)

1093C - Mishka and the Last Exam

Tutorial
Solution (PikMike)
Naive (PikMike)

1093D - Beautiful Graph

Tutorial
Solution (Ajosteen)

1093E - Intersection of Permutations

Tutorial
Solution (PikMike)

1093F - Vasya and Array

Tutorial
Solution (Ajosteen)

1093G - Multidimensional Queries

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone link this editorial to the contest materials?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the Intersection of Permutations editorial in more detail?

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

    You can read about 2D-BIT at topcoder.

    The idea about offline trick comes from the treap implementation. With treap you would do something like: for each BIT x in query sum up the amount of numbers which are less than or equal to y. Imagine processing the same thing with BIT. At first glance it seems like you would need to do operations "add 1 in y" and "get prefix sum up to y". However, you don't need all the points up to max coordinate. You can compress the numbers in each BIT and find needed position with binary search.

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

Can anybody help me why I m getting Runtime Error On Test Case 9 in The Most Discussed Beautiful Graph Problem My solution.

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

Could someone tell me why I got TLE in problem D? Here's my submission. Thanks a lot!

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

    Number of test cases = 3e5, and for each test case you memset the whole colour array and first array, which are also 3e5.

    It is stated that it is guaranteed that summation N over all test cases doesnt exceed 3e5, so for each test you should manually loop on array 0->n and clear it yourself, which gives a total accepted complexity of 3e5 over all test cases.

    Here is your 47162894 updated :D

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

      Thank you for your detailed explanation, which helped me a lot :D

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

        Its okay :D, I also got time limit for this reason in the contest :(

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

It's giving me runtime error on Scanner Class.

https://codeforces.com/contest/1093/submission/47155880

Every time I got stuck with this scanner shit.Please give me any alternative.

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

Is there a recursive(with memoization) implementation of Problem F? I didn't fully get the editorial.

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

    You can code it recursively but it won't look easier. I can tell you my more straightforward approach.

    Let it be the same dp and sdp definitions. Now you want to update dp[i][lst] by making the last segment of value lst. That means that there is some position prv, where the segment of maximum length of value lst could start (this length is found with len and position of the rightmost element not equal to  - 1 or lst.

    Thus you want to sum up all the dp[j][l] for j = prv... i - 1 and l = 1... k, that is sdp[j]. However, the previous segment couldn't end with lst, subtract dp[j][lst].

    Add a little bit of maintaining partial sums over both dp and sdp arrays and you'll get the same complexity.

    Code

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

Can anyone explain to me why problem F's solution is right?

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

Can someone explain the reason behind solving 2^a+2^b in problem D ?

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

    The last sentence explains it? If the graph is bipartite then the only coloring exists (color vertices of the first partition white and the second is black). White is one of {1, 3}, black is {2}. That is 2size colorings. And then change white to {2} and black to {1, 3}.

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

      Hard to Understand the solution of D. What have changed if there were only two numbers 1 and 2(not 3).Please explain the reason for 2^a + 2^b .

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

        1 and 3 are the same in terms of making pairs. So you can put either 1 or 3 on each vertex, that is 2 options. Thus it's 2size. With only 1 and 2 you'll have a single option for each vertex, it would be just 1.

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

          Then why, 2^size for both parts. By your explanation it should be 2^a for one part(1,3) and simply 1 for another part(2).

          Can also you explain why res = res * cur for each iteration on Node in Code.

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

            It is 2a for part {1, 3} and 1 for part {2}. But then you swap parts and color the first part {2} and the second part {1, 3}.

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

            The colorings on each connected component are independent, so we multiply their answers.

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

Can someone help me out with my code? I did exactly what is mentioned in the tutorial however couldn't pass the second pretest during the contest. Here is the link to my code: https://ideone.com/jWlp4l

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

    Shouldn't fl be the other way around? The answer is 0 if at least one connected component isn't bipartite.

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

      Oh! Didn't take care of that. Thanks, it worked by changing fl the other way round. Was a little bit confused.

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

Can someone help me out with my code? It kept getting Runtime Error on Test Case 10 in problem E. I'm using persistent segment tree and I can't find anything wrong with it. Here is my code. Thank you so much if you could help me figure out the problem.

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Another approach for problem F:

Let dp[i][j][k] : the number of ways of fill the firsts i elements where j is the last element and appear k times, this is O(N * K * N) in memory, but only need dpi - 1 for update dpi so the memory become O(N * K).

Looking what happen into the transition when a element x come? There is two cases:

x ≠  - 1: how the element is fixed dp[j][k] will be 0 except for j = x, more precisely dp[j] should be shift one position because all the ways of end with j increase by 1, and a new value should by put in dp[x][1], these value is such that l ≠ j , in other words all the ways of end with other element, and if dp[x][len] become greater that 0 then make it 0, because this is a invalid array.

x =  - 1: fix every possible element and do the same as for x ≠  - 1 K times.

So i need something that support insert one element in the front and delete in the back, and have the sum of all of it's values, this is possible with a deque!!!

Keeping K deque one for each possible element the transition can be done in O(K), and the time complexity become O(N * K).

For more details of the implementation see my code:

Solution
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Can someone explain me, In the F problem.. Why are we subtracting dp(cnt-len,lst) as well and not only sdp(cnt-len). Thank you.

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

    If you don't connect new correct segment of color lst with some previous one then you'll never break any conditions. And if optimal answer has these segments merged then you'll still visit this state.

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

      Where does this color come from? Are you saying that gray is much far from Red? :P

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

For Problem F... I still can not understand why the number of the bad status is sdpcnt - len-dpcnt - len, lst,can you explain it more specifically?Thx...

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

From what I understand, the soln for G will NOT work if the queries is asking for minimum distance, right? Is there some other way to solve it if the problem asks for minimum?

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

if((col[v] ^ col[to]) == 0) bad = true; anyone please explain the working of the statement from the editorial of BEAUTIFUL GRAPH??

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

    If two neighbor vertices have numbers 2 or {1,3} both then sum would become even. So it's checking this only. Like col[1]=1 and col[2]=1 then col[1]^col[2]=0.

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

For problem E, I don't understand what the tutorial is talking about. What is "update in point and sum on rectangle"? And how exactly are we remunerating the numbers?

Edit: Finally got it, I was imagining you meant reordering rather than renumbering. So for example if

a = [5, 1, 4, 2, 3, 6] b = [2, 5, 3, 1, 4, 6] then the new b should be [4, 1, 5, 2, 3, 6], changing each number in b to the position of the corresponding element in a. So the first element in b becomes 4 because the index of 2 in a is 4.

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Despite what they said in the editorial sqrt decomposition is fast enough to pass E. General idea split a and b into chunks. Each chunk of b has a segment tree that keeps track of how terms the chunk has in common with all other chucks of a. Updates take , since you have to update at most four segment trees. For the other type of query you brute force part of the query so you only have to deal with intersections between whole chunks of a and whole chunks of b. Then for each chunk of b contained in the query you use the segment tree to find the number of terms it has in common with all chunks of a contained in the query. Worst case complexity for queries is . Final complexity , and yes this is fast enough to pass. My code 47287195.

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

    I used a similar sqrt-decomposition technique with BIT. One important thing to note is block size you choose can have a big impact on your runtime. For my implementation, I was updating the BITs for each block frequently, so it was advantageous for me to choose a larger block size. With a block size of , I was able to get it to run under 2000 ms, faster than the official soln. 47315299

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

      That makes sense to use a larger block size. It seems like the trade off is between how far you travel to get to the ends and starts of blocks in the brute force part which favours a smaller block size and how many blocks you have to iterate over in the segment tree/BIT query part which favours a larger block size. The second part is more costly because there is an extra log factor when you do the queries. I suspect you could use calculus to figure out the optimal block size.

      For my implementation a block size is much slower (3931 ms) than (2558 ms). The best block size that I have found for my implementation is it gets (1825 ms) 47317374.

      It is interesting how a similar sqrt-decomposition approach can have such different optimal block sizes.

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

Problem D Can someone help me? My solution is giving TLE on test case 13 https://codeforces.com/contest/1093/submission/47291028

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

1093A

https://codeforces.com/contest/1093/submission/47239530

Why was this solution not accepted? Can somebody help?

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

Anybody please explain why 2^a+2^b work in problem 1093D — Beautiful Graph.I need mathematical proof.Please help

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

    You have two parts of size a and b, we want to proof that one of them should be totally odd and one of them should be even. We obtain this fact using induction on length of a path. We assume that vertices of this path should be like: odd,even,odd,even,... now erase the last vertex and we can apply to induction hypothesis, after that add this vertex and the erased edge. Since one of the endpoint of that edge is odd(for example), this vertex should be even. So for each two vertex in same part, they should be as same cause length of every path between them is even. Now there is two case: 1:part with a vertices be odd, we have 2^a to choose that every vertex should be 1 or 3. 2:part with b vertices be odd, we have 2^b like previous case.

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

Thanks for problem G, short and nice.

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

can anyone explain me the last statement in pikmike solutions forn(mask, 1 << k) ans = max(ans, abs(bst[(1 << k) — 1 — mask] + bst[mask])); printf("%d\n", ans);

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

    In bst I have the minimum value for each mask (the values of ci of editorial). And I also know that ci will have all its signs turned if I replace 0 with 1 in mask and 1 with 0. That is the same as doing (2k - 1)^mask (or minus as I do). Thus bst[(2k - 1)^mask] will have the maximum value of mask but with multiplied by -1. I wanted to update the answer with (max - min) and I have min and ( - max). So I can do ( - ( - max) - min) or |max + min| (as I surely will have the non-negative value in a result).

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

In tutorial for problem G, should time complexity be for the code you give? I think they are quite different.

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

    What makes you think that?

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

      In your code, it cost you time on the segment tree and O(2k) time to modify or update bst after it for each modification or query. The time used when building the tree is O(n2k). Thus the time complexity is . To get the result , we could build 2k segment trees, and I got TLE when implementing this(my submission). Actually, the difference occurs when dealing with query and modification, one is each time and the other is , which makes me think they are quite different.

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

        It costs me on both update and get queries. There are loops of 2k iterations on each of these functions. I also do have 2k segment trees, it's just the traversal order that differs. I have the other submission, which does about the same as yours and it works twice as slow. It seems, you should consider the time spent jumping around in memory while implementing it.

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

          I got it. Thanks for your explanation and sorry to take up your time.

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

While I (somewhat) understand how the solution to problem E works, and I've also read the article on Topcoder (about BIT, and another about RMQ),

I really don't understand how to come up with such a solution , the rectangle method seems quite non-intuitive .... can someone give any suggestions on this based on their own experience ?

Thanks a lot !

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

    To be fair, problems of kind "answer something on a segment" don't come in lots of different forms. Like all of them are divided into:

    • precalculate something on prefix
    • segment tree
    • Mo

    This problem clearly doesn't fit into Mo category, prefix is also kinda weird here. Thus is probably segment tree or some other online structure.

    And there is another common trick. When you have several synchonized permutations but the exact values on them doesn't matter, you can renumerate one of them to identity permutation. I personally met this technique quite a few times.

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

      Hi PikMike,

      Thank you for taking out the time to answer my question.

      Could you kindly clarify what you mean when you say "renumerate one of them" ? Do you mean getting rid of one of the permutations by finding a common property of the elements of the permutation (like in this question we reduce 2 permutation arrays to a single array by representing each number as a coordinate) ?

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

        Yeah, essentially it is getting rid of one permutation. In some cases you can just abandon this one, in some you will still need it (but at least in will be 1, 2, ..., n). The latest problem on this trick I remember should be 1043D - Mysterious Crime.

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

Need help for problem G, from what i understand from the tutorial, we will build 2k segment tree, each tree will be based on the value of , then we will take the maximum and the minimum of each 2k and take optimal distance as the result, is this right? and how can do this since each of |ax, i - ay, i| already has their fixed ci?

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

    You don't take arbitrary ci but the opposing ones. Take the easiest case — point x is larger on each coordinate than point y. Thus, you'll need cx be all ones and cy be all minus ones. However, for any other pair of opposing in each position values of c the sum will not exceed the appropriate pair. This concludes that the right values of cx and cy will have the maximum result of all candidates. The other cases of relative positions also follow the same principle.

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

      Hi @pikmike, i was solving october Long challenge and that has question very similar to question G . Can you please explain how we are querying the max and min in the range ??

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

I think the naive solution for Mishka and the Last Exam is not correct. It's getting TLE on the 9th test case. http://codeforces.com/contest/1093/submission/47462619 Or Should it get a TLE that's why it is the naive solution?

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

    Yeah, it's TL but much simpler logic. That's why it's called naive.

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

can someone explain PROBLEM E in easier manner? i really confused.

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

In problem E, square root decompsition + binary indexed tree solution is getting accepted, when block_size is fixed about 800, but getting TLE when block_size is used by sqrt(n). In both solution each update is O(4*logn) and each query is O(2*block_size + (n/block_size)*logn) and pre build is O(nlogn).

So, is data set weak for problem E? Isn't it possible to create such input so that this solution can't get accepted?

Accepted using block_size = 800: 47504503
TLE on test 16 using block_size = sqrt(n): 47504554

**Update: ** Accepted solution runs in about 2.5 sec, when block_size is 1700.

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

    My algorithm with block_size sqrt(n)[about 500] get Accepted. 96324829. I think it's not necessary use BIT and vector is enough.

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

I keep getting TLE in D on test case 22. Can anyone tell me what's the problem? Here's my solution.

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

    u should set by hand, not memset ! With memset u get a complexity of O(N) so a total of O(N ^ 2). setting it by hand would result in a complexity of O(N) because the sum of N over all test cases is smaller than 3e5

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

Can somebody help me with my code on F ? I checked myself many times with the provided code but i find nothing suspicious. I get WA on test 4 47825046

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

Please, someone, suggest me some material of how to compress numbers in a 2D BIT. I am unable to get how Editorialist of the Problem E is compressing the numbers in each BIT.

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

I am getting wrong answer in prob. D, test case 3,that is , for some cases my code is giving output 0, anybody got any ideas? Link to the code :

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

Hello, can anyone explain to me why my code of problem "D-Beautiful Graph" is not working? I tried to make it as similar to example code as possible but still does not work. my code

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

I did the same approach as Editorial for problem D but I got wrong answer at test 3. Could anyone help me figure out what wrong with my submission 62551741