Problemset 5

Adrian_Kosowski 2005-01-20 23:02:19 UTC #1

Problemset 5 is now over. You are invited to post any remarks or questions concerning the problems, as well as short descriptions of your accepted solutions.

Adrian_Kuegel 2005-01-20 23:43:20 UTC #2

The smallest area will be bounded by water melons from left,right,top and bottom. Note that they don't have to be at the corners of the rectangle, for example if they are arranged like this:
.X..
...X
X...
..X.
So in my solution, I tried every y-coordinate of a water melon as upper bound. Then I tried lower bounds in steps of 2^i distance from the upper bound. For each such lower bound, I find in O(n) the smallest x-interval such that if I use it as left and right bound, it covers at least k fruit.
Now I check if between the last lower bound and the current lower bound there can be a smallest area (note, that all x-intervals for smaller lower bound will be >= size of current x-interval). If there can be a smallest area, I evaluate recursively in a similar way.
With this strategy, I will skip a lot of non-optimal possibilites. Although the algorithm still looks like O(n^3) in theory, it behaves like O(n^2 log n) on the data set.

Adrian_Kosowski 2005-01-21 01:06:59 UTC #3

Not only that, your approach actually seems to work about twice as fast as the O(n^2 log n) algorithm used by Hieu Nguyen and by the test solution .

(For each possible value y of the length of the vertical side of the rectangle perform a segment-tree-based O(n log n) left-to-right scan: at each point of the set draw a vertical segment of length y with the bottom end at this point and detect the minimum possible length x such that there exists a horizontal segment of length x intersecting at least k-worth of vertical segments associated with the points of the set.)

But really, your algorithm, whatever its complexity may be, is faster for all test cases I've been able to come up with so far .

tomek_sof 2005-01-21 23:00:41 UTC #4

BLOCKS

It was a great problem, thanks!

Theorem 1.

If the blocks in the initial and final positions are same, the puzzle is solvable in 3 steps.

Proof

We will first shuffle columns, then rows, then columns again.

Let's match positions in the initial position with positions in the final position in an arbitrary way, such that the color is same. Therefore, we have n^2 quadruples of numbers:
(x1,y1,x2,y2)
Every (x1,y1) appears exactly once and every (x2,y2) appears exactly once.

We want move the block (x1,y1,x2,y2) via some (x1,y3): (x1,y1) -> (x1,y3) -> (x2,y3) -> (x2,y2), so that all (x1,y3)'s are distinct and all (x2,y3)'s are distinct.

In other words, for each y3 we want to choose n quadruples with distinct x1's and distinct x2's.

Define A[i,j] to be the number of quadruples with x1=i and x2=j. The sum of every row and of every column of this matrix is n. For y3=1, we want to choose n positive elements of this matrix, each from a different row and different column. Then we will subtract 1 from those elements and continue. (in other words, subtract a permutation matrix). In the second step, the sum of each row and column will be (n-1).

It remains to be proven that in a matrix with nonnegative integer entries such that each row and each column sums up to the same (positive) number, we can choose one element in each row and in each column.

This is such an interesting property. It took me a long time to prove it and at some points I was convinced that it is not always possible.

It is not enough that the sum of each row and each column is positive (not equal)! For example:

OK - now why the property is true.

It is an immediate consequence of the Hall's Marriage Theorem. We are matching rows to columns. The theorem states that it is possible to match set A to distinct elements of B iff for each subset S of A, the number of elements matched by S is greater than or equal to |S|.

In our case, choose a subset S of rows. Suppose the sum of each row and column is c. Then, the sum of these rows is |S|*c. The matched columns contain all the positive entries out of these rows, so the sum of these columns must be at least |S|*c, hence there must be at least |S| of them!

QED

Now the algorithm.

From the theorem it is easy to check whether the puzzle is solvable in 3 steps. It is also easy to check if it is solvable in 0 or 1 steps. What remains is to check whether it is solvable in 2 steps, if it is solvable at all (the colors are same).

Suppose we are permuting columns first, and then the rows (then we transpose the inputs and check again).

For each color calculate the set of initial and final positions for that color. We want to match the initial positions (x1,y1) to the final positions (x2,y2) so that all the intermediate squares (x1,y2) are distinct.

If there is just one copy of a color, we just match and mark the square (x1,y2) as used.

