RomeoFantastik's blog

Very interesting, but hard problem
By RomeoFantastik, history, 9 years ago, In English

Hello guys! Like I have done before, I want to propose you a nice problem form main.edu.pl I am stuck at it, but I think it's good for training yourself. http://main.edu.pl/en/archive/pa/2010/cuk If you have good ideas, please share it here. :D

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

»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

hint: meet in the middle technique in O(3n / 2 × poly(n))

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think meet in the middle should work fine here. Also, if I remember correctly a whole bunch of approaches to this question have been discussed in the pdf preview for "Looking for a challenge" which is available online for free on the official site.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've been trying to submit a solution for like an hour, but I get Runtime Error for all the cases except the very small ones.

I checked my solution locally and it works, and it doesn't exceed the 128MB memory limit. I use a pair<ll,int> array of size 2M, so it's roughly 24MB, which is very far from the memory limit. I don't know what else to try.

Anyone else experiencing problems with that site judge?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

I have a nice solution.

Try all possible assignments for the first half of the sweets. Let a, b and c be the number of sweets each person gets. We'll assume that the requirement is a ≥ b ≥ c. Let a', b' and c' be the respective values for the second half (we'll get to it later), so if we're gonna use this assignment in the first half, we're gonna need a' - b' ≥ b - a and b' - c' ≥ c - b. Ok, let' store the values b - a, c - b and a - c of every assignment in the first half for later use. Now, let's move on to the second half.

In the second half, try every possible assignment too, we have values a', b' and c'. As we said earlier, we'll need to find out of all the triplets in the first half, the minimum a - c such that a' - b' ≥ b - a and b' - c' ≥ c - b.

Now, let's transform the problem. Let's think of the triplets in the second half as points in the plane (a' - b', b' - c') with an assigned value of a' - c', and triplets in the first half as rectangles in the plane from coordinates (b - a, c - b) to (∞, ∞) with a value of a - c. Then, for every point, we're looking for the rectangle with minimum value that it belongs to. We can do a sweep line algorithm by increasing x coordinate supported by a BIT for RMQ (rectangles come before points in case of a tie in x coordinate). Whenever we come across a rectangle with lower left corner (x, y) and value v, we update our BIT from position y to position MAX with value v. And when we come across a point at (x, y) with value v, we query the BIT in the range (1, y) for the minimum element m and update our answer to v + m in case it's better than what we already have.

The overall complexity of this solution is O(3n / 2 * log3n / 2), I think.

UPDATE: Since the judge is not working, I tested it locally after downloading the tests from the site and it works under 2 second for all test cases.

→ Reply