A necklaces has N beads and A different colors for each bead. Two necklaces are considered the same if one can be rotated to make the other.

Observations

Consider a necklace with 4 beads and 2 different colors of beads. The total number of lines of beads would be 2^4. Now subtract of all of thes lines that can rotate to become itself in less than 4 rotations.

Think about splitting 4 into 2 and 2. Setting the first 2 and the second 2 to be the same string would lead to a rotation by 2 creating the same string. For example if they are both 10...

original first rotation second rotation third rotation 1010 ----> 0101 ----> 1010 ----> 0101

If we subtract of all the possible ways to make the 2 beads (2^2) is the total number of lines that can be rotated into themselves, If we subtract of 4 from our original number, we get there to be 12 total lines that can be created without the lines repeating themselves with less than 4 rotations.

Since we know that 12 lines never repeat themselves with less than 4 rotations, we realize that this number has to be divisible by 4, since for each string, all 3 of its rotations are also part of the 12.

1000, 0100, 0010, 0001 are all part of the 12 strings and are rotations of each other 1100, 0110, 0011, 1001 are all part of the 12 strings and are rotations of each other 1110, 0111, 1011, 1101 are all part of the 12 strings and are rotations of each other

This means that this value after subtracting of all the ways to rotate and repeat early has to be divisible by the total number of beads. Although, it will not always be as simple as subtracting of one case because of over-counting (explained later).

Prime length Necklaces

In the case with the number of beads as 4, it was able to be split into multiple 2s (a factor of 4). Since prime length necklaces don't have any factors other than 1 and itself, it has to be split into all 1s.

Consider a necklace with 7 beads and 2 different colors of beads. There are 2^7 different lines of beads, and the only 2 cases that repeat themselves are all one color or all the other color.

Subtracting off these two cases gives 2^7-2, and as previously shown this value has to be divisible by 7, because all thats left are strings that have all 6 of there rotations part of the 2^7-2. Therefore 2^7 is congruent to 2 mod 7, or 2^6 is congruent to 1 mod 7.

Lets generalize this: consider a necklace with N beads and K different colors of beads. There are K^N different lines of beads, and only case where they repeat themselves are all the same color (K different colors). This means that K^N-K is congruent to 0 mod N, or K^N-1 congruent to 1 mod N. Fermat's little theorem is proved

Composite length Necklaces

With a composite length necklace, look through all the divisors and choose to either add, subtract them, or don't do anything. Think about it like this, all the factors should be removed from the total eventually, and if a factor is removed, and factor of the factor is also removed, turning into somewhat of an inclusion-exclusion problem.

look at the case for N as 12 and 2 different bead colors. The answer is 2^12 (split into 1, 2, 3, 4, 6, 12 groups) — 2^6 (1, 4) — 2^4 (-1, 2 (2 is subtracted)) + 2^2 (1). To find out which factors are added, subtracted, and neither though is the really cool part. Write each term as 2^(12/k) for k as divisors of 12.

2^(12/k) counts all multiples of k. If you add all ks with an even amount of prime factors and subtract all ks with an odd amount of prime factors everything works perfectly. First add 2^(12/1) (1 has 0 (even) prime factors) adding all multiples of 1. Then subtract 2^(12/2) and 2^(12/3) (2 and 3 have 1 (odd) prime factors). Now add back 2^(12/6) (6 has 2 (even) prime factors). This cancels everything. Here is the proof:

