kipawa's blog

By kipawa, history, 7 years ago, In English

I am currently trying the following problem.
I have some thoughts for solution but I am unable to solve it completely.
My thoughts are as follows — If we have a pattern like a*b, then if the first occurrence of 'a' in string t is at index i and the last occurrence of 'b' in string t is at index j. Then our answer will be the number of distinct subsequences of the string t(i,j). Here t(i,j) means the substring of string t from index i to index j.

But the problem is that I am unable to think of a general solution. I am also not able to find any editorials. Please help me!

Full text and comments »

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

By kipawa, history, 8 years ago, In English

I was trying out the problem Destroying Roads. I am getting WA on test 16 but I cannot figure out whats wrong with my logic. Please help me out
I am searching for any node i such that distance from s1 to t1 through i is feasible, i.e dis[s1][i]+dis[i][t1]<=l1 and dis[s2][i]+dis[i][t2]<=l2.
Now once I get any such 'i', I try to figure out the value of i such that above condition holds and the the distance from s1 to t1 via i and from s2 to t2 via i is minimum.
To calculate that distance, I construct the shortest path tree with source as 'i' and then I calculate the above value via O(n) lca algorithm, i.e once the shortest path tree is created, I traverse from s1 to t1 keeping only that edges and from s2 to t2 keeping only that edges and deleting the other edges.
I tried many test cases and my code is working fine, but its giving WA on test 16, answer is 2942 but my code is giving 2941.
Please help me out!
My code
Thanks in advance!

Full text and comments »

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

By kipawa, history, 9 years ago, In English

I was solving problem 279C (Ladders)
My logic is to create two arrays inc and dec
inc[i] contains the largest j, such that i<=j and the sequence from ai, ai+1, ..., aj is increasing.
dec[i] contains minimum j, such that i>=j and the sequence from aj, aj+1, ..., ai is decreasing.
Now the sequence l,r is ladder if inc[l-1]==dec[r-1] || inc[l-1]>=r-1 || dec[r-1]<=l-1 (I used 0 based indexing)
I am getting WA on test 20, please help me!
Solution Link
Thanks in advance!

Full text and comments »

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