Computer Science Canada

Usaco
Author:  A.J [ Fri Mar 21, 2008 11:27 pm ]
Post subject:  Usaco
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
Author:  Clayton [ Sat Mar 22, 2008 11:02 am ]
Post subject:  RE:Usaco
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.
Author:  A.J [ Sat Mar 22, 2008 7:03 pm ]
Post subject:  Re: Usaco
I was kidding Wink

sure, solutions WELCOME

Please spread the word though....
Author:  CodeMonkey2000 [ Sat Mar 22, 2008 8:13 pm ]
Post subject:  RE:Usaco
Meh contests are boring.
Author:  fishtastic [ Sat Mar 22, 2008 10:17 pm ]
Post subject:  Re: RE:Usaco
CodeMonkey2000 @ Sat Mar 22, 2008 7:13 pm wrote:
Meh contests are boring.

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

edit: btw, i am on 2.3 too.
Author:  klopyrev [ Tue Mar 25, 2008 7:20 pm ]
Post subject:  Re: Usaco
I'm done USACO Training. Very Happy Best resource for programming contests.
Author:  A.J [ Tue Mar 25, 2008 8:21 pm ]
Post subject:  Re: Usaco
I'm now on 3.1 Very Happy!
Author:  A.J [ Tue Apr 01, 2008 7:47 pm ]
Post subject:  Re: Usaco
Never mind, I'm on 3.3! This string should really pick it up! I want to see who does USACO!
Author:  SJ [ Mon Apr 14, 2008 5:23 pm ]
Post subject:  RE:Usaco
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 >.>
Author:  nike52 [ Mon Apr 14, 2008 9:13 pm ]
Post subject:  Re: Usaco
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.
Author:  klopyrev [ Tue Apr 15, 2008 9:59 pm ]
Post subject:  Re: Usaco
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.
Author:  SJ [ Wed Apr 16, 2008 5:09 pm ]
Post subject:  RE:Usaco
AHH! I got it! wohoo! thank you so much Very Happy finally I can move on to 2.2 xD
Author:  A.J [ Wed Apr 16, 2008 11:22 pm ]
Post subject:  Re: Usaco
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 All out

anyways, I hope I'm on the right track, so any thumbs up (or down) will be appreciated...
so...please help Praying
Author:  klopyrev [ Thu Apr 17, 2008 3:55 pm ]
Post subject:  Re: Usaco
DONE 2006.12.09 PROB Your Ride Is Here [ANALYSIS] (Chapter 1)
DONE 2006.12.24 PROB Raucous Rockers [ANALYSIS] (Chapter 3)

16 days... Very Happy

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.
Author:  A.J [ Thu Apr 17, 2008 4:25 pm ]
Post subject:  Re: Usaco
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!
Author:  thegoose [ Fri Apr 18, 2008 9:54 am ]
Post subject:  Re: Usaco
klopyrev @ Thu Apr 17, 2008 4:55 pm wrote:
DONE 2006.12.09 PROB Your Ride Is Here [ANALYSIS] (Chapter 1)
DONE 2006.12.24 PROB Raucous Rockers [ANALYSIS] (Chapter 3)

16 days... Very Happy

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.


The fast record for finishing USACO training I've ever heard of is 2 weeks by Zhou Yuan....but he wasn't exactly learning how to code when he did that....

USACO training is a bit out of touch with the current situation of contests, but I guess it's probably a good place to start. The online judges aren't bad too (for all levels), although some of them are a bit overwhelming.
Author:  klopyrev [ Fri Apr 18, 2008 10:30 am ]
Post subject:  Re: Usaco
I can imagine someone good can finish USACO training in a week, just not many people bother.

And yes, I agree that USACO is out of date.

Although, it is very out of date compared to IOI, not so much for CCC.
Author:  mwplachta [ Sat Apr 19, 2008 9:10 pm ]
Post subject:  Re: Usaco
It is not possible to finish all 6 chapters in just one week - NOBODY can do it (I mean if you really are solving it on your own, without help from any forums - and this is how you should work on it). And USACO is absolutely not out of date - I consider it the best programming contest and training web site in existence.
Author:  r691175002 [ Sun Apr 20, 2008 12:26 am ]
Post subject:  Re: Usaco
Create a new account after completing it and go 18 hours a day.
I dare you.