Now what happens if there are two copies (that was the most possible) of a color? If the initial positions are in the same column or final positions are in the same row, again there is just one possibility really (mark squares (x1,y2) and (x1,y2') as used).

OK, but we are left with some colors for which there are two options - either mark (x1,y2) and (x1',y2') OR (x1,y2') and (x1',y2) as used.

Now this part of my algorithm was pretty dumb (come on, I was tired) But I don't know if it can be done much better.

For some colors, one (or both) of these options may not be possible, due to the fact that some squares have already been marked. Then we know what to do - choose the other option.

I just do this repeatedly until all the squares in question are unmarked for each of the colors left.

Now guess what I did next.... Hopefully we are left with not so many colors (I guess 0 most of the time), so just brute-force all 2^K possibilities!

tomek_sof 2005-01-21 23:23:33 UTC #5

Maybe because it is not really O(n^2 log n), but O(M n log M), where M is the size of the grid.

My approach is also O(n^3) in the worst case.

For each left and for each right bound of the rectangle I do a top-to-bottom O(n) scan to find the smallest rectangle covering at least K melons (if good, decrease from the top, if not, increase at the bottom).

But first I check if there are more distinct x's or more distinct y's

tomek_sof 2005-01-21 23:34:46 UTC #6

The Modern Dress Code

I view it as a graph coloring problem - no two neighbors should have the same color.

My general idea is taken from what I found in literature as the Hungarian folk algorithm for distributed independent set. I guess I am using a simplistic version of that.

In step K, assign only the color K to vertices. I give each vertex a random priority. An uncolored vertex will assume the color K if its priority is larger than that of any uncolored neighbor.

Then I added some little improvements:
- in the last step, if the vertex is still uncolored, assign a random color greater than K
- in each step also try assigning the color K-1 (it may still be possible), if no neighbor is colored as K and I am the highest priority out of the uncolored neighbors
- also try assigning the color K-2, if no neighbor is colored K-2 and I am the highest priority OUT OF those neighbors who are not colored and have no neighbor colored K-2 (2 steps are needed to convey this information)

Adrian_Kuegel 2005-01-22 00:14:38 UTC #7

First we have to check which paths exists between vertices. If there is at most one path between two vertices, a naive algorithm could just count how often each segment is used and take the maximum of that. But there can be two paths from a vertex to another vertex, one clockwise and one counterclockwise (like in the 2nd sample input). In that case, we have to decide which path should be build in the new waterway. I used a greedy choice here, but I can't prove why it is optimal. My greedy choice is:
take the shortest of the two paths, or if both are equally short, take the clockwise path. It is important that in the case of a tie you break the tie always in the same manner.
So, if this greedy choice is used, we can observe that the cities that should be reached following a clockwise path build an interval, and the same for counterclockwise paths. Now let the interval for clockwise paths be [i, j]. Clearly, all nodes k with iTo determine the interval of nodes for clockwise paths, first ignore if there may be two paths, and just determine how many nodes you can reach clockwise or counterclockwise. This can be done for all nodes in O(n) overall using dfs. After that, apply the greedy choice, making sure that #nodes clockwise + #nodes counterclockwise < n.
Now, choose one segment to start with and determine in O(n) how many nodes have paths passing clockwise through that segment. Store the most distant such node. Then go through the other segments in clockwise order, calculating the number of paths by using the result of the adjacent segment (note, whenever you go to the next segments, the number of paths decreases by k, where k is the number of nodes for the last segment that had paths passing through the segment). Recalculate the most distant node having paths through the current segment.
Do the same thing for counterclockwise direction.

tomek_sof 2005-01-22 00:51:52 UTC #8

My solution has 3 cases:

there is a full cycle both ways - the answer is 1+2+3+...+n/2+...+1, since this is the minimum number of segments each city uses, and there are n segments and n cities, so the average must be at most this (and is achievable)
there is a full cycle just one way - in this case I found out that the length of paths going in the opposite direction are always at most 1 (two connected cities); if there are no edges going in the opposite direction, the answer is n*(n-1)/2, if there is one such edge, the answer is same, if there are two or more, the answer decreases by x-2 (each edge saves 1)
there are no full cycles - in this case I went around the circle, keeping track of how far you can go left and how far you can go right. If you can get somewhere both ways, I brute-forced all possibilities. Now send all the boats you need to send, increasing the numbers on the segments. We need to add an arithmetic sequence, for example 5,4,3,2,1 to the next segments, if the maximum distance we can go is 5.

In order to be able to add an arithetic sequence in constant time to a part of our array, instead of the sequence, we store the second-order difference sequence!

For example:

sequence:
0  4  2  3  2  1
differences:
0  4 -2  1 -1 -1
second order
0  4 -6  3 -2  0

We can add any arithmetic sequence in constant time to any subarray because the second order differences are non-0 in a constant number of places!

0  0  5  4  3  2  1  0  0  0
0  0  5 -1 -1 -1 -1 -1  0  0
0  0  5 -6  0  0  0  0  1  0

tomek_sof 2005-01-22 01:06:02 UTC #9

It is not optimal in general.

For instance, on the test case AAAABBB, I think your algorithm will say 23 while less can be achieved - even by sending all the boats in the same direction you only get 21. It is beneficial to send some boats around the AAAA rather than inside the congested BBB.

tomek_sof 2005-01-22 01:11:17 UTC #10

Or even AAB - it's not good to use the B backwards edge.

Adrian_Kuegel 2005-01-22 01:12:46 UTC #11

You are right, my algorithm gives 23. Thanks for the test case
So I was just lucky to get accepted. Btw, do you also have a "case 3" example where greedy is not optimal?

tomek_sof 2005-01-22 03:49:04 UTC #12

AAAAACBBB

Adrian_Kuegel 2005-01-22 04:40:17 UTC #13

Thanks again
I get 19 with my algorithm, and as far as I see the answer should be 18.

Adrian_Kosowski 2005-01-22 04:40:51 UTC #14

A few general comments:

BLOCKS: I guess not much is left to be said... All I can add is that the 2SAT approach seems to work when solving the 2-permutation case: when given choice, try to apply matching (marking) option 1, recurse into the path of forced no-choice assignments, if this turns out impossible, return to the point of decision and retry with option 2. If option 1 is OK do not retry (after all, if the path of no-choice cannot be continued, it means that none of the unmatched blocks have been affected by the earlier decision in any way).

WMELON: Most of the test data consisted of 1000 points spread throughout the whole square, but this didn't stop the O(n^3) from winning.

WATERWAY: If you want to prove the correctness of some approach , it is probably best to look at two kinds of connections between points: those that can be routed one way, and those which can go both ways around the cycle. If all traffic is of the first kind it is not that hard to come up with a linear time solution. The cases that remain correspond to regexps: B*, [AB]* or [BC], B+ C[BC] B+ A[AB]. For B the answer is (n^2)/4, for [AB]* and [BC]* routing things "the long way" is seldom a good idea (only can only be considered for paths coming from exactly one section of adjacent B-s). Finally in the last case only paths from one group of B-s to the other can be routed both ways. With due patience it is possible to write explicite which of these paths should go which way in different cases, or take the trouble to generalise "an extension of the Okamura-Seymour theorem due to Frank" (which says, roughly, that if there is no traffic of fixed route, the width required is the ceiling of half the maximum of the sum of the number of paths going across exactly one of a given pair of edges of the cycle, taken over all pairs of edges). The test data for all cases requiring routing was small and not very restrictive, so any sensible attempt made was bound to succeed .

Pascal_sof 2005-01-22 08:18:05 UTC #15

You guys got me really crazy on this set...
There I was sitting peacefully at first place, and when you came in, stole me the first place and cracked down problem BLOCKS and WATERWAY, for which I had been working for days without success...

I used exactly the same algo... except I didn't have the proof about 3 being a maximum ! This is why I gave up at the end, because I thought there was a test case requiring 4 moves. In fact, I just discovered a stupid bug this morning in my code when you need only one move (forgot to order the list of y-coordinates in case of column shuffling, this was always working for row shuffling due to the order of input). Just corrected it and it got accepted.
This is kinda frustrating...

Pascal_sof 2005-01-22 08:24:39 UTC #16

I used a different scheme, borrowed from an article from Lukasz Kuszner, the one who proposed the problem (strange coincidence isn't it ? )

the current state is kept in one variable (using some restricted range of values, and hoping we will never start with those)
priority is defined as deg*10000 + rnd(10000), and kept in another variable
each time a vertex as higher priority than its neighbours, it is assigned a color, which is the minimal color not assigned to any of its neighbours

I also discovered that initializing each vertex with rnd(nr), and then changing it to rnd(maxc+2) as long as Eceq(color) is true, was giving good results. That's why in my algo I switch to this code when the number of days left is getting small.

Matiea87 2009-06-23 05:43:58 UTC #17

Witam wszystkich mam taki oto kod:

#include <iostream>
using namespace std;
//-------------------------------
int main()
{
	int n,t,silnia = 1;
	cin >> t;
	while (t)
   {
		cin >> n;
		for (int i = 1; i <= n; i++)
		silnia *= i;		
		cout << (silnia % 100) / 10 << " " << silnia % 10 << endl;
		--t;
   }
   system ("pause");
   return 0;
}

Wszystko u mnie działa ale jak wrzucam na serwis to cały czas pisze, że Przekroczono limit czasu. Mógłbym mi ktoś pomóc bo już skończyły mi sie pomysły jak to zmienić.

TU_RU 2009-06-23 08:17:31 UTC #18

Nie dziw sie ze masz TLE. Gorzej już się tego nie da napisać . Po pierwsze liczysz tą silnię a wcale nie trzeba .....
SPOJ to konkurs, który ma na celu sprawdzać umiejętność pisania wydajnego i szybkiego kodu a nie tylko takiego który działa.
Pozdrawiam

wiktor2093 2009-06-23 20:00:38 UTC #19

o ile dobrze pamiętam to wystarczy sobie rozpisać silnię chyba dla liczb 1-15 i coś zauważyć

narbej 2012-01-11 11:40:55 UTC #20

Nigdy nie pisałem ani nie próbowałem pisać c#, ale niezależnie od użytego języka:
1. Nie trzeba tablicować danych wejściowych, można je naprzemiennie wczytywać i od razu drukować wynik dla wczytanej liczby.
2. Nie musisz sprawdzać czy danych jest wiecej niż 30 - jakaś mała dawka zaufania do autora zadania;-), że tak jest
3. Jeżeli w zadaniu podany jest zakres liczby to też [zaufaj autorowi, że tak może być] a u ciebie ... używasz int16 tak mi się przynajmniej wydaje [convert.to.int16] ale czy to na pewno wystarczy? int16 =~ 2^16 == 65 536 lub może nawet tylko +- 32768 ?
......
nie wiem czy teraz już będzie bez NZEC - spróbuj