For a k with odd prime factors the times it has already been added is: N choose 0 (k = 1) — N choose 1 (k prime) + N choose 2 (k multiple of two primes) — ... + N choose N-1 (k multiple of N-1 (even) primes). Due to the fact that odd chooses and even chooses are equal, it cancels out to be counted just 1 time (the last N choose N hasn't been subtracted). This proves that we have to subtract the odd powers.

For a k with even prime factors the times it has already been added is: N choose 0 (k = 1) — N choose 1 (k prime) + N choose 2 (k multiple of two primes) — ... — N choose N-1 (k multiple of N-1 (odd) primes). Due to the fact that odd chooses and even chooses are equal, it cancels out to be counted just -1 times (the last N choose N hasn't been added). This proves that we have to add the odd powers.

Finally or a number k that is a multiple of a perfect square, it completes the bionomial. N choose 0 (k = 1) — N choose 1 (k prime) + N choose 2 (k multiple of two primes) — ... + or minus N choose N (because the final is just the product of the prime divisors without any powers) Since all the rest of the multiples of perfect squares are also 0, all other divisors of a multiple of a perfect square contributes to 0. The entire binomial cancels out with 0 for all multiples of perfect squares.

There is a special function that gives 1 if the number has even number of prime divisors, -1 if it has odd prime number of divisors, and 0 if it is a multiple of a perfect square regardless of prime divisors. Idk how to get mu so I'll just call it m(a).

[sum for all d as a divisor of p] m[d]*a^(p/d) is congruent to 0 mod p - Gauss's Necklace Formula

If you wanna reach expert you have to

• pass specialist (obviously)
• know some topics
• get good perfs

Now a lot of people think "if i can get expert perfs i can become a expert" and your wrong. Expert perf best means that your worse than expert. Aim to always get a higher level than you already are so im finna be aiming for master next (bit of a stretch this is my cap).

Now how do u get good tho. Solve problems and listen to twice ofc (do u get the reference). But just solving bum ahh problems that are 1600 won't get you to specialist. If you wanna get to specialist u have to at least be solving 2000s imo cus then youll at least be able to solve 1600-2000 in contest and hopefully get good perf.

And for learning topics just learn them as you go. Look at the solution and if u dont understand the topic from there look at usaco guide or search it up online its not that hard.

Also don't forget to peel the leaves and do the derivative and binary search strat to solve dodecaseptic polynomials

Apparently my posts are "repetitive", "not good quality", and "useless" so i guess ill try to make a good one.

My teacher told me that instead of learning how to do different problems in different creative ways (sounds yuck in general), be lazy and use the same way, and he taught me how to peel leaves off the tree.

So if you go to a tree and start peeling the leaves, you'll prob never finish off the tree. One reason is because there's too much leaves and the second reason is because the entire tree isn't made of leaves so you'll be left with branches when you're done. The first problem is easily solved cus we're using a computer algorithm and not actually peeling leaves. The second one is trickier though, how would you delete a tree by only peeling leaves. It's actually a lot simpler than it seems. You just have to use the secret technique to turn branches of a tree into leaves so u can peel them off too.

I know this just sounds like I'm spouting nonsense (apparently like my other posts) but I'm actually not. Look at an actual computer science tree.

If you don't know what a leaf is, it's a node that is only connected to one other node in an undirected tree, or a node that has no children. I double bordered all the leaves in the image. So now our beautiful beautiful tree has a stump and branches growing out from the stump, finally reaching the double bordered leaves at the end. Now we can pluck off these leaves. Fun right, I love plucking leaves of trees while going outside. Anyways after you pluck off all the trees you get this new tree (with all the edges from the plucked leaves removed).

Now you might be wondering, what are the new double bordered nodes? Well they are nodes with 0 children, or only connected to one other node. "WAIT A SECOND, THATS A LEAF!" — probably you as soon as you see this part of the beautiful post. You're right smart one, after you pluck off the leaves (very soothing task by the way you should try it sometime) you get more leaves. Unlike in real life where you get actual branches. Yuck! Now you might be thinking, I can keep peeling the leaves, and to that I say good job thats pretty much it. Here are the pictures of the tree as you keep peeling.

Good job! You have successfully learned how to delete a tree (hopefully). Now you're probably thinking why is this useful? Well it isn't... IF you aren't doing anything and just mindlessly (or should I say algorithmlessly) plucking off leaves.

For example, let's look into how to use this technique for an actual USACO silver tree problem (the entire goal of the post).

Cowntagion

This problem is classified as greedy on USACO guide, and everyone hates when they can't figure out a simple greedy idea. Since this problem is a tree problem, think about how to peel the leaves. You know that every single node has to have one infect at the end of the days. Thinking about this and leaves gives us the question, how does a leaf get a infect?

Simple, leaves can only get an infect from their parent. This means that a parent has to double enough times to give 1 infect to every single one of its children. Why is this true? Think about this, if a parent has 1 node, and its parent has how much ever it could possibly need. The parent needs to provide for the children as we said earlier. This is only done if the parent has enough infects to give to each one of its children, and keep one for itself (all nodes need to have an infect including the parent). This leads to the observation that node i needs to have child[i]+1 infects. To get this amount, it could either get 1 and then continue to double, or get child[i]+1, separate 1s from the parent. obviously, getting one and doubling is faster or the same as getting each one from the parents in all scenarios, because it is an exponential vs a linear (1 : 1, 2 : 2, 4 : 3, 8 : 4, ... exponential mogs). This means that we can get the idea that a parent of x children should get 1 infect from its parent, and then double until it has >= x+1 infects.

That's the greedy idea for the problem; double the infects until it's enough for its children and yourself. For the full solution, loop through each node, find how much doubles it takes, and how much moves it takes to move to the children, and add it all up for all nodes.

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    // notice how the adjacency list isn't even needed or even any graph algorithm
    // number of connections to node i
    vector<int> con(n, 0);
    for (int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b; a--; b--;
        con[a]++;
        con[b]++;
    }
    int ans = 0;
    for (int i = 1; i < n; i++){
        // find how much times the infects need to double
        int infects = 1;
        // it should be number of children + 1, which is the same as 
        // con[i]-1 (subtract parent) + 1 and the ones cancel
        while (infects < con[i]){
            infects *= 2; ans++;
        }
        // add the number of moves to the children
        ans += con[i]-1;
    }
    // finally add the answer for the root node
    int infects = 1;
    // root doesn't have a parent so its con[0]+1 (the one isn't subtracted)
    while (infects < con[0]+1){
        infects *= 2; ans++;
    }
    // add children
    ans += con[0];
    cout << ans << endl;
}

Here is the code if you need it. Notice how I don't actually use leaf peeling in the code, but instead only use it to get the greedy idea. The point of leaf peeling is that it makes the problem a lot simpler to view.

Let's look at a harder example (squarey).

Barn Tree

The point of the problem is to move haybales from barn to barn so that all the barns have an equal amount of haybales.

Look straight at the leaves. The first thing you notice is that the leaves are only connected to one other barn, meaning that it can only move haybales too/take haybales from one barn. This means that if a leaf has too much bales (more than the average), it has to pass it's bales on too the neighbor. If otherwise, it has to take from the neighbor. Thats pretty much the idea, except after taking/giving, the node is removed, parent is updated, and a new leaf can be formed. This follows the leaf peeling process and gives our answer on which barns to move bales from. Now the only issue is what order should these movements be printed in. This part is pretty intuitive, if a barn is giving, it means it is giving enough so it can be equal to average. This will only increase the parent and decrease the current node down to the average, so no values will be negative. This allows the process to be printed very first. The second type of process is where the parent gives to the child. If the parent gives to the child, the parent could be in the negative, causing its parent to give to it. This could cause a chain of being negatives starting from the root node. To avoid the negatives, reverse the order in which the bales are given from the parents to the children, so that the process starts at the root node, and is never negative.

Thats it! leaf peeling for the win.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
#define int long long
struct ans{
    int startbarn;
    int endbarn;
    int baleamt;
};
signed main(){
    int n; cin >> n;
    vector<int> bales(n);
    int avg = 0;
    for (int i = 0; i < n; i++){ 
        cin >> bales[i];
        avg += bales[i];
    }
    avg = avg/n;
    vector<vector<int>> adj(n);
    vector<int> con(n, 0);
    for (int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b; a--; b--;
        con[a]++; con[b]++;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    queue<int> q;
    // add leaves to the q for bfs
    // make 0 the root
    for (int i = 0; i < n; i++){
        if (con[i] == 1 && i != 0) q.push(i);
    }
    // give and take to/from parent for the answer
    vector<ans> give;
    vector<ans> take;
    while (!q.empty()){
        int cur = q.front();
        q.pop();
        for (int i : adj[cur]){
            if (con[i] == 1 && i != 0) continue;
            con[i]--;
            if (bales[cur] > avg){
                // give case
                give.push_back({cur+1, i+1, bales[cur]-avg});
            }
            else if (bales[cur] < avg){
                // take case
                take.push_back({i+1, cur+1, avg-bales[cur]});
            }
            bales[i] += bales[cur]-avg;
            // only add i if its a leaf
            if (con[i] == 1 && i != 0) q.push(i);
        }
    }
    // reverse take to avoid negatives
    reverse(take.begin(), take.end());
    cout << (int)give.size()+(int)take.size() << endl;
    for (auto i : give){
        cout << i.startbarn << " " << i.endbarn << " " << i.baleamt << endl;
    }
    for (auto i : take){
        cout << i.startbarn << " " << i.endbarn << " " << i.baleamt << endl;
    }
}

Thanks for reading this! Downvote me if you want but know I tried my best this time.

So basically I took my first contest and then my second contest and then my third contest and the my fourth contest where I made pupil. I then took my fifth contest and then my sixth contest and then my seventh contest and then my eight contest when i made specialist

Thanks to DragonChess233 for the great idea

dont promote to USACO silver in a previous contest or cheat and get caught

a lot simpler than plat so ima go through all the ways to promote

• work in a team environment

• use Generative AI

• obscure ur ip address

• consult the problems with people other than the contest director

• share any technical information or code pertaining to a contest while it is actively running

• use pre-written codes or templates

• use multiple login IDs or use invalid information

• submit code that behaves in a malicious way to the grading server

これは内緒で、カンニングをしないためのリマインダーです。

Thanks for reading another epic post (this one is for wrenzox)

How to make USACO platinum

To make USACO platinum you must: - be in USACO gold and promote with a certified gold contest - be in USACO silver and promote with a perfect score before certified window and then promote with a certified gold contest - be in USACO bronze and promote with a perfect score before certified window and then promote to USACO gold with a perfect score before the certified window and then promote with a certified gold contest

That is pretty much all u have to do to accomplish USACO platinum

You might be thinking "this guy is an idiot". Well you probably aren't wrong but heres how to actually do one of these options

First option (be in USACO gold and promote with a certified gold contest), to do this you must either: - promote to USACO silver in a previous previous contest and promote to USACO gold in a previous contest after the first contest - promote to USACO silver with a perfect score and promote to USACO gold in the same contest

Second option(be in USACO silver and promote with a perfect score before certified window and then promote with a certified gold contest), to do this you must: - promote to USACO silver in a previous contest iclearhouses Third option(be in USACO bronze and promote with a perfect score before certified window and then promote to USACO gold with a perfect score before the certified window and then promote with a certified gold contest), to do this you must: - not promote to USACO silver in any previous contest

Now you might still be thinking "this guy is an idiot". You still probably aren't wrong but just to clear things up you have to do one of these

First option's first option (promote to USACO silver in a previous previous contest and promote to USACO gold in a previous contest after the first contest), to do this you must: - not promote to USACO silver in any previous previous previous contest

First option's second option (promote to USACO silver with a perfect score and promote to USACO gold in the same previous contest), to do this you must: - not promote to USACO silver in any previous previous contest

Second option's first option (promote to USACO silver in a previous contest), to do this you must: - not promote to USACO silver in any previous previous contest

Third option's first option (not promote to USACO silver in any previous contest), to do this you must: - not promote to USACO silver in any previous previous contest

Im still an idiot but now you know how to make USACO platinum (from experience) good luck guys!

btw iclearhouses is my pretty pink princess!

top 8 tips oat 1. if ur doing bad in contest stop doing bad so u can do good in contest 2. if ur not sleeping before contest, sleep because then u will have sleep and it will let u have the sleep for contest 3. if u cant pass usaco bronze, start doing usaco platinum so bronze problems will be easy 4. if u cant pass usaco silver learn lazy segment trees. it solves (100^100)% of silver problems 5. if u dont know what an xor operator is, learn from tip 4 6. if u hardstuck on 800 problems give up and become a doctor 7. if u have a rating of 1954 and a high of 2021 ur the greatest cper oat 8. if u dont have tip 7 u should quit and go into business