help with one "usaco hard problem" ... please.....

Let's talk about algorithms!

Moderator: Board moderators

arabiukas
New poster
Posts: 2
Joined: Fri Mar 21, 2003 11:03 am

help with one "usaco hard problem" ... please.....

Post by arabiukas »

{2003 03 21}
I copied problem text... please help.... I don't know how to do it....

{**}
Farmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed the posts, but he's having a problem with the rails. The local lumber store has dropped off boards of varying lengths; Farmer John must create as many of the rails he needs from the supplied boards.

Of course, Farmer John can cut the boards, so a 9 foot board can be cut into a 5 foot rail and a 4 foot rail (or three 3 foot rails, etc.). Farmer John has an `ideal saw', so ignore the `kerf' (distance lost during sawing); presume that perfect cuts can be made.

The lengths required for the rails might or might not include duplicates (e.g., a three foot rail and also another three foot rail might both be required). There is no need to manufacture more rails (or more of any kind of rail) than called for the list of required rails.

PROGRAM NAME: fence8
INPUT FORMAT
Line 1: N (1 <= N <= 50), the number of boards
Line 2..N+1: N lines, each containing a single integer that represents the length of one supplied board
Line N+2: R (1 <= R <= 1023), the number of rails
Line N+3..N+R+1: R lines, each containing a single integer
(1 <= ri <= 128) that represents the length of a single required fence rail

SAMPLE INPUT (file fence8.in)
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

OUTPUT FORMAT
A single integer on a line that is the total number of fence rails that can be cut from the supplied boards. Of course, it might not be possible to cut all the possible rails from the given boards.
SAMPLE OUTPUT (file fence8.out)
7
{***}
thank you....

Enslaver
New poster
Posts: 1
Joined: Tue Apr 08, 2003 6:38 pm

Fence rails is a NP complete problem

Post by Enslaver »

You cannot optimally solve this problem, therefore you have to optimize again and again and hope to get the best solution in the time limit. I could give you the official solution .. i'm at 1.5.4 now. :)

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

Post by Lars Hellsten »

I just recently solved this one. It's definitely one of the most difficult (computationally) contest problems I've seen.

It actually is possible to solve optimally, at least, with the test data that's given. But the advice about it being NP complete is good. Don't waste your time looking for a dynamic programming or greedy solution, because there are none. The only way to solve it is with a search. You just have to be a little clever and prune down the search space.

Here are a few hints... hopefully they'll help without giving too much away.

Hint #1: If you can cut K rails, you can cut the K shortest rails.

Hint #2: Remember DFSID? It comes in handy on searches with a potentially deep tree. (Although the training material mentions iterative deepening very early on, this was the first USACO problem where I actually used it.)

Hint #3: To make your tree deep with lower branching factor, try satisfying the most constrained variables first.

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

Post by Lars Hellsten »

Hint #4: There are only 128 possible rail lengths. This means that for the larger inputs you are going to have many duplicates.

BTW, my solution runs in less than 0.5s on all the test cases. :D

Asif
New poster
Posts: 4
Joined: Thu Mar 06, 2003 12:19 pm

Post by Asif »

Thanks for the hints. But I don't understand how I can use the observation that there are repeatations of the values. Please help.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin »

I just solved this problem, after having some problems. Finally I scrapped everything and rewrote a very short & simple solution... which passed all test cases in < 0.02 seconds :-)

1) Keep track of the number of rails of each size, like railcnt[x] = how many rails of size x do we want?

2) Instead of DFSID, I use binary search. If there are 20 fence rails, first I do an exhaustive search for "is it possible to get the 10 smallest rails". if yes, then i try 15.

3) If you try to get the x smallest rails, you first calculate how much you can "throw away" from each board. In the exhaustive search, we first try using as much as possible of the smallest board (starting with the biggest rails). If we decided to move on to board 1, update the waste (we will never go back to board 0 again)

Hmm not sure how to explain it better, the code is really short.

Asif
New poster
Posts: 4
Joined: Thu Mar 06, 2003 12:19 pm

Post by Asif »

Can you please explain point no. (3) more? Thanks.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin »

