# USACO

USACO discussion here. What algorithms did you guys make?

• Respond to the [level] #[number] (like Bronze #1) post with your code

• If your level and number are not posted yet, post your code as [level] #[number]: [code]

Note by Cody Johnson
6 years, 8 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Another question: Which language did you use? Let's keep a tally in our posts (reply only to this one!)

Python: 1

C:

C++:

Pascal:

Java:

- 6 years, 8 months ago

Python: 2

C:

C++:

Pascal:

Java:

I'm learning C++ now.

- 6 years, 8 months ago

Python: 2

C:

C++:

Pascal:

Java: 1

- 6 years, 8 months ago

Python: 2

C:

C++:

Pascal:

Java: 2

- 6 years, 8 months ago

C++++, but they post linguistic stats after each competition

- 6 years, 3 months ago

Can somebody please post these problems? I

- 6 years, 8 months ago

- 6 years, 8 months ago

Thanks! :)

- 6 years, 8 months ago

i did bronze. #1 (combo) was trivial, #2 (milktemp) i brute forced, #3 i didn't really try. as you can see I'm really bad at programming.

- 6 years, 8 months ago

I also did bronze. #1 was easy, like you said; #2 I also brute forced but later I was shown a better sol; #3 I found a good solution to.

- 6 years, 8 months ago

I'm sorta surprised you guys didn't try #3; what did you find hard about it? Organizing the adjective strings? Efficiency?

- 6 years, 8 months ago

Creating a list of all the possible combinations

- 6 years, 8 months ago

Wait but maybe we don't even have enough memory to do that.

eh maybe there is i kind of forgot the problem

- 6 years, 8 months ago

Ah shoot, I messed up on #1 because I assumed things that made the problem too easy. 400 is okay; maybe next time!

- 6 years, 8 months ago

I did silver. 1. I use DP (not actual DP) but it is more likely a binary search. 2. I use priorityqueue structure data, 2 looping (beginning->end, end->beginning) 3. I use 2 states DP (positionnow,position_last). Again, 2 times (beginning->end, end->beginning)

Anyone did the silver?

- 6 years, 8 months ago

Yay results!

I got 667 in Bronze (yay promotion).

1: I hoped I would get it perfect, but failed tests 2 and 3 darn.

2: I thought I might get it perfect, but timed out tests 9 and 10.

3: I knew I would timeout later cases and get earlier ones, but I wonder why I failed test 4.

Also, I used java.

- 6 years, 8 months ago

Congrats! I got 800 in bronze because 6 of the 30 programs timed out. I should've been more efficient on my #3, I had all the time in the world! >:O

- 6 years, 8 months ago

Good job! You probably did the same thing on #2 as me.

Yeah, I was sitting around eating dinner in the last hour. I should have fixed those cases in #1 where $N<5$ (2 and 3) and I might have been able to improve #3.

If I missed one more case, I would not have gotten promoted, whew!

- 6 years, 8 months ago

Bronze #1 (derp, I thought about PIE but I thought it would be too complex) (OOP FTW):

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;

public class combo{
public static void main(String[] args) throws IOException{
Scanner s = new Scanner(new File("combo.in"));

int n = s.nextInt();
s.nextLine();

int[] farmer = {s.nextInt(),s.nextInt(),s.nextInt()};
s.nextLine();
int[] master = {s.nextInt(),s.nextInt(),s.nextInt()};
s.nextLine();

s.close();

ArrayList<combination> combos = new ArrayList<combination>();

for(int i = -2; i <= 2; i++)
for(int j = -2; j <= 2; j++)
for(int k = -2; k <= 2; k++){
}

Collections.sort(combos);

for(int i = 0; i < combos.size()-1; i++)
if(combos.get(i).compareTo(combos.get(i+1)) == 0){
combos.remove(i+1);
i--;
}

PrintWriter p = new PrintWriter(new File("combo.out"));

p.println(combos.size());

p.close();
}
}

