Waste less time on Facebook — follow Brilliant.
×

USACO

USACO discussion here. What algorithms did you guys make?

Thread guidelines:

  • 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
4 years ago

No vote yet
9 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

Comments

Sort by:

Top Newest

Can somebody please post these problems? I

Mark Mottian - 4 years ago

Log in to reply

Here

Daniel Chiu - 4 years ago

Log in to reply

Thanks! :)

Mark Mottian - 4 years ago

Log in to reply

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:

Michael Tang - 4 years ago

Log in to reply

Python: 2

C:

C++:

Pascal:

Java:

I'm learning C++ now.

Ryan Soedjak - 4 years ago

Log in to reply

Python: 2

C:

C++:

Pascal:

Java: 1

Cody Johnson - 4 years ago

Log in to reply

@Cody Johnson Python: 2

C:

C++:

Pascal:

Java: 2

Daniel Chiu - 4 years ago

Log in to reply

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

Spock Weakhypercharge - 3 years, 6 months ago

Log in to reply

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.

Daniel Chiu - 4 years ago

Log in to reply

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

Cody Johnson - 4 years ago

Log in to reply

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!

Daniel Chiu - 4 years ago

Log in to reply

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?

Ammar Fathin Sabili - 4 years ago

Log in to reply

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.

Ryan Soedjak - 4 years ago

Log in to reply

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.

Michael Tang - 4 years ago

Log in to reply

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

Michael Tang - 4 years ago

Log in to reply

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

Michael Tang - 4 years ago

Log in to reply

@Michael Tang Creating a list of all the possible combinations

Minimario Minimario - 4 years ago

Log in to reply

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

eh maybe there is i kind of forgot the problem

Ryan Soedjak - 4 years ago

Log in to reply

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

Akash Singh - 1 year, 9 months ago

Log in to reply

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

Akash Singh - 1 year, 9 months ago

Log in to reply

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

Akash Singh - 1 year, 9 months ago

Log in to reply

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

Akash Singh - 1 year, 9 months ago

Log in to reply

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();
            lines.add(l.substring(19,l.length()-5));
        }

        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];
        adjectives.add(new ArrayList<String>());
        adjectives.get(0).add(first);

        while(last.length() > 0){
            String[] split = last.split(" ",2);
            first = split[0];
            if(split.length > 1)
                last = split[1];
            else {
                adjectives.add(new ArrayList<String>());
                adjectives.get(adjectives.size()-1).add(first);
                break;
            }
            adjectives.add(new ArrayList<String>());
            adjectives.get(adjectives.size()-1).add(first);
        }

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

        for(int i = 0; i < adjectives.size(); i++)
            Collections.sort(adjectives.get(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;
    }
}

Cody Johnson - 4 years ago

Log in to reply

I think your observation was for #2.

Michael Tang - 4 years ago

Log in to reply

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++){
            cows.add(new cow(s.nextInt(),s.nextInt()));
            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;
    }
}

Cody Johnson - 4 years ago

Log in to reply

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++){
                    combos.add(new combination((farmer[0]+n+i)%n,(farmer[1]+n+j)%n,(farmer[2]+n+k)%n));
                    combos.add(new combination((master[0]+n+i)%n,(master[1]+n+j)%n,(master[2]+n+k)%n));
                }

        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;
            }
        }
    }
}

Cody Johnson - 4 years ago

Log in to reply

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.

Ahaan Rungta - 4 years ago

Log in to reply

I only solved #1. :'(

Zi Song Yeoh - 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...