vovuh's blog

By vovuh, history, 13 months ago, In English

Suddenly, all problems expect A and D were invented by me. The author of A and D is MikeMirzayanov.

1234A - Equalize Prices Again

Tutorial
Solution

1234B1 - Social Network (easy version)

Tutorial
Solution

1234B2 - Social Network (hard version)

Tutorial
Solution

1234C - Pipes

Tutorial
Solution

1234D - Distinct Characters Queries

Tutorial
Solution

1234E - Special Permutations

Tutorial
Solution

1234F - Yet Another Substring Reverse

Tutorial
Solution
WA?
 
 
 
 
  • Vote: I like it
  • +112
  • Vote: I do not like it

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

Fenwick appraoch for 1234D : Solution

Implementation similar to: CodeMonk Problem

Awesome contest by the way! :D

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

    I used bitmasks and segment tree instead: 61684182

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

      I also used a segment tree but I used sets instead of bitmasks: 62130226

      Apparently it is too slow... Can anyone explain why? by how much? or if it has a worse complexity time than the tutorial or other solutions?

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

        Sets would be slower by a constant-ish factor (final complexity about $$$O(n \log n \cdot A \log A)$$$), since there are at most 26 distinct letters. This could be significant, as bitwise operations are one of the fastest hardware operations that a computer can do, compared to having to clear and rebuild trees every update.

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

          Thanks a lot! I have submitted it using bitmasks instead of sets. It went from more than 2 seconds to just 140ms (because ofthe constant-ish factor!): 62184825

          Thanks again:)

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

      I also used segment tree with bitmasks, each node would be an integer whose ith bit represents whether the character is present in the range or not, and the answer for any l,r will be the logical OR of the subsequent segments, But i am getting a wrong answer.

      Solution Link : https://codeforces.com/contest/1234/submission/92510866

      Edit: Found the error. Accepted

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

    Can you please tell me how you came with the intuition of using Fenwick tree?

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

      From what I can tell it's the same concept as explained in the editorial, except that he's using a Fenwick tree instead of an ordered set for "does the character exist in this range" queries

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

      Spheniscine Correct!

      pyduper I am assuming you know basics of BIT :)
      Notice that the question wants us to find if a character exists between the range l to r. ie. for all characters from a to z if their count(l to r) > 0 or not.

      Which we can easily do by creating 26 BITs for every alphabet(and basically do what a BIT does)
      So the ans for total distinct elements between l and r would be like :

       for(int i = 0 ; i < 26 ; i++){
             int count = query(BIT[i],r) - query(BIT[i],l-1) ;
             ans += count > 0 ;
       }
      

      Updating BITs :
      Assume we need to change arr[index] to char ch what we notice here is that we have to decrease frequency in BIT[arr[index]] at index by 1 and increase frequency of BIT[ch] at index by 1
      which would be like :

       update(BIT[s[i]-'a'],i,-1) ;
       s[i] = ch ;
       update(BIT[s[i]-'a'],i,1) ;
      

      Also the complexity of the code would be : NlogN + 26*QlogN which is quite feasible :)

      Thats it!

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

        Thanks.. I accidentally down voted instead of up voted. I cannot change it now. I am really sorry.

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

    funny thing that I saw a lots ppl like you, they knew a lots advanced things that I only heard about, like segment tree or fenwick tree or dp on tree, but the most important thing that you and they are the same, just only specialist. So the question I want to know that why you know a lots but you cant do anything gud in official time of a contest, and can I archive candidate master without knowing about segment tree or fenwick tree. I really need to know answer for this question, help me if you can, plz!

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

      Well, it's just been a year since I knew about CP and if you see my rating graph I was not serious at all till april-may(mostly because I was into development at that time) so that makes about 7-8 months.

      If you ask me the reason the obvious answer would be lack of practice(I have just solved about 400-500 problems (mostly easy-med) over coding websites all together).

      looking at my graph I think I am kind of improving (maybe?)

      important My personal thoughts: BIT should not be considered as hard as Segment Tree (according to me a person with 1400+ rating can easily understand and implement BIT).

      BIT just requires 8-10 lines of code to implement. Also, I've never actually required to implement a seg tree in questions of rating < 1900 (mostly) but that's just my personal thoughts :D.

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

        My opinion is that BIT is easier to code, but harder to intuit, while segment trees are the opposite. Segment trees are more powerful (it can solve any problem BIT can, and some problems BIT can't), but BIT tends to be faster constant-wise.

        This problem is actually quite instructive about the difference, cause you need 26 sum-BITs, one for each character, but only one OR-segment-tree. Segment trees can work on any monoid (type/set with an identity value and an associative binary operation), but BIT has the additional requirements of the operation being reversible and commutative, hence working on + but not on OR (which is commutative and associative, but not reversible).

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

    Hi Dsxv

    1234D

    I tried with an approach similar to the one mentioned in editorial. The only difference between the implementation is: I used array of sets while they used vector of sets. Could you please tell me what's wrong with my solution:

    62051065

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

      I think the 'lower_bound' in your code is working in linear time. Just replace it with ( it = contain[i].lower_bound(l) )

»
13 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

My solution to E: https://codeforces.com/contest/1234/submission/61676673

Just consider how the distance of each pair in the array changes in permutations.

Let the smaller number in the pair be m and the other be n;

The distance increases by m-1 when i=m because m goes to the front and the distance increases 2m-n when i=n because n goes to the front and m shifts 1 backwards. For i from m+1 to n-1 the distance simply decreases 1 because one of the number between them goes to the front.

I hope my explanation makes sense as English is not my first language:D

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

    can you please elaborate?

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

      In the first to (m-1)th permutations the distance between m and n is constant. In the (m)th permutation, the number m goes to the front of the permutation so the distance increases by m-1. In the (m+1)th to the (n-1)th permutations, one of the number between m and n goes to the front so number m shift one unit back thus their distance decreases by 1. In the nth permutation the number n goes to the front while number m stays in the position of m+1 so now their distance is m+1-1=m. The distance used to be n-m so the change of the distance is m-(n-m)=2m-n In the rest of permutations, their relative position is back to normal so the distance doesn't change.

      Does this make sense?

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

Weak Example in F makes me WA on 5........ I want strong example QAQ (sorry to my poor English :D

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

How can we do C with dfs?

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

    You will TLE

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

      C can be solved by dfs by building a graph like this: example

      and check if there is a path.

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

        Can you please explain how to do it with dfs with proper code and explanation?

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

            what do the various directions specify in your code

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

              direction in which water is entering.

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

          I got accepted with dfs, the ideia is basically what MZuenni said:

          Firstly you make two types of edges, {1, 2} and {3, 4 ,5 ,6}, and you can see that with edges {1, 2} you can only continue on the line that you are, going to the next column, and with edges {3 ,4 ,5, 6} you go to the next column changing your line (see the picture above).

          If there is a path, then there is only one of them, by the "nature" of the edges, so the complexity is O(n).

          Here is my submission: 61677625, hope to be clear enough.

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

          C.Pipes using BFS/DFS--

          1. Simplify given strings into just 1s and 3s.

          2. Create a directed graph

          3. If it's a 1-pipe, add an edge from i to i+1 (Don't add for end of row1)

          4. If it's a 3-pipe (in both rows for that column),connect it diagonally from row1 to row2 or row2 to row1. (Don't add for end of row2)

          5. Use BFS/DFS to check if 2*n+1 th node is visited or not

          Python implementation-- https://codeforces.com/contest/1234/submission/61743877

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

    u can use dp also.taking care of direction in which water is coming(horizontal-0,vertical-1),x and y co-ordinates. u can refer to this submission

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

