Usaco

[A.J]

I decided to see how many people actually do the USACO training, and to see how people are doing.
For example:
user:A.J (amleshe1 on training page)
Started:1-2 weeks back
Chapter/part:2.3
Question working on:Zero sum/Controlling Companies

No answers/solutions are to be discussed here or the post will be deleted (hopefully the mods will help me out there).
Only questions about the understanding of other questions, and running errors, etc... will be applicable.

A.J

[Clayton]

A.J. wrote:

No answers/solutions are to be discussed here or the post will be deleted

I'm afraid I don't support this at all. Discussion is part of learning. It's not like we're writing the CCC as this thing happens.

[A.J]

I was kidding

sure, solutions WELCOME

Please spread the word though....

[CodeMonkey2000]

Meh contests are boring.

[fishtastic]

CodeMonkey2000 @ Sat Mar 22, 2008 7:13 pm wrote:

Meh contests are boring.

I am sorry A.J. but I agree with him.

edit: btw, i am on 2.3 too.

[klopyrev]

I'm done USACO Training. Best resource for programming contests.

[A.J]

I'm now on 3.1 !

[A.J]

Never mind, I'm on 3.3! This string should really pick it up! I want to see who does USACO!

[SJ]

I'm stuck on Sorting a Three Valued Sequence for a looooooooooooong time now (like, a month or 2?) and gave up on it and almost forgot about it... can you help me? My "algorithm" is to just have a sorted list, look at the number of differences, and the number of switches is # of differences div 2 if # of diff is even, if its odd then it's # of diff + 1 div 2. It fails 1 test case, i think... I don't know whats wrong with it >.>

[nike52]

Quote:

I'm stuck on Sorting a Three Valued Sequence for a looooooooooooong time now (like, a month or 2?) and gave up on it and almost forgot about it

ACK! Bad memories. Unless you're very smart, USACO/topcoder isn't for the beginner. I should have started with the CCC first. It would have been better for me if I started at a moderate skill level.

[klopyrev]

For sorting a three-valued sequence:

Sort the sequence and consider the following things:

How many 1s are in a place where there should be a 2.
How many 1s are in a place where there should be a 3.
How many 2s are in a place where there should be a 1.
...
How many 3s are in a place where there should be a 2.

There numbers are enough to solve the problem.

First of all, if you have that a -> b -> a, you can fix that with just 1 swap.

The problem is when you have a -> b -> c -> a. You need 2 swaps to fix that.

[SJ]

AHH! I got it! wohoo! thank you so much finally I can move on to 2.2 xD

[A.J]

I'm almost at Chapter 4!!!
I think I might have beaten the record for getting to the end of Ch 3 (in 3 weeks), then I stopped at the question 'Camelot'.
I just have to finish that question to get to Chapter 4!!!!

I already BFS'ed for the knights and I would have already finished the problem IF THAT STUPID KING WASN'T INVOLVED!!!!!

Now I have to check if any knight can take the king with it on its shortest path, or 2nd shortest path, etc... or if the king already has a shortest path without the knight's help.............soooooooooo tiring

anyways, I hope I'm on the right track, so any thumbs up (or down) will be appreciated...
so...please help

[klopyrev]

DONE 2006.12.09 PROB Your Ride Is Here [ANALYSIS] (Chapter 1)
DONE 2006.12.24 PROB Raucous Rockers [ANALYSIS] (Chapter 3)

16 days...

Anyway, for Camelot... You're almost on the right track. In your BFS, consider adding a new state - whether the king has been picked up by this knight.

[A.J]

I don't remember racuous rocker as a chapter 3 problem...
anyways, 16 days beats my record by (almost) 5 sixteenths (it took me about 21 days...)

so, I'll add if the king has been picked up or not....but what if the king isn't on the knight best path?

I think I got how to do it, so thanks klopyrev!