shoya's blog

By shoya, history, 5 years ago, In English

Lets say there is initially an empty array and we have to preform Q number of queries of 3 types :-
1. x, add x in the array.
2. x, delete one occurrence of x from the array if exists.
3. L R, print the count of integers present in the array in the range [L, R].

Constraints :-
- 1 <= Q <= 1e5
- L <= R
- 1 <= x, L, R <= 1e5 (small)
- 1 <= x, L, R <= 1e9 (large)

One solution that came to my mind for small constraints is to use segment tree on the range [1,1e5] with time complexity O(Q*log(1e5)) with space complexity of O(1e5). But that solution wouldn't work for large constraints.

Is there another way to solve this problem which doesn't use segtree ? Can we use c++ STL here ? Please suggest your techniques.

Also another variation to the same problem can be :-
Lets say there is initially an empty array and we have to preform Q number of queries of 3 types :-
1. x, add x in the array.
2. x, delete one occurrence of x from the array if exists.
3. x, print the count of integers present in the array greater/smaller than x.

Full text and comments »

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

By shoya, history, 5 years ago, In English

Consider initially an empty set and there are two types of queries:-
1) Given x, insert integer x in the set.
2) Given x, get the max integer y in the current set such that y<=x.

For Example :-
Suppose after several type 1 queries our set is {3,1,-14,1,5}.
Now type 2 comes with x=6 then answer would be 5.
Now type 1 comes with x=6 then set becomes {3,1,-14,1,5,6}.
Now type 2 comes with x=8 then answer would be 6.

How can we solve this problem without using policy based data structure ?

Full text and comments »

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

By shoya, history, 5 years ago, In English

Which IDE/Editor do you use and what do you like about it? How do you test for sample tests of the problem fast? Do you use terminal during contest? Also how do you debug your code during contest? Do you use IDE Debugger or debug manually?

Full text and comments »

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

By shoya, history, 5 years ago, In English

Hello everyone,.
Can you suggest some problemset or an online judge whose problems are worth solving and you get to learn a great deal. I know codeforces is among the topmost judges but as there are like zillion of problems out there you can't solve them all. I want to know from div1 people what do they think which problems or which online judge benefited them the most in their CP path.
Thanks

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By shoya, history, 5 years ago, In English

Hello everyone,
I'm creating this blog post to know about the problems that you once solved and thought to yourself Man I feel amazing after solving this problem. If you remember those favourite problems or you know some problems which requires amazing concepts to learn and you were in awe of the beauty of the problem then post their link in the comments and share them with us.The problem need not be necessarily from codeforces it could be from any judge.

Full text and comments »

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

By shoya, history, 5 years ago, In English

Problem link

Here is my approach :
- Calculate All pairs shortest distance using floyd Warshall for every pair of cell.
- Then dp[subset] = optimal answer for this subset.
- For each tyger u subset try to connect that with this subset in minimal way using pre-calculated shortest distances such that dp[subset u] = dp[subset] + min_dis.
- At last take sum for all subsets.

But this gives wrong answer. Please help.
Can someone tell me the approach to solve this problem ?

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it