It is obvious that because of dynamic programming we need to remove at most one bit from our mask to cover all possible submasks that can update our answer. What is this means ?

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

    Now I understand it , becasue some dp[mask] may not init

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

I did the testing for F and found out few Test Cases. Surprisingly the WA code when ran on custom innovation, It gives same answer as that or correct code, But when it's executed locally or on some other online Compiler(other CP sites like codechef), the WA program fails on following Test Cases.

Test Cases Where WA should fail

Though If anyone finds the reason behind the behaviour of WA code in Custom Innovation, do let me know. I'm quite curious about this.

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

    That's because CLOCKS_PER_SEC in codeforces is 1000, but in other compiler (I used Dcoder) is 1000000. So clock() gives microseconds. Instead you should set , (clock()-tt) > (1.90)*CLOCKS_PER_SEC).

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

My code for problem C. https://codeforces.com/contest/1234/submission/61656247 Can anyone help me with that? I considered that the number of 3,4,5,6 type pipes should be odd and if a pipe is of 3,4,5,6 type in one row,it should be of the same type in the corresponding index of the other row.

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

I also applied segment tree approach 61686336. But it's giving TLE. Can anyone please tell me where I went wrong?

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

    @gaurav_iiitian check my code I used segment tree and it got accepted. My code was easy to understand..

    link — https://codeforces.com/contest/1234/submission/61689286

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

      Thanks @dhruv_garg for replying, But I think our implementations are almost same. The only difference being I coded in python. I think codeforces hasn't set time multiplier for python since my code is giving TLE in just 2s which should be 10s for python. @admin look into this please. I'm really disheartened to see this in codeforces and it's my early days here.

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

        Same story, but I did it after contest by adding some optimizations. Firstly I used bit representation for each char: 'a': 1, 'b': 2, 'c': 4. We have an alphabet with size of 26. So 'z' is 2^25. And if you want to know the sum, you just do bitwise OR (Node1 | Node2). Then I precalculated bit representation for every char and stored it in the dictionary. I added the popcount function (https://stackoverflow.com/questions/407587/python-set-bits-count-popcount) for [l, r] requests. Python got TL on 9th test, but PyPy got AC with 1980 ms. Here is the submission 61730030. Hope it will help.

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

          Nice approach, I got TLE once during contest and after that many times. I stored all the characters in a dictionary of 26 keys where we can directly check which of the character is present or not (count==0). But yours might do better since xor is better than (looping 26 times). Mine gave TLE on test case 13 on PyPy. I'm really hopeful that moderators and admins take a note of this and in future this don't happen.

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

    I also got TLE when I implement segment Tree with Python...@admin please have a look at this..

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

I used approach of tutorial D. Can someone please explain why lower_bound(s[i].begin(), s[i].end(), l) is getting TLE but same solution with s[i].lower_bound(l) instead, not?

Only difference is way of using lower_bound.

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

Why does ceil(double(sum)/n) give a wrong answer on but (sum+n-1)/n doesn't.

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

can someone help in finding issue in this code https://codeforces.com/contest/1234/submission/61661254. it's failing on 1 test case on codeforces compiler. but locally it passes

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

Can anyone tell me why I got TLE by using char instead of string in problme D?(I used the same approach as the tutorial, I switch char to string then it got accepted)

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Well. I have a deterministic solution for F. Vovuh I don't know where your solution will break. But intuition is not coming. My approach:

dp[mask][len] will store maximum starting index for all the submask of mask with length len. then we can simply find the answer for it's complement for all length. link to my solution:

61694665

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

    As you can see, my main solution is deterministic too (and it solution is described in the editorial). Moreover, my second (possibly WA) solution is also fully determined (except the order of masks with the same number of ones).

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

Damn slow python... Got TL with Segment Tree

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

Very Nice Explanations and Clear Editorials.

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

I wonder why I got TLE in pronlem D when using Segment Tree......(61656622)

(sorry for my poor English x(

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

My solution got tle in D in system testing and the same solution is accepted on submitting after System testing

https://codeforces.com/contest/1234/submission/61710080

https://codeforces.com/contest/1234/submission/61641496

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

    Your accepted solution took 1996ms which is too close to limit of 2s. difference of few ms in runtime can happen due to various factors.

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

I think this is not as simple as before

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

unordered_set let me down on B2 :(

Nice tests!

This post helps, in case anyone who used unordered_map or unordered_set needs it.

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

After the contest I tried to write B2 with STL deque,but when I use unordered_map it got TLE but map got AC.In my previous conciousness map should be slower than unordered_map,what's wrong with unordered_map in B2?
The unoredered_map version TLE:61711501
The map version AC:61711675

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

    unoredered_* very slow if hash function have a lot of collisions. Author know stl implementation of hash function and generate special tests. Map (non unordered) is a tree and have determine time of work.

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

    You can read this

    If you use unordered_map, your time complexity may up to O(n).

    (and, sorry to my poor English

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

      So, when is the ideal scenario to pick unordered_map over map if we want to use it as hash?

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

SquareRoot Decomposition approach for D: 61667541

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

    Thank you I was searching for this

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

    Do you have any other snippets for sqrt decomposition for others problems that you can share ?

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

Need help in this. https://ide.codingblocks.com/s/137727 for problem D this solution is getting WA for test case 2 https://ide.codingblocks.com/s/137726 I just switched line 91 and 92 got AC for all the test cases. Why am i getting this. I created 26 sum query segment trees and for every alphabet if the sum of segment is greater than 0 then there is that distinct character in it and I increased the answer for that query. Why does swapping two line get me WA?

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

For B2:

Changing from unordered map to map gave AC. The unordered map is faster than the map then why did I get TLE?

Thanks.

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

Hey Comunity! I am getting TLE in problem 1234B2 for test case 23. Can someone please help me? my sol

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

I dont think prob E is a 2000-difficulty problem, just like a 1700 or 1800 problems in a div2 contest. I also saw a quite easy task in another div3 before that had 1900-difficulty. I feel weird when there are a lots overrating problems in div3, so I wonder how ppl rate difficulty for problems

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

    Yeah that's true. It's probably because many high rated coders just solve the last problem and leave the contest. And the algorithm thinks they couldn't solve that problem. I am not sure about this. I am just guessing

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

    Problem rating are decided by relativey how many official contestants mangage to solve it during live contest. Majority of people do not get time to even read last 2 questions hence they could not solve. Ultimately, that leads to over-rating.

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

Anyone can explain why using std::set gets AC but gp_hash_table (policy based data structures)(https://codeforces.com/blog/entry/60737) gets TLE? I'm very confused.

AC: 61716953

TLE on test 20: 61712878

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

    dont use hashtable, its overkill in this case, and also hashtable sometime is not a gud choice because of hacks. Consider using a deque instead, this task is all about how to work with a double end queue and nothing else

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

      Yeah, i just used hash table to check if elements existed in queue or not.

      But I can not understand why set + deque = AC but gp_hash_table (as I know it's 4x faster than normal std::map) + deque = TLE. It's weird.

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

        I am not sure but what he mean is that it can be hacked. refer this blog

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

I used a segment tree for problem D. I tried the segment tree that had unordered_map(61658230),set(61650912) and map(61656330) as elements of its nodes but all three showed TLE. Can anybody help me figure out where is the mistake in my code.

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

As C have only 2 input strings, I zipped them, and used regex with eval, analyzing pairs of symbols (columns). An alternative to if-else blocks. Perl code 61668008 (or shorter without zip: 61669016)

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

can anyone explain why it TLE on b2 https://codeforces.com/contest/1234/submission/61635087 I think complexity is best possible

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

Alternate approach for E, any two consecutive elements of the array x and y contribute abs(x-y) to all f(pi(n)) where i is less than min(x,y) or when i is greater than max(x,y). x and y contribute abs(x-y) -1 to all f(pi(n)) when i lies between x and y.

Using a Segment tree with lazy propagation we can do the above contributions/range updates for all pairs of consecutive elements. Answers will be the ranges i,i for i: 1 to n

Here is the code : https://codeforces.com/contest/1234/submission/61666909

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it

In problem B1 and B2 i have used Dequeue and Unordered_Set, these are my solutions:-(both are same) B1:- link B2:- link

unordered_set should work more efficiently than set as per time complexity, but in B2 i got TLE on Test Case 23 , after changing unordered_set to set i got AC:link Please anyone explain me why this happen? and also how should i select set (i.e unordered_set/set) while solving any similar problem in future!!

Thanks!

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

In problem E, I have this stupid question which I cannot figure it out on my own -_- .

In the code provided above:

for (int i = 1; i < n; ++i) {
		res[i] = res[0] - cnt[i];
		for (auto j : adj[i]) {
			res[i] -= abs(i - j);
			res[i] += j + (j < i);
		}
	}

So why res[i] += j + (j < i) here. I thought when we move the element i to position 1 then the cost should be res[i] = j-1 + (j < i), shouldn't it?

Thanks in advance <3

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

    I don't sure my answer what exactly do you mean but if I understood you correctly, that's because $$$i$$$ and $$$j$$$ are $$$0$$$-indexed in the code.

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

    He has decremented values of a[i] initially that's why res[i]=j+(j<i).

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

Problem D: I implemented editorial's solution in JAVA. For that I had to use TreeSet for lowerbound() function. Here's my JAVA code: 61727406

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

Can somebody explain me problem F's soln? Sorry but i am unable to understand the editorial?

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

can someone

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

Need DP idea of Problem C.

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

C.Pipes using BFS/DFS--

  1. Simplify given rows into just 1s (1,2=1) and 3s (3,4,5,6=3).

  2. Create a directed graph

  3. If it's a 1-pipe, add an edge from i to i+1 (Don't add for end of row1)

  4. If it's a 3-pipe (in both rows for that column),connect it diagonally from row1 to row2 or row2 to row1. (Don't add for end of row2)

  5. Use BFS/DFS to check if 2*n+1 th node is visited or not

Python implementation-- https://codeforces.com/contest/1234/submission/61743877

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

can anybody explain, what does this mean ?

"Let dp[mask] be the maximum number of ones in some mask that is presented in the given string and it is the submask of mask" , here what does the submask of mask mean?

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

    The submask has fewer or equal number 1s than the mask and the position of all the 1s in submask coincide with the 1s in mask (the mask includes the submask)

    For example : 010011 is the submask of 011011

    This is my opinion so correct me if I'm wrong <3

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

      can you please explain how the submask is helping in dp , I have understood till the point in editorial that we have to find two non-intersecting mask in the string and the one of the pair with max sum from both mask will be answer, but I can't understand beyond because of not able to understand the role of submask in dp further from here.

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        if (dp[mask] == __builtin_popcount(mask)) {
        			int comp = ~mask & ((1 << 20) - 1);
        			ans = max(ans, dp[mask] + dp[comp]);
        		}
        

        So the point the submask is important is :

        • $$$dp[comp]$$$ will be the maximum number of 1s from all the submasks of $$$comp$$$ (include the mask $$$comp$$$ as well)

        • We don't know if the " $$$comp$$$ " mask is really present in the string or not, so we need to take the max of the submasks so that it is added to the answer.

        For example:

        • $$$mask$$$ is ...100110 ( $$$dp[mask] == __builtin_popcount(mask)$$$ ) --> this ensures the mask is present somewhere in the string) (...bcf...)

        --> $$$comp$$$ is ...011001 ($$$comp$$$ may or may not present in the string). So if we don't take the max of the submasks then $$$dp[comp]$$$ will be 0 then. But let suppose there is a substring (which is a submask of $$$comp$$$) ...010001 (...ae...) then $$$dp[comp]$$$ will be >0 (say, 2) and the answer is larger.

        P/s: if $$$comp$$$ doesn't intersect with $$$mask$$$ so the submasks of $$$comp$$$ doesn't also

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

Didn't understood the tutorial of E could someone pls elaborate on making prefix arrays.

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

    My approach is somewhat different:

    Let $$$F_j$$$ represent the $$$j$$$-th answer value, i.e. $$$f(p_j(n))$$$.

    Now consider each consecutive pair in array $$$x$$$, i.e. $$$x_i$$$ and $$$x_{i+1}$$$. We want to consider this pair's "contribution" ($$$|pos(p_j, x_i) - pos(p_j, x_{i+1})|$$$) to the final values in $$$F$$$. Let the smaller of the pair be $$$l$$$ and the greater be $$$r$$$ (if they are equal, their contribution to all values of $$$F$$$ are zero, so we can skip it)

    It turns out that we can split these contributions to five regions:

    • for indices $$$j < l$$$, we want to add $$$r-l$$$ to $$$F_j$$$,
    • for index $$$j = l$$$, we want to add $$$r-1$$$,
    • for indices $$$l<j<r$$$, we want to add $$$r-l-1$$$,
    • for index $$$j = r$$$, we want to add $$$l$$$,
    • for indices $$$j > r$$$, we want to add $$$r-l$$$.

    Now the problem reduces to the "Array Manipulation" problem from HackerRank, i.e. we need to find a way to efficiently add values to entire ranges of indices. It turns out that there's a simple solution: instead of working on the final array $$$F$$$, we work on another array $$$D$$$ instead, where we want the eventual value of $$$D_i$$$ to equal $$$F_i - F_{i-1}$$$. We can then extract $$$F$$$ from $$$D$$$'s prefix sum.

    So if we want to add e.g. value $$$x$$$ to $$$F_{a..b}$$$, simply add $$$x$$$ to $$$D_a$$$, and subtract $$$x$$$ from $$$D_{b+1}$$$.

    Sample code (Kotlin): 61688222

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

      How did you come up with those five contributions ?

      Edit: Nevermind, that's simple observaton. Got it.

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

Problem A can also be solved using binary search :: Solution : https://codeforces.com/contest/1234/submission/61633785

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

【Problem E】 I did not understand what tutorial says. please tell me what cnt[min(x[j],x[j+1])+1] and cnt[max(x[j],x[j+1])] stands for.

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

    Because all the number from $$$min(x[j],x[j+1])+1$$$ to $$$max(x[j],x[j+1])-1$$$ will have their presence increase by 1 so $$$cnt[min(x[j],x[j+1])+1]++$$$ and $$$cnt[max(x[j],x[j+1])]--$$$. From the number $$$max(x[j],x[j+1])$$$ till on doesn't increase so we decrease 1 at $$$cnt[max(x[j],x[j+1])]$$$

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

Has someone solved D with a segment tree with bitmasks, or am I alone dumb?

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

    If you mean problem D, yes I did it that way too (after contest time though, cause the contest time wasn't convenient for me, but I solved it blind)

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

      Lol, I forgot write problem which I meant, anyway thx for answer

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

F. Yet Another Substring Reverse ( with explanation )

Check out my solution for more detailed explanation : 61824886

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

Can anybody help me with the problem C though my approach is similar to tutorial given Here's my code: https://codeforces.com/contest/1234/submission/61957647

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

what is __builtin_popcount??? i don't know it

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

great tutorial!

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

F is beautiful problem

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

In problems like C, we can take input in two ways, a string input or (int or char) input in array? I'd like to hear advice on what should be used in such cases? Is string input faster than array inputs in C++? How dose C++ take string input internally? Does it also create an array first and store characters in that array? Thanks :)

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

I have a question about pipe. In the context we could reasonably assume that the we are searching in 0th pipe and 1st pipe. If we encounter 3,4,5,6, we will make cur = !cur or cur ^= 1 The logic is simple, but when I tried to use an array of dimension 2 x n, the test 2 is always failed. Then I switched to string array dimension of 2, by the same algorithm, my answer was accepted. What is the difference?

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

1234B2 can be solved in linear time (O(n)), using BITSET: https://ideone.com/W1jsgi

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

I guess I find a counter test case you mentioned in Tutorial-1234F.

#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
using namespace std;
const int N = 1e6;
int main()
{
  std::srand(std::time(nullptr));
  int i = 0;
  for(; i < 19; ++i) {
    cout << (char)('a'+(i%19));
  }
  for(; i < N-2; ++i) {
    cout << (char)('a'+(rand()%19));
  }
  cout << "aat" << endl;
}

The answer should be 20, but may got 19 when using WA?-solution. counter test case like this

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

A video tutorial for problem E: https://www.youtube.com/watch?v=pNK352FDaS0

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

https://codeforces.com/contest/1234/submission/73987434 I don't get what I did wrong can someone look at this code and help me.It's 1234B2

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

Can anyone please look at my submission of D -> (75041571). I have basically boiled it down to the code provided by vovuh in the editorial. It's still getting TLE. Any help would be appreciated.

Thanks!

EDIT: I have found the problem. Please check this 75047705. The for (auto x: v) loop gives TLE and for (int i = 0; i < 26; i++) does not. I don't understand. I have initialised the size of the vector to be 26 already.

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

In this problem 1234B2 - Social Network (hard version) i tried using deque instead of queue as i saw in the solution. Here is my solution to the question 76456403. But i am getting TLE over here? Is the time needed for deque more than queue? And i was using an unordered_set. If u could help me with what needs to be done to avoid this TLE.

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

Problem A should had to be explained more clearly and easily with notes

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

For problem D, I used the same approach as given in the editorial but still got TLE. Please help.

Submission link:- https://codeforces.com/contest/1234/submission/86257137

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

Did Problem E, With segment tree lazy propagation Solution 88938957. For detailed explanation comment below.

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

can anyone help me out with the soln of qn 1234B2. Time Complexity of the soln is O(n logK ). still it is failing on Test 10. 1234B2 - Social Network (hard version). I have included the main code.

int main() { ll n, k, id, i ; cin>>n>>k;

ll arr[n];

deque dq ;

deque :: iterator it;

for(i=0;i<n;i++) cin>>arr[i];

for(i=0;i<n;i++) { it =find(dq.begin(), dq.end(), arr[i]);

if(it == dq.end()) { if(dq.size() == k) { dq.pop_back(); dq.push_front(arr[i]); }

else
{
    dq.push_front(arr[i]);
}

} }

cout<<dq.size()<<endl;

for(ll v : dq) { cout<<v<<" "; }

return 0; }