### kipawa's blog

By kipawa, history, 3 years ago, ,

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!

• 0

By kipawa, history, 4 years ago, ,

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.
My code

• 0

By kipawa, history, 4 years ago, ,

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)