Assume that we're only interesting in finding out whether we can cut out _exactly_ x rails (the x smallest) from the board. Let totboard = sum of all board lengths and railtot = sum of the x smallest rails. We can thus at most waste totboard-railtot of the boards.

We sort the boards and rails in increasing order. The search function starts working with the smallest board. It loops from the longest remaining rail (again, we're only considering the x smallest rails, forget about the rest). For every rail we either try to use it (make a recursive call, updating how long the current board is and which rails we have left) or we don't use it (keep looping). If we recurse, start checking rails of the same length as the last one used. After all, using rail 5 then rail 3 is same as rail 3 and rail 5.

At the end of the recursive function, we must also consider skipping the remaining part of the current board. If so, we call the recursive function to work on the next board, starting with the longest rail, and updating how much we have wasted so far. If the waste ever exceed the maximum amount of waste, backtrack.

The header of my recursive function (which uses some globals to keep track of board size and remaining rails) is this:

bool search(int curboard, int lastrail, int wasteleft)
{
}

Where curboard is which board we're currently "working" on chopping up, lastrail is the size of the last rail we chopped from this board (or 128, highest possible rail size if none has been cut so far) and wasteleft is how much more we can afford to waste if we are to find a solution.

It's easier to keep track of the rails having a railcnt array, telling how many rails of each size we have. Note that this array should only include the x smallest rails!! So before the start of search, update railcnt to only include the x smallest rails.

Outside _ALL_ of this we have a binary search for x.

Asif
New poster
Posts: 4
Joined: Thu Mar 06, 2003 12:19 pm

Post by Asif »

Thank you so much.

HQH
New poster
Posts: 1
Joined: Sun Jun 15, 2003 5:50 pm

Help with contact

Post by HQH »

Hi, im with flood fill Algorithms at usaco.


I have a problem in 1.2.1, with problem "contact" and "Shaping Regions"(10 of 11 cases), i dont know how to apply the flood fill Algorithms to him.

Can someone help me or give me a valid solution for this problem ( only for study him and understand the algoritm, not for cheat!!!)

Thank you.

My e-mail is fdkaos2000@yahoo.es

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

for contact, you gotta deal with 01, and 001, which all has a binar value of 1

so the best way is to add 1 in the front, ie 101 and 1001
just walk through the input data, keep track of the longest block you need (ie if the input asks you for something at most length 16, just keep track of 16 most recent characters) and so on.

for shaping regions, a boolean of 10000x10000 is too large, so you gotta keep track of all the rectangles instead of all the 1x1 areas. so you calculate the new rectangles formed by placing an overlapping rectangle on top of it.

what i dont understand ishow did you not finish shaping regions and get to contact? they are not in the same section...

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Help needed for USACO problem

Post by ec3_limz »

Hi,

I am at USACO section 1.2.5 and am stuck at the problem Stringsobits. I tried generating all possible strings and of course got TLE when my program had to generate 2^31 strings.

Here's the problem. I would appreciate any help given. Thank you very much.
Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits

INPUT FORMAT
A single line with three space separated integers: N, L, and I.
SAMPLE INPUT (file kimbits.in)

5 3 19

OUTPUT FORMAT
A single line containing the integer that represents the Ith element from the order set, as described.
SAMPLE OUTPUT (file kimbits.out)

10011
Thanks, again.

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs »

Hello.
The post is 3 months old... are you still stuck with it? I believe I could give you some hints on this one. :)

User avatar
mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

Post by mlvahe »

Now I'm at 1.4.1 and can't solve Cryptcowgraphy.

Can any body help me with it, please.

I saw Aleksandrs Saveljevs's reply and I'd be greatful if he helped me.

Alessandro
New poster
Posts: 27
Joined: Mon Jun 14, 2004 10:33 pm
Location: Latina, Italy

Post by Alessandro »

For Stringsobits:

Start from the left of the binary sequence you must find: for every place, choose 0 if the remaining places can contain I valid strings, otherwise it is 1. Obviously, you must change the value of I every time you place a 1, and also you must use binomial coefficients to find how many valid strings can be contained by a certain amount of bits.

Goodbye
Alessandro
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it

Post Reply

Return to “Algorithms”