water's blog

By water, 11 years ago, In English

My rating is just 1453 but I still wanner write my own tutorial to share with you.

A. 252A - Little Xor This is a simple problem. We can write a algorithm using brute force. The complexity of it is O(n^3). My code 2713341.

B.252B - Unsorting Array This is a greedy problem. There are several special cases: 1. There is only one or two interger. Answer is "-1". 2. There are three interger and they are placed like "1 2 1" or "2 1 2", whatever you do you will make an sorted array. 3. All the numbers are the same so we can't make any operation. 4. Here are other cases: We find the first unequal pair searching from the head of the array, then we swap them. We will get the unsorted array unless what happen below: The pair are the first two numbers and the second is the max number or the min number. So we just search the unequal pair from the trail and swap them then we will get the right answer.The complexity of it is O(n). My code 2714096

C.251A - Points on Line This is a DP problem. We user two pointers and one points to the left most interger and the other points to the right most interger.For every left points we need find out the right most interger, then we just calculate C(r-l+1,2) means we pick up two intergers from the sequences freely. Because the position of the right interger can't decrease so the complexity of it is O(n*2).My code 2704914

These are the problem I solved in the contest. Sorry for my poor English and bad code ability. You may seek the official editorial for more infomation.

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

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

good explanation , tnx :-) but your problem links are incorrect :-??

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can solve C problem, using binary serach (upper_bound function). Here's my code.