guptaji30's blog

By guptaji30, history, 3 years ago, In English

there are 3 types of queries

0 X add a number X, 1 X remove the number X (X always exist), 2 X return the number of subsets that sum to X,

0<=X<=10^3 0<=number of queries <=10^3

I tried to implement this using the knapsack approach but its bound to give TLE

any suggestions? Any help would be appreciated

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

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

I am a bit confused regarding the time complexity here.

X <= 1000, and number of elements is also at-max 1000.

In the worst case, assume 1 insertion and then 1 subset query alternating one after another.

500 subset queries and for each query you'll need O(N*|X|) operations. So the total operation turns out to be around 500*500*1000 ≈ 2.5e8 operations? Maybe brute forcing using knapsack won't give TLE.

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

I think its very common to add in knapsack in O(size), similarly we can delete from knapsack also in O(size).

Code

Note that the addition part is quite easy, and the subtraction also works the same way(it is clear that the order doesn't matter when we add in the knapsack, intutively you can assume that the last element added was the one to be deleted and try to think how would you undo it).

Hope it helps.

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

    This is not correct according to me, we have to calculate number of ways to get sum = X. we cannot undo on knapsack. because number of ways are construct on top of past states, how can we update that.

    Just curious, with no offense to author as i might also be wrong, do people just upvote anything coming from high rated people or they actually even read the approach and then upvote.

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

      No offense, just run a stress test using brute force approach(knapsack with every query) and then do report.

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

        if that was possible , we can solve this question easily without two stack approach or divide and conquer which is another method to solve this, so i guess that approach is wrong.

        link to codeforces edu two pointer problem

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

          Order matter while adding or deleting in the problem you mention in link that's not the case here !!

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

            wait to be clear this are not stack like update, like add X,remove X , X could be anything, so its random deletion.

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

            This approach will work here.

            AC Code

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it -20 Vote: I do not like it

    I found another flaw in this lets say you are adding 1000 merely 100 times in state, now when the total sum gets around 10^5, and now you have to maintain all those sums, so that when you start removing 1000 again, it does not mess up with your answer. so even if its correct it might not be feasible for the time complexity.
    we could get around with it some kind of sparse sum states, might not be feasible tho.

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

      Just look at the editorial of 1111D - Destroy the Colony.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 4   Vote: I like it -19 Vote: I do not like it

        but we need to maintain more than 10^5 sum right instead of 1000, as i said above, or am i wrong here. because lets say upto some prefix of queries your sum is 1200 and i remove 200, and ask you how many are possible with 1000 sum, so it will still contribute to the answer.so maintaining only upto 1000 is not correct.

        Also thanks for the problem learnt quite a lot, now i get to know operations are reversible

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

      navneet.h if you notice X<=1000 so we need not store or calculate dp states above 1000 as all the queries of type 2 are of form '2 X'. Feel free to correct me.

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

        If you see mathematically or from the code, it seems that it's not needed more than 1000 size but I am not getting intuition why only 1000 states are needed.

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

          In each of the dp states we are trying to calculate the number of subsets that can be formed with sum being X. And the answer to dp[X] only depends on some dp states for which the sum is less than X. So all dp states for which sum is greater than 1000 are useless as at the end of the day none of them will ever be queried. So why to calculate them? Compute only things which maybe queried in future.

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

We could solve this in $$$ Q * X * sqrt(Q)$$$ with square root decomposition, i already explained this on our group to someone. Hope at that time it was not live.

So basically you can decompose array into square root buckets or now when you remove the element, you can recalculate the current knapsack bucket, as you know the all the element in square root bucket. this will handle for the update part. Complexity of update is $$$ X * sqrt(Q)$$$ , as there will be only sqrt elements

Now for the query part you know the knapsack states, so you can iterate on square root buckets to get number of ways to get sum = X, complexity will be same $$$ X * sqrt(Q)$$$, for finding the ways part to get sum = X, on first two buckets its just $$$ \sum _{i = 0} ^{ i = X} ways1[i] * ways2[X-i] $$$, similary you can keep combining those buckets and after this remaining atmost square root element, can be added in this in same way as we did in update.



Another way is kind of FFT and segtree, i am not sure about this approach, but we can build convolution tree, someway, i will think this in more detail and write the answer.

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

    imagine people downvoting just because it had some downvotes before and not reading the approach,lol
    this is also one way to solve this question also feasible btw.
    The most funny thing is above i made same comment one is getting upvoted and one is downvoted, what kind of people are on codeforces, anyways, no wonder i have stopped caring about downvotes.

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

I think knapsack is the way to go. Because the third type of queries only ask for subset sums of $$$X<=10^3$$$, we only need the knapsack DP array to be of length 1001. Say we have calculated the DP array for some numbers, then it's easy to calculate a new DP array in $$$O(maxX)$$$, extending the set of numbers by adding number X (query type add). Remove queries make it harder. We can use offline deletion from datastructure only supporting insertion and a stack of DP arrays to answer all the queries offline, and support delete. This only costs an extra log factor, and would give a runtime of $$$O(maxX*Q*log(Q))$$$

Edit: Oh, removing is just as easy as adding, because instead of adding, we know subtract all DP transitions. My approach could still be useful for queries of the form: Is a subset sum of X possible?

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

    you could use number of ways to check if possible or not, like creating a array with subset sum = p * mod,p is whole number. have less probability of failing for random mod and when you randomise more by using more number of mods, chances of failing is even less, for reference you could see code of my friend above for the codeforces edu problem.

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

What is goc33?

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

You didn't write the correct constraints. The actual constraints were 7*1e3 for both 'X' and the queries. That is surely going to make a difference right?

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

    Not in this case, the solution still would be O(queries * range(x))

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

      But how? like this guy said. https://mirror.codeforces.com/blog/entry/92845?#comment-816270 change 500 to 3500 now and 1000 to 7000. This should surely give TLE now. 3500 * 3500 * 7000

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

        As far as I understand this problem, there are 3 types of queries: insert, delete and number of subsets. Now let's analyse the time taken by each one:

        1) Insert: you just need a for loop of size O(range(X)) (using the knapsack approach)

        2) Delete: this query takes same time as Insert, just we would have to use incremental loop than a decremental one.

        3) Number of subsets: this would run in O(1) time, as you just have to return a direct array entry!

        So worst case complexity = O(Queries * max(X))

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