class combination implements Comparable<combination>{
public int a, b, c;

public combination(int a, int b, int c){
this.a = a;
this.b = b;
this.c = c;
}

public int compareTo(combination co){
if(a > co.a) return 1;
else if(a < co.a) return -1;
else {
if(b > co.b) return 1;
else if(b < co.b) return -1;
else {
if(c > co.c) return 1;
else if(c < co.c) return -1;
else return 0;
}
}
}
}


- 6 years, 8 months ago

Bronze #2:

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;

public class milktemp{
public static void main(String[] args) throws IOException{
Scanner s = new Scanner(new File("milktemp (2).in"));

long start = System.nanoTime();

int n = s.nextInt(),
x = s.nextInt(),
y = s.nextInt(),
z = s.nextInt();
s.nextLine();

ArrayList<cow> cows = new ArrayList<cow>();

for(int i = 0; i < n; i++){
s.nextLine();
}

s.close();

Collections.sort(cows);

int max = 0;

for(int i = 0; i < cows.size(); i++){
int temp = cows.get(i).a,
total = (cows.size()-i-1)*x+y,
j = 0;

for(; j < i; j++)
if(cows.get(j).b < temp)
total += z;
else
total += y;

if(total > max)
max = total;
}

PrintWriter p = new PrintWriter(new File("milktemp.out"));

System.out.println(max + " - " + (System.nanoTime()-start));

p.close();
}
}

class cow implements Comparable<cow>{
public int a, b;

public cow(int a, int b){
this.a = a;
this.b = b;
}

public int compareTo(cow c){
if(a > c.a) return 1;
else if(a < c.a) return -1;
return 0;
}
}


- 6 years, 8 months ago

Bronze #3 (observation: the optimal temperature would be at least one cow's lower temperature):

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;

public class nocow{
public static void main(String[] args) throws IOException{
Scanner s = new Scanner(new File("nocow.in"));

int n = s.nextInt(),
k = s.nextInt();
s.nextLine();

ArrayList<String> lines = new ArrayList<String>();

for(int i = 0; i < n; i++){
String l = s.nextLine();
}

s.close();

ArrayList<ArrayList<String>> adjectives = new ArrayList<ArrayList<String>>();

String first = lines.get(0).split(" ",2)[0],
last = lines.get(0).split(" ",2)[1];

while(last.length() > 0){
String[] split = last.split(" ",2);
first = split[0];
if(split.length > 1)
last = split[1];
else {
break;
}
}

for(String q : lines){
first = q.split(" ",2)[0];
last = q.split(" ",2)[1];
for(int i = 1; i < adjectives.size()-1; i++){
first = last.split(" ",2)[0];
last = last.split(" ",2)[1];
}
}

for(int i = 0; i < adjectives.size(); i++)

ArrayList<String> combinations = combinations(adjectives);

for(String q : lines)
combinations.remove(combinations.indexOf(q));

PrintWriter p = new PrintWriter(new File("nocow.out"));

p.println(combinations.get(k-1));

p.close();
}

public static ArrayList<String> combinations(ArrayList<ArrayList<String>> arr){
if(arr.size() == 1)
return arr.get(0);

ArrayList<String> combinations = new ArrayList<String>(),
arr1 = arr.get(0);
ArrayList<ArrayList<String>> arr2 = arr;
arr2.remove(0);
ArrayList<String> sub = combinations(arr2);
for(String s : arr1)
for(String t : sub)
combinations.add(s + " " + t);

return combinations;
}
}


- 6 years, 8 months ago

I think your observation was for #2.

- 6 years, 8 months ago

http://www.expert5th.in/packers-and-movers-pune/

- 4 years, 6 months ago

http://www.expert5th.in/packers-and-movers-bangalore/

- 4 years, 6 months ago

http://www.expert5th.in/packers-and-movers-pune/

- 4 years, 6 months ago

http://www.expert5th.in/packers-and-movers-bangalore/

- 4 years, 6 months ago

Bronze. 1 was trivial. 2 was easy if I didn't spend 1 hour doodling. I didn't have time to attempt 3. Overall, a disappointing performance.

- 6 years, 8 months ago

I only solved #1. :'(

- 6 years, 8 months ago