Jokes aside, I think the USACO is the best resource, although it could use some more instructional text. It is pretty much a series of problems you must complete in order.
Author:  thegoose [ Sun Apr 20, 2008 12:27 am ]
Post subject:  Re: Usaco
mwplachta @ Sat Apr 19, 2008 10:10 pm wrote:
It is not possible to finish all 6 chapters in just one week - NOBODY can do it (I mean if you really are solving it on your own, without help from any forums - and this is how you should work on it). And USACO is absolutely not out of date - I consider it the best programming contest and training web site in existence.


I suppose the times we're discussing are by people who are already well trained and decided to do USACO to 'flex hands'. I've seen several occasions where these people knock off 50+ problems from the same section of an online judge in a day. Also, Zhou Yuan did finish IOI in 1 hour each day, so I wouldn't rule that out as a possbility since training is about 200 problems.

USACO training was put together before the major IOI escalation (Finland/Korea/Wisconsin). A lot of the techniques described on it are no longer useful on *OI and a lot of the 'hot' topics over the past few years are not covered. Also, a lot of the bottle necks on training are quite meaningless, and they typically cause a lot of frustration and time waste on the scale of months.

I would say USACO training is good for starting off, but things like Ural, SPOJ and TopCoder are equally good for that purpose. For harder problems at the IOI level, SGU and POI/BOI/CEOIs seems to be a must these days. (I did some experiments with the US team last summer, and the result seems to be going at POIs without seeing anything like those beforehand is virtually suicidal)
Author:  mwplachta [ Sun Apr 20, 2008 2:05 am ]
Post subject:  Re: Usaco
thegoose @ Sun Apr 20, 2008 12:27 am wrote:


I would say USACO training is good for starting off


This is true - I consider the USACO training site as a training site - and for this purpose it is very good.
Author:  A.J [ Sun Apr 20, 2008 8:38 pm ]
Post subject:  Re: Usaco
Nice...people actually do USACO at compsci.ca (take that saad Laughing ).

anyways, I haven't visited it in a while now (about a month now), as I'm working on a chess program.


