I_love_Chris_Evans's blog

By I_love_Chris_Evans, history, 6 hours ago, In English,

Have you ever regretted your permanent/semi-permanent username?

Read more »

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

By I_love_Chris_Evans, history, 3 days ago, In English,

problem
submission

My logic:
1. Check if the query can be satisfied completely with just one segment.
2. Sort segments first based on increasing left endpoint and then based on decreasing right end point. Traverse the sorted segments from left to right. Remove unnecessary segments. Each segment that remains must be the longest segment connecting the previously connected segments, going as far right as possible. Therefore, any three consecutive segments A, B, C which are remaining should not satisfy ((A union C) intersect B) == B.
3. Sort the trimmed array based on increasing right endpoint, and then based on increasing left endpoint.
4. Use lower_bound to find the first and last segment in the trimmed array corresponding to left and right ends of the query, and check one segment to the right from the first segment (the one we found for the left endpoint).
5. Check if the segments found are valid, and print the outcome.

Can anyone help me find the reason for WA?
Thanks!

Edit: Nvm, found a test case
segments : [1, 4] [2, 6] [3, 8] [5, 9] [7, 10]
queries : [2, 9]
Correct answer is 2, I'm printing 3 because I removed the needed segments.

Read more »

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

By I_love_Chris_Evans, history, 11 days ago, In English,

problem statement
my solution

I just can't figure out why TLE. Complexity seems to be $$$n^{2}logn$$$. Please help.

Read more »

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

By I_love_Chris_Evans, history, 8 months ago, In English,

There's an array A of N elements. You don't know the element values, but you do know that each of them is a power of 2. You are given xor of some segments of this array, and your task is to determine one valid array, which satisfies all the segment xor.

eg: N = 6, segments = 3
xor: [1, 2] = 3, [2, 3] = 0, [3, 6] = 12
one valid value of A is [1, 2, 2, 8, 2, 4].

Read more »

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

By I_love_Chris_Evans, history, 9 months ago, In English,

Hello everyone!

Can anyone please help me with this problem : Given a graph with positive weighted edges, how to choose a subset of edges with maximum sum such that no two edges share a common vertex?

This wasn't taken from any judge, I'm just interested in knowing how it can be solved. As it's not from any judge, there are no constraints except what I already mentioned above.

Thanks!

Read more »

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

By I_love_Chris_Evans, history, 10 months ago, In English,

If anyone's looking for a teammate, please let me know. Female participants preferred(as then we have all girls team). No restriction on ratings :)

Thanks!

PS: Requesting to not spam in comments.

Read more »

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