Would it be possible for you to share the first question of your test as well?? It would really help!!

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

    There were a lot of different questions so I will share mine.

    Q1: given an array with n elements, and Q queries consisting of an integer find whether there exists an element in the array such that it's bitwise and is zero

    1<=n<10^5 , 1<=q<10^5

    Q2: Given a binary string, find the number of subsequences with unique values when converted to base10 number.

    1<=l<10^5

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

      How to solve Q2?

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

        BlueTulpis Do you get it? I don't understand what are they asking

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

          If string="101", then count subsequence which in decimal representation are unique

          Here

          we have

          0,1,10,101,11

          so anwer=5

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

            UPD — I hope this will work

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

              I think this is incorrect, for string="110011", it gives 37, while the answer is 17.

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

              i think this will also take the subsequences which starts with 0 like 01 but in base10 representation 01 is same as 1.

              So our final ans must be dp[n]-1-distinct subsequences starting with 0(except '0')

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

              Can you explain the code

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

      Can you please tell range of ai in Q1?

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

        I have seen this question before the range of ai is also in the same range as n. The question can be solved using SOS DP. By implementing it, the code becomes really short and is easy to understand. If you want, I can share my code here.

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

          Ohh yes I got it. Range of ai was most important part of the problem :).

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

      .

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

        I think you will TLE, as at each node you will have more than one path which may potentially contain answer. num & x = 0 them there are many num which satisfy this. Searching for all of them will give you TLE.

        Feel free to correct me.

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

Its addition and deletion on knapsack, I saw this idea here IZho017 bootfall