## Search found 53 matches

Sun Feb 13, 2005 7:18 pm
Forum: Algorithms
Topic: Special case of Hamiltonian cycle
Replies: 4
Views: 1486
Got AC, sad that I can't come up with trics like this.
Sun Feb 13, 2005 4:01 pm
Forum: Algorithms
Topic: Special case of Hamiltonian cycle
Replies: 4
Views: 1486
Wow! You are everywhere! Great!
Thanks for the link, if by V you mean the number of vertices, than the ALGO looks pretty much like the one everybody has used.
10k u very much!
Sun Feb 13, 2005 9:47 am
Forum: Algorithms
Topic: Special case of Hamiltonian cycle
Replies: 4
Views: 1486

### Special case of Hamiltonian cycle

I need help with: http://acm.sgu.ru/problem.php?contest=0&problem=122 If you don't want to open it, the problem is: You have an undirected graph with N vertices. Each vertex has at least (N+1)/2 neighbours. Needed is to construct a hamiltonian cycle. I guess it is assumed that it always exists. I he...
Thu Jan 06, 2005 9:52 am
Forum: Algorithms
Topic: Exact matching subimages
Replies: 5
Views: 1504
Thank you so much! I didn't find no errors in your algo. Besides, task H is qiute interesting by itself. Perhaps I ll have to look for good techniques of guessing values for (x2-x1) and (y2-y1)... I realize that I can't solve this problem strictly, but I could dig for a suboptimal solution... Again,...
Tue Jan 04, 2005 2:58 pm
Forum: Algorithms
Topic: Exact matching subimages
Replies: 5
Views: 1504
Probleb: Help the dumb Russian Time Limit: ASAP We have two matrices A and B with dimensions (W1,H1) and (W2,H2) respectively. You need to find six numbers x1,y1,x2,y2,w,h such that A(i,j) = B(k,l) for each i=x1..x1+w-1 for each j=y1..y1+h-1 for each k=x2..x2+w-1 for each l=y2..y2+h-1, such that the...
Tue Jan 04, 2005 11:45 am
Forum: Algorithms
Topic: Exact matching subimages
Replies: 5
Views: 1504

### Exact matching subimages

Hi! I have a practical task and I need some pointers on that. Imagine we have two raster images (let it be .BMP). Let's say they are big, about 1000x1000x32bit. I need to find their largest common subimage. And I am not interested in subimages smaller than, let's say 50x50. I decided that computing ...
Sun Oct 17, 2004 3:12 pm
Forum: Volume 107 (10700-10799)
Topic: 10746 - Crime Wave - The Sequel
Replies: 27
Views: 17585
Well I never really gave this idea a deep thought, but if we add M-N banks such that everyone gets to them in no time than we can use Hungarian Method here. And it runs under N^4... Ain't I right?
Sun Oct 17, 2004 2:55 pm
Forum: Volume 107 (10700-10799)
Topic: 10746 - Crime Wave - The Sequel
Replies: 27
Views: 17585

### 10746 - Crime Wave - The Sequel

:-? Help me people! Its the dumb russian again. I used DP for this problem. I stored situations in structures like this: nBank : integer; // Current bank that we re trying to save PartolsMask : a bit vector of length M, indicating which police patrols went to the banks At first I had one situation n...
Mon Sep 20, 2004 4:08 pm
Forum: Volume 107 (10700-10799)
Topic: 10709 - Intersection is Not that Easy
Replies: 41
Views: 9407
Hah... Per's post seems really helpful 8-))))
Check out this test :
LS LS
0 0 1 0 // segm 1
2 2 2 -2 // segm 2

and this one too
LS LS
0 0 1 0
2 1 3 1
Mon Sep 20, 2004 4:03 pm
Forum: Volume 107 (10700-10799)
Topic: 10707 - 2D-Nim
Replies: 15
Views: 21055
Yep, I already have a variant like that. And it looks pretty good!
Wed Sep 15, 2004 5:29 pm
Forum: Volume 107 (10700-10799)
Topic: 10704 - Traffic!
Replies: 15
Views: 8873
For me, only this case is worth mentioning
1
0 4
0
0
0
0

Sat Sep 04, 2004 6:19 pm
Forum: Volume 107 (10700-10799)
Topic: 10707 - 2D-Nim
Replies: 15
Views: 21055
YES! Absolutely the same here. My trouble is mostly about sorting components and the points in them. For this purpose I wrote 2 different sorting function, and I never use nothing but mergesort. I dont know of any good pascal built-in sorting procedures. Other than that, I also decreased all the coo...
Fri Sep 03, 2004 3:07 pm
Forum: Volume 107 (10700-10799)
Topic: 10707 - 2D-Nim
Replies: 15
Views: 21055

### 10707 - 2D-Nim

Well I solved it. But I didn't enjoy it at all. My pascal solution is 200+ lines and over 5KB in size. I wan't smaller programs, preferably in Pascal. If your program is AC and under 2KB or so, please leave it here as a private message or send it to caa<commercial_at>academ.tsc.ru Thanks to everyone...
Thu Sep 02, 2004 9:01 am
Forum: Volume 107 (10700-10799)
Topic: 10704 - Traffic!
Replies: 15
Views: 8873
Well in my tree the height is always equal to the number of blocks (if we measure the height in edges).
Tue Aug 31, 2004 8:30 am
Forum: Volume 107 (10700-10799)
Topic: 10704 - Traffic!
Replies: 15
Views: 8873
No I never proved an upper bound. When I think of a 6x6 field I just don't believe that there is A WHOLE LOT of possible situations. But since you asked me about it and its an interesting question, let's put it this way: 1. there are 12 lines in total, vertical and horizontal. 2. we can put 1 block ...