iceman91's blog

By iceman91, 12 years ago, In English

I am trying to solve this problem. In this problem we have to reassign the scores such that they are possible and the absolute difference between original scores and the new scores is minimized. Now for assigning possible scores, I can construct a bipartite graph (X,Y) where nodes in X correspond to all the matches that are going to take place and nodes in Y correspond to all the team that are participating. There is an egde (x,y) iff y is one of the teams participating in match x. Finding maximum flow in this network gives me an optimal assignment. But how do I deal with the constraint of minimizing the absolute difference in this kind of network? If I am wrong with my approach, please do correct me.

Full text and comments »

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

By iceman91, 12 years ago, In English

I am trying to solve this problem. My idea so far is to compute what is the probability of each item on a particular shelf being tasted. But since the number of pots on a shelf could reach 10^5, this approach doesn't seem feasible. Since I couldn't find the editorial for this problem, I would really appreciate if someone could point me in the right direction.

Full text and comments »

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

By iceman91, 12 years ago, In English

Here is the link to the problem and here is the link to my solution. I am using a disjoint set data structure to store 2 kinds of elements x and !x. If x and y are in the same set then they have the same type. If !x and y are in same set then x can eat y. I keep getting WA. Does anybody has any idea about this?

Full text and comments »

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

By iceman91, 12 years ago, In English

I tried solving the problem using segment trees but I am getting runtime error on submission. My code is available here. I analyzed all the array sizes but they seem correct. Any ideas as to why it is producing runtime error?
Update
The problem with solution is size of the array tree. On careful inspection it can be seen that the maximum index of the array accessible is 2*(2*n+1) where n is the maximum size of the input. To prevent that we can either increase the size of the array to 4*n or put a check that it never exceeeds the maximum limit size.

Full text and comments »

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

By iceman91, 12 years ago, In English

I am trying to solve a seemingly standard segment tree problem. The problem can be found here . I came up with a solution to the problem using square root decomposition. Though the complexity of the solution is enough to pass the time limit but the tutorial describes the solution using segment trees. It talks about constructing 3 segment trees.
- First segment tree stores at any given node how many numbers are divisible by 3 in the corresponding range.
For e.g.

Consider an array of 4 integers [0 0 0 0]
1. Increment every number in range 0-3 by 1
2. Increment every number in range 0-1 by 1
3. Increment every number in range 0-2 by 1
At this stage node corresponding to range 0-3 should store 0 because addition of 1 to the whole
range leaves no number divisible by 3. 
  • Second segment tree stores how many numbers leave a remainder 1 on division by 3.
    In the above example, node corresponding to range 0-3 would store 4.
  • Stores the quantity added to a particular range only.
    In the above example, node corresponding to range 0-3 would store 1.
    I couldn't understand how to update the tree1 and tree2 on increment operation?

Full text and comments »

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

By iceman91, 12 years ago, In English

I tried solving Problem D during Practice using the method described in tutorial. But I keep getting runtime error. Is there a way to determine which runtime error my code is encountering or probably what's wrong with my solution? Here is a link to my submission.

Full text and comments »

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