I'm at Ch. 4.
Author:  Sane [ Thu Apr 24, 2008 1:17 pm ]
Post subject:  RE:Usaco
The USACO Open is today. I just finished the Bronze level competition in an hour (it's a four hour contest). Fairly confident I got perfect. But they won't promote me to Silver... It's to "prevent cheating" apparently.

Disappointed. Sad

Edit: I'm annoyed because there's a glitch in the problem "Castle", which is preventing me from getting to the next section. The 7th output file seems to have gone missing.

I've sent them an e-mail, but no one's getting back to me. So I'm stuck inside this section until someone fixes whatever is wrong.

Could someone try resubmitting for the castle problem? It's under section 2.1.

My output is the correct output. Below is a screenshot.

Posted Image, might have been reduced in size. Click Image to view fullscreen.
Author:  klopyrev [ Thu Apr 24, 2008 6:22 pm ]
Post subject:  Re: Usaco
Lol... Email Rob about it.
Author:  thegoose [ Fri Apr 25, 2008 7:37 am ]
Post subject:  Re: Usaco
klopyrev @ Thu Apr 24, 2008 7:22 pm wrote:
Lol... Email Rob about it.


Rob (and the rest of the coaches) is all busy with USopen and camp selection since this is the biggest USACO event of the year other than camp.

On a side note, there is a double header of contests this weekend (COI/Usopen). So if you have coding time that are currently being wasted, glhf. The COI website is here: http://www.hsin.hr/coci/.
Author:  Sane [ Fri Apr 25, 2008 8:45 am ]
Post subject:  Re: Usaco
thegoose @ Fri Apr 25, 2008 7:37 am wrote:

On a side note, there is a double header of contests this weekend (COI/Usopen). So if you have coding time that are currently being wasted, glhf. The COI website is here: http://www.hsin.hr/coci/.


Registered.

I'm sure I'll do terrible, but I need the practice. Thanks. (I figured out I messed up something really dumb on the Bronze division)
Author:  Sane [ Sat Apr 26, 2008 11:48 am ]
Post subject:  RE:Usaco
Holy crap. The COI is freaking difficult. I give up. I've had zero practice manipulating numbers as large as 10^18 ... And I'm pretty sure some of these questions involve having to take the square root of numbers that large.
Author:  A.J [ Sat Apr 26, 2008 2:11 pm ]
Post subject:  Re: Usaco
I finished the bronze.

I wanted to ask you, Sane, whether you got it all perfectly?

I got everything except I think that my algorithm for the 3rd question might timeout (I am not going to talk about it any further as many people might still be writing it).
Author:  Sane [ Sat Apr 26, 2008 4:46 pm ]
Post subject:  RE:Usaco
I made a really dumb mistake of making one of my arrays a char array when it needs to hold much larger values. Stupid mistake because I stopped after an hour. Otherwise it was all right. It's depressing because I get perfect on the silver contests, so I was hoping to move up to something more difficult...
Author:  klopyrev [ Sun Apr 27, 2008 4:06 pm ]
Post subject:  Re: Usaco
I don't think COI is anymore difficult than IOI. I think this was actually a particularly easy COCI contest. I didn't actually participate in it. I was too lazy.
Author:  Sane [ Sun Apr 27, 2008 4:31 pm ]
Post subject:  RE:Usaco
Yeah. And I find IOI freaking difficult too. xD

Those problems are just at a whole nother level. I never know how to deal with numbers that large. Well, time to get back to USACO training. Rob fixed the Castle problem.
Author:  klopyrev [ Sun Apr 27, 2008 5:10 pm ]
Post subject:  Re: Usaco
long long is your friend.
Author:  Sane [ Sun Apr 27, 2008 6:40 pm ]
Post subject:  RE:Usaco
Ohshi. Damn Dev-C++. I didn't know long long could go up to 20 digits, because Dev-C++ doesn't support it.

I had been trying to do all those questions by manipulating char arrays. =.=
Author:  Saad [ Sun Apr 27, 2008 6:51 pm ]
Post subject:  Re: RE:Usaco
Sane @ Sun Apr 27, 2008 6:40 pm wrote:
Ohshi. Damn Dev-C++. I didn't know long long could go up to 20 digits, because Dev-C++ doesn't support it.

I had been trying to do all those questions by manipulating char arrays. =.=


Dev-C++ is not a compiler its an IDE. It uses the MinGW compiler which does support long long. Furthermore your forgetting literal constants. IE 1234LL is 1234 in long long format.
Author:  thegoose [ Sun Apr 27, 2008 8:55 pm ]
Post subject:  Re: Usaco
klopyrev @ Sun Apr 27, 2008 5:06 pm wrote:
I don't think COI is anymore difficult than IOI. I think this was actually a particularly easy COCI contest. I didn't actually participate in it. I was too lazy.


Stop being lazy.....^_^

I'd say the difficulty of this COI is the geometric mean between CCC and the hardest of IOIs. I was a bit surprised that none of the COCI's trademark hard problems were on this COI.
Author:  Sane [ Mon Apr 28, 2008 4:32 am ]
Post subject:  Re: RE:Usaco
Saad @ Sun Apr 27, 2008 6:51 pm wrote:
Sane @ Sun Apr 27, 2008 6:40 pm wrote:
Ohshi. Damn Dev-C++. I didn't know long long could go up to 20 digits, because Dev-C++ doesn't support it.

I had been trying to do all those questions by manipulating char arrays. =.=


Dev-C++ is not a compiler its an IDE. It uses the MinGW compiler which does support long long. Furthermore your forgetting literal constants. IE 1234LL is 1234 in long long format.


It does support it, but it's still bugged.

C:
#include <stdio.h>   
                               
typedef unsigned long long Long;

int main(void)                                       
{                                                     
   Long juul = 123456789012345678LL;   
   unsigned char *pjuul;                             
   int i;                                             
                                                     
   printf("sizeof(Long) = %d\n", sizeof (Long));
   printf("juuld: %lld\n",juul);
   printf("juulx: %016llX\n",juul);                     
   pjuul = (char *) &juul;                           
   printf("juulb: ");                                 
   for (i = 0;i < sizeof(Long); i++) printf("%02X",*(pjuul + i));
   printf("\n");         
                       
   return 0;
} 


I get:

C:
sizeof(Long) = 8
juuld: - 1506741426
juulx: 00000000A630F34E
juulb: 4EF330A64B9BB601


Many people have found mingw's support for long long to be bugged.

The fix is to use:

C:
%I64d
%016I64X


Which works. But the Dev-C++ documentation and C standard says to use %lld, so I'm not sure how portable that fix would be.
Author:  Saad [ Mon Apr 28, 2008 2:53 pm ]
Post subject:  Re: RE:Usaco
Sane @ Mon Apr 28, 2008 4:32 am wrote:
Saad @ Sun Apr 27, 2008 6:51 pm wrote:
Sane @ Sun Apr 27, 2008 6:40 pm wrote:
Ohshi. Damn Dev-C++. I didn't know long long could go up to 20 digits, because Dev-C++ doesn't support it.

I had been trying to do all those questions by manipulating char arrays. =.=


Dev-C++ is not a compiler its an IDE. It uses the MinGW compiler which does support long long. Furthermore your forgetting literal constants. IE 1234LL is 1234 in long long format.


It does support it, but it's still bugged.

C:
#include <stdio.h>   
                               
typedef unsigned long long Long;

int main(void)                                       
{                                                     
   Long juul = 123456789012345678LL;   
   unsigned char *pjuul;                             
   int i;                                             
                                                     
   printf("sizeof(Long) = %d\n", sizeof (Long));
   printf("juuld: %lld\n",juul);
   printf("juulx: %016llX\n",juul);                     
   pjuul = (char *) &juul;                           
   printf("juulb: ");                                 
   for (i = 0;i < sizeof(Long); i++) printf("%02X",*(pjuul + i));
   printf("\n");         
                       
   return 0;
} 


I get:

C:
sizeof(Long) = 8
juuld: - 1506741426
juulx: 00000000A630F34E
juulb: 4EF330A64B9BB601


Many people have found mingw's support for long long to be bugged.

The fix is to use:

C:
%I64d
%016I64X


Which works. But the Dev-C++ documentation and C standard says to use %lld, so I'm not sure how portable that fix would be.


Actually this bug would be windows related (specifically msvcrt.dll). However a simple #define and #ifdef could ensure portability.
More information here

On a smaller note, are you coding in C or C++?.

Sorry for going a little off topic Embarassed
Author:  Sane [ Mon Apr 28, 2008 3:29 pm ]
Post subject:  RE:Usaco
Usually C.
Author:  Sane [ Wed May 07, 2008 10:03 pm ]
Post subject:  RE:Usaco
A.J, I found Camelot a lot easier than a lot of other chapter 3 problems. Camelot took me 2 tries to get working (forgot to handle the case where there are no knights). Some other problems like Humble Numbers took me a whole day to get working. Do you think Camelot was really the hardest one in chapter 3?

P.S. The most annoying part about that question was parsing the input in C. Since as far as I know, you can't use scanf if you want to stop at the EOF. I had to use getchar() and manually parse it.
Author:  A.J [ Sat Jan 31, 2009 11:15 pm ]
Post subject:  Re: Usaco
k, I am almost done USACO training....

and does anyone know whats the deal with the 'new' training pages? what is it about and how does one get access to it?
Author:  saltpro15 [ Sun Feb 01, 2009 8:41 am ]
Post subject:  RE:Usaco
Well, about 2 months ago i started hearing about how great the USACO training is for DWITE, so I thought I'd check it out. So after a month and a half learning C++, I have 1 question done -.- I understand how to get the answer, I just don't know enough C++ to code it Very Happy
Author:  phreadj [ Sun Mar 29, 2009 6:23 pm ]
Post subject:  Re: Usaco
A.J @ Sat Jan 31, 2009 11:15 pm wrote:
k, I am almost done USACO training....

and does anyone know whats the deal with the 'new' training pages? what is it about and how does one get access to it?


you can easily make an account (possibly even the same as your contest account, not sure)
and it is sort of like a contest which never ends. once you look at the question, the timer starts and it doesnt stop
until you submit the right solution. The questions get harder as you do more, it is good practice
Author:  A.J [ Sun Mar 29, 2009 9:18 pm ]
Post subject:  RE:Usaco
nice

I am at the end of chapter 5 of the normal training pages

if I finish it, then I'll look into the new ones for sure. thanks
Author:  SJ [ Sun Mar 29, 2009 10:59 pm ]
Post subject:  Re: Usaco
phreadj @ Sun Mar 29, 2009 6:23 pm wrote:
A.J @ Sat Jan 31, 2009 11:15 pm wrote:
k, I am almost done USACO training....

and does anyone know whats the deal with the 'new' training pages? what is it about and how does one get access to it?


you can easily make an account (possibly even the same as your contest account, not sure)
and it is sort of like a contest which never ends. once you look at the question, the timer starts and it doesnt stop
until you submit the right solution. The questions get harder as you do more, it is good practice


I thought the new training problems are "invitation only"? are you referring to ace.delos.com/traingate

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy