DEV Community: Alice Lee

USACO Techniques - Simulation

Alice Lee — Wed, 26 Mar 2025 01:35:42 +0000

What is Simulation?

Simulation is directly simulating what the problem statement tells you to do. Since there are no algorithms required, the program is written in a direct and straightforward manner.
Key Characteristics:

Follows problem description literally
Uses conditional statements and loops heavily
Often involves tracking state changes over time

Example Problem 1

USACO Jan 2019 Bronze 1. Shell Game

Overview

Rules:

Three shells named 1,2,3 (positions 1, 2, 3)
Pebble starts under one shell
N swaps performed 4. a and b are swapped, g is the guess

Solution Code(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    //freopen("shell.in","r",stdin);
    //freopen("shell.out","w",stdout);
    int N;
    cin>>N;
    vector<int> guess(3);
    vector<int> shells = {0,1,2,3}; 
    while(N--){
        int a,b,g;
        cin>>a>>b>>g;
        swap(shells[a],shells[b]);
        guess[shells[g]]++;
    }
   cout<<max({guess[1],guess[2],guess[3]}); 
}

Example Problem 2

USACO Dec 2018 Bronze 1. Mixing Milk

Overview

Pour milk(100 times)*:

1->2->3->1 sequence
Therefore, for the i_th pour, bucket[i%3] pours into bucket[(i+1)%3]

Solution Code(C++)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    //freopen("mixmilk.in","r",stdin);
    //freopen("mixmilk.out","w",stdout);
    vector<ll> cap(4),amount(4);
    for(int i=0;i<=2;++i) cin>>cap[i]>>amount[i];

    const int N = 100;
    for(int i=0;i<N;++i){
        ll bucket1 = i%3; //index of the first bucket
        ll bucket2 = (i+1)%3; //index of where the first bucket pours into
        ll pourMilk = min((cap[bucket2]-amount[bucket2]),amount[bucket1]);
        amount[bucket2] += pourMilk;
        amount[bucket1]-= pourMilk;
    }
    for(int i=0;i<=2;++i) cout<<amount[i]<<"\n";
}

Introduction to Data Structures

Alice Lee — Sun, 09 Mar 2025 12:51:20 +0000

What are Data Structures?

Data structures allow you to store and organize different types of data(eg, int, string, etc.) and use these information efficiently.
In C++, the STL(Standard Template Library) data structures can store any type of data. Its data type is declared by what you insert inside <>.
For example: vector<int> array;.
Every STL data structure allows you to use the size() and empty() methods, explained later.
This note covers arrays, dynamic arrays, iterating, stacks, queues, sets, maps, and pairs.

Arrays

An array is a special kind of data type that allows users to store multiple values of the same data type inside.
There exists a class array in STL, simply declared like this:

array<int, 20> a;

Dynamic Arrays

A dynamic array is a special kind of array that is "dynamic." This means the size of the dynamic array can be modified
There are different ways of declaring a dynamic array(vector, the most commonly used one) shown below.

vector<int> v(n); //creates a vector "v" with the size of n, all values initialized to 0

vector<int> v; //another way, same as above
v.resize(n);

vector<int> v = {1,2,3} //creates a vector with three elements 1,2,3 with size of 3

vector<int> v(5,1) //creates a vector size of 5, with all elements value initialized 1

Iterators

Iterators are pointers that point towards an element in a data structure.

Vector iterators

Vector iterators are often used to define the range of a data structure. The two useful iterators are v.begin() that points towards the first element, and v.end() pointing towards a position after the last element. For example:

vector<int> v = {4,3,2,1};
sort(v.begin(),v.end());
for(int i=v.begin();i!=v.end();++i) cout<<*i<<" ";
//or for(auto i : v) cout<<i<<" ";
//or for(vector<int>::iterator i = v.begin();i!=v.end();++i) cout<<*i<<" ";
//output: 1 2 3 4

Set iterators

Iterators of a set are often used to access elements in a set.
Set: A container that stores a sorted list of unique numbers. For example:

set<int> s={1,2,5,5,2};
for(auto i = s.begin();i!=s.end();++i) cout<<*i<<" ";
//output: 1 2 5
//or: for(auto i : s) cout<<i<<" ";
//same output

Common actions(vector)

vector<int> v(5);
v.push_back(2); //v={0,0,0,0,0,2} appends 2 to the end of the vector

vector<int> v;
v.push_back(1); 
v.push_back(2);
v.push_back(3); //v={1,2,3} the vector automatically resizes itself
v.erase(v.end()-1) //v={1,2}
v[0] = 3; //v={3,2}

Sieve of Eratosthenes: What is it? And how to implement sieve in C++

Alice Lee — Mon, 03 Mar 2025 06:48:51 +0000

What is Sieve of Eratosthenes

Sieve of Eratosthenes is one an ancient algorithm that finds all prime numbers in a given range. It is also used for finding all divisors of a number with a faster time complexity.

Sieve Algorithm

The algorithm starts by generating a boolean array Boolarray to store whether i is a prime number or not. 2. Every number in the array is set to be TRUE by default. 3. The outer loop of the algorithm iterates Boolarray from 2 to sqrt(n) . - Inner loop iterates through j and accumulate by i(for all multiples of i), all multiples are marked FALSE(since these are not prime numbers). - Inner loop works by marking FALSE on all multiples of i

We are left with b with all prime numbers being TRUE in the range of 1 to n.

Time Complexity

The time complexity of the above logic is O(n log log n). The outer loop runs for sqrt(n), while the inner loop runs roughly n / i times.

Example in C++

#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    bool Boolarray[n+1];
    for(int i = 2; i <= n; i++) {
    Boolarray[i]=true;
    }
    for (int i = 2; i * i <= n; i++) {
    if (Boolarray[j] == true) {
        for (int j = 2 * i; j <= n; j += i) {
        Boolarray[k] = false;
        }
    }
    }
    for(int i = 2; i <= n; i++) {
        if(Boolarray[i]==true)
            cout<<i<<" ";
    }
    return 0;
}

Image Source https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html

Big O Notation Explained: How to Analyze Your Algorithm’s Speed

Alice Lee — Thu, 27 Feb 2025 02:08:17 +0000

What is Time Complexity

Time complexity is a tool for algorithm analysis that helps you calculate roughly how fast your algorithm is. It measures the number of operations in an algorithm.
(The USACO grading server can handle around 2*10^8 operations per second.)
Time complexity is denoted with “Big O notation” as O(f(n)), aka “asymptotic notation.”

Calculating Time Complexity

We consider all constant numbers of operations as O(1). For example, input and output and math operations. When there is a loop, the time complexity is the number of times the loop has to iterate multiplied by the number of operations each iteration. Ignore constant factors and lower-order terms. If an algorithm contains multiple blocks of code, the time complexity is considered the worst time out of all loops.

Constant Factor

Completely ignore the constant factor of time complexity. For example, adding ten numbers together takes longer than adding two. However, there is no difference in time complexity since we ignore the constant factor O(10*1) and O(2*1). Therefore, both complexity counts as O(1).

Examples

O(1) Complexity

int a = 1;
int b = 2;
int c = a + b;

int n=100;
for(int i = 0; i < n; i++){ //code }

O(n) Complexity

int n;
cin>>n;
for(int i = 0; i < n; i++){ //code }

int n;
cin>>n;
for(int i = 0; i < n+9999; i++){ //code }

O(nm) Complexity

int n,m;
cin>>n>>m;
for(int i = 0; i < n; i++){
  for(int j = 0; j < m; j++){
    //code 
  }
}

O(n^2) Complexity

int n;
cin>>n;
for(int i = 0; i < n; i++){
  for(int j = 0; j < n; j++){
    //code 
  }
}

O(log n) Complexity

int n; 
cin >> n;
for (int i = 1; i < n; i *= 2) { //code }

Since log_2 n with base 2 means the number of square root n has to execute to get n<=1, if we iterate from 1 to n with i multiplying itself by 2, it runs for exactly log n times; thus the code represents O(log n) complexity.

int binarySearch(const std::vector<T>& arr, const T& target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

O(sqrt(n)) Complexity

int n, cnt=0; //count cnt the number of prime factors
cin>>n;
for(int i = 1; i*i <= n; i++){
  if(n%i==0){
    if(i*i==n)
      cnt++;
    else
      cnt+=2;
  }
}

Counts the number of prime factors of n.

Image Source https://www.linkedin.com/pulse/understanding-big-o-notation-vijay-s-c

Beginner Contributions: This is how I learned to contribute to open source projects on GitHub

Alice Lee — Sat, 22 Feb 2025 03:38:39 +0000

Intro

Feb 22, 2024. This is the absolute first time I'm actually contributing to GitHub. I've struggled and slacked, never actually learned what Git and Github are. I didn't even know what a repo was at that time. Now I've realized that forking, cloning, and all the "crazy" stuff on GitHub only takes a few hours to master. I decided to watch a bunch of YouTube videos and, most importantly, to read the "Collaborative Coding" section in GitHub Docs.

What I learned

Git-Think of this as a time machine to track everything that happened to your code. This works well with the GitHub platform. If you are using Mac(like me) git is already installed if you have Xcode. To install, refer to the "resources" section of this post, and run git commands in Mac Terminal.
Repository(Repo)-It's a place to track the version histories for all your work. You can also add a README inside a repo to explain what your project is about.
Fork-A copy of a repo that is yours. You can experiment with the repo however you want.
Commit-All the changes you made in your branch that are recorded.
Pull Request(PR)-It's a proposal to merge someone's commits to the main branch.
Issue-Issues are literally issues occurring in a project. It also helps maintainers track bugs, requested features, webdev mistakes, etc. If you're a beginner contributing to an open-source project, look for issues with the label "Good first issue."

These are the resources that helped me

GitHub Docs
Download Git
Git Tutorial
GitHub's Git Tutorial
Pull Requests
Contributions Tutorial

Good Luck. Follow me on GitHub 👍