Good Bye 2023 tutorial

11 months ago, # |

← Rev. 2 →

-16

Can anyone explain C to me, I couldn't understand it at all

→ Reply

azureglow

11 months ago, # ^ |

it's sad:(

→ Reply

11 months ago, # ^ |

why ?

→ Reply

11 months ago, # ^ |

+13

let there be m total numbers and total sum = sum out of those m numbers x numbers are odd not that which ever player's turn it is does not matter the new number added to the array is as ((a[i] + a[j]) / 2) / 2 is even so if a[i] and a[j] are of same parity the score will reamain same but if a[i] and a[j] are of different parity then the score decrease by 1 so for first player it is optimal to choose a[i] and a[j] of same parity (more specifically both should be odd) and for second player will chose ai and aj of different parity. you might have a question why first player tries to choose ai and aj both. it is because if he choose both odd then there will be fewer chance of the second player choose different parity numbers. so if there are X odd number then the first player will choose 2 odd numbers and insert an even number total score remain same SUM. X -> X — 2 now the second player will chose 1 odd and 1 even score will become SUM — 1 and X -> X — 3. now this pattern will continue till X >= 3 if X is 2 then first player will both odd numbers and the score remain same SUM. if X = 1 then the it has to be chosen atleast once so the score will decrease by 1 SUM -> SUM — 1. simple formula to calculate this is ans = (SUM — (X / 3) — ((X % 3) % 2)). hope this helps. here is my submission 239685245 to understand better what i'm saying. please forgive my english

→ Reply

11 months ago, # ^ |

I have a similar code, can I send it to you?

→ Reply

11 months ago, # ^ |

yes share it here

→ Reply

11 months ago, # ^ |

← Rev. 2 →

int a[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n==1){
        cout<<a[1]<<endl;
        return;
    }
    if(n==2){
        cout<<a[1]<<' '<<(ll)((a[1]+a[2])/2)*2<<endl;
        return;
    }
    cout<<a[1]<<' '<<(ll)((a[1]+a[2])/2)*2<<' ';
    ll even=0, odd=0;
    if(a[1]&1) odd+=a[1];
    else even+=a[1];
    if(a[2]&1) odd+=a[2];
    else even+=a[2];

    for(int i=3;i<=n;i++){
        if(a[i]&1) odd+=a[i];
        else even+=a[i];
        if(odd&1) odd--;
        else cout<<odd+even<<' ';
    }
}

What am I wrong here?

→ Reply

11 months ago, # ^ |

as much as i can understand you code you subtracting 1 from ans for each odd number but have to subtract 1 for every 3 odd numbers

→ Reply

11 months ago, # ^ |

if the sum of the odd numbers is odd, then I decrease the sum of the odd numbers by 1. You say it should be done every 3 odd numbers. I didn't understand why

→ Reply

11 months ago, # ^ |

← Rev. 2 →

for even numbers no affect on the final result but for odd there is two steps done repletely which are

1 — choose 2 odd and do the operation to don't waste it's value

2 — choose 1 odd + 1 even and do operation to decrease the value by 1

so here we get that there is decreasing by 1 per 3 odd numbers also you can check my answer 239675910

→ Reply

11 months ago, # ^ |

Thank You so much :)

→ Reply

11 months ago, # ^ |

input: 5 7 13 11 19 1

output: 7 20 30<- okay but after 48 why not 50 ? 7, 13, 11, 19 7+13 11+19 20+30=50 WHY ?!

→ Reply

11 months ago, # ^ |

suppose there are 6 odd number 1 3 5 7 9 11 First -> remove 9 11 insert 20 A = {1 3 5 7 20} Second -> remove 7 20 insert 26 A = {1 3 5 26} First -> remove 3 5 insert 8 A = {1 26 8} Second -> remove 1 and 26 insert 26 A = {8 26} First -> remove 8 26 insert 34 A = {34} ans = 34 notice that there are 6 odd numbers first first 2 turns SUM decresed by 1 then for next 2 turn SUM decrease bu 1 ans = (36 — (6 / 3) — ((6 % 3) % 2)) = 34

→ Reply

11 months ago, # ^ |

I wrote it a little differently but it was accepted

int a[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n==1){
        cout<<a[1]<<endl;
        return;
    }
    if(n==2){
        cout<<a[1]<<' '<<(ll)((a[1]+a[2])/2)*2<<endl;
        return;
    }
    ll sum=0, odd=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(a[i]&1) odd++;
        if(i==1) {
            cout<<sum<<' ';
        }
        else{
            if(odd==3) {
                --sum;
                odd=0;
            }
            if(sum&1) cout<<sum-1<<' ';
            else cout<<sum<<' ';
        }
    }
}

→ Reply

11 months ago, # ^ |

great continue upsolving GL&HF

→ Reply

11 months ago, # ^ |

Thank You so much too :)

→ Reply

Nandan1436

11 months ago, # ^ |

This was a very good explanation. Thank you. It was helpful.

→ Reply

11 months ago, # ^ |

Thanks! Happy new year

→ Reply

quater_nion

5 weeks ago, # ^ |

How can one make a formula out of all this information during the contest??

→ Reply

THE_THUNDERSTORM_BEGINS

11 months ago, # |

-18

Wanderfull round guys. People who are downvoting everything are a punch of noobs actually

→ Reply

11 months ago, # |

← Rev. 3 →

-35

[ Deleted ]

→ Reply

Ianlsam

11 months ago, # ^ |

can u stop whining everywhere bruv, we get it but this is the editorial

→ Reply

11 months ago, # ^ |

← Rev. 3 →

-27

[ Deleted ]

→ Reply

Ianlsam

11 months ago, # ^ |

← Rev. 3 →

+13

wdym lmao, go cry about it in the announcement or something, there has already been enuff complaints , bruh this shit is past and irrelevant, in the editorial at least

→ Reply

ABDTTWBWJ1

11 months ago, # ^ |

← Rev. 2 →

-23

[ Deleted ]

→ Reply

Rushdi

11 months ago, # ^ |

it's clear that you're Folka but in 2nd account

→ Reply

details about the cardinal of the stab

11 months ago, # ^ |

I don't even have any other accounts!

→ Reply

Rushdi

11 months ago, # ^ |

ok maybe I'm wrong idk

→ Reply

red.frost24

11 months ago, # |

Just a request If you are going to make this contest unrated, do it this year itself please. I understand why most people are unhappy with the contest and therefore I am fine with it being converted to an unrated one. But I also don't want to end 2023 with a rating of 1383 and then wake up in 2024 seeing myself back at 1270. So this was just a request, hope you consider it :)

→ Reply

Steven-_-AbuAlkhair

11 months ago, # |

Can anyone prove this to me or explain why?

In this case, b=a⋅p, where p is the smallest prime factor of x. Then x=b⋅p=b⋅ba

→ Reply

123gjweq2

11 months ago, # ^ |

← Rev. 5 →

So (b mod a = 0) means that a is a divisor of b. If b and a are the first and second biggest divisors of some number x respectively and a is a divisor of b, a must be the greatest divisor of b. To show by contradiction: assume a isn't the greatest divisor of b. Then there is some middle number between a and b, call it c, which divides b. Since x % b = 0, x % c must be = 0, and a and b wouldn't be the first and second largest divisors of x.

Now how do you find the greatest divisor of b? By dividing b by the smallest divisor of b, which will always be the smallest prime factor of b, call it p. So a = b/p, or b = ap.

Now we show that, assuming b and a are the first and second greatest divisors of some number x and b % a = 0, one solution for x = bp.

We will show that, assuming x = bp and b % a = 0, the second greatest divisor a = b/p.

Since p is the smallest prime factor of b, p is also the smallest prime factor of bp. So in order to get the greatest divisor of bp, we just divide by p. Our greatest divisor of x = bp is b, which is what we want.

Now we are left with b as the greatest divisor of x = bp and we can pull out another smallest prime factor of b to get b/p = a. And so a is then the second greatest divisor of bp. Or is it?

What if our smallest prime factor of b is p = 2 for example but our second smallest prime factor of b is s = 3? Then surely we would have a = bp/s = 2b/3 rather than bp/p^2 = b/2, right?

Well let's assume that the second greatest divisor, a, of x = bp is bp/s rather than bp/p^2. Recall that, in this case, a = bp/s must be the greatest divisor of b. So b/(bp/s) must be an integer. b/(bp/s) = s/p which is not an integer since s and p are both primes. So a = bp/s doesn't work. s can be generalized to any single prime factor of b where s > p.

And of course, when dividing by two prime factors of bp to find a, it will always be correct to divide by the two smallest primes, which is p^2, otherwise a wouldn't be the second greatest divisor.

Now we have shown that, for the case where b % a = 0, one solution for x = bp where p is the smallest prime factor of b. And since a is the greatest divisor of b, we can compute this easily by doing b^2/a.

Hope this helps. I guessed the solution in the contest and thought about it later and realized it had a nice little proof.

→ Reply

Shubhan_Singh

11 months ago, # ^ |

← Rev. 2 →

What if our smallest prime factor of b is p = 2 for example but our second smallest prime factor of b is s = 3? Then surely we would have a = bp/s = 2b/3 rather than bp/p^2 = b/2, right?

here you mean to say a=bp/ps and not a=bp/s, right?

please ignore this comment, i had misread and codeforces isn't letting me delete this

→ Reply

123gjweq2

11 months ago, # ^ |

← Rev. 3 →

I meant to say a = bp/s because if a were bp/ps = b/s then a wouldn't be the second greatest divisor of bp since there is b/p > b/s and bp % (b/p) = 0.

In this part of the explanation I was basically showing why a cannot be bp/s.

Edit: haha ok I see your edit too. Unfortunately codeforces doesn't let you delete comments lol

→ Reply

Roronoa__Zoro

11 months ago, # |

Don't just write the statement (for this case, the answer is this and for that it is that) . Prove your Solution ,that is what editorials are for.

→ Reply

bestial-42-centroids

11 months ago, # |

+43

My proof for problem H doesn't use any generating function and I find it more natural. I have very bad latex skills so I couldn't really manage to write everything so I'll link some pictures of my draft if someone is interested in the computations.

Disclaimer: I don't do math in english so my wording might be inaccurate sometimes (although I think you should roughly get the idea if you're familiar with the concepts I'll use)

The general idea is the following:

Let $$$S_r = {\{M \in \mathbf{Mn(\mathbf{F_q})} | rank(M) = r\}}$$$.

We are interested in the cardinal of $$$S_r$$$. As the constraint is on the rank of the matrix, it's pretty reasonable to solve this by considering equivalence classes.

Let's consider the group morphism:

$$$(P, Q) -> (M - > PMQ^{-1})$$$

where P and Q are in $$$\mathbf{GLn(\mathbf{F_q})}$$$.

It is a group action.

The orbits of this action are fixed by the rank (two matrixes are equivalent iff they have the same rank, this is a consequence of the rank theorem (more specifically, the fact that restricting a linear application to a supplementary of the Ker gives an isomorphism)).

Having this group action in mind, we get that

$$$|S_r| = \frac{|\mathbf{GLn(\mathbf{F_q})} \cdot \mathbf{GLn(\mathbf{F_q})}|}{|Stab_r|}$$$

(my cdot here should be an x but idk how to type this :/)

Now, to compute $$$|Stab_r|$$$, the easiest matrix to pick is $$$J_r$$$ (the canonical representant of the equivalence class of matrixes of rank r, a matrix that has 0 everywere and 1 on the first $$$r$$$ positions of the diagonal).

Now, $$$P, Q$$$ are in $$$Stab_r$$$ iff P Jr = Jr Q

I'm unable to type the whole thing because my latex is bad but essentially it is just about writing P and Q as block matrixes (with dimensions matching Jr), it gives an isomorphism between the stab and:

$$$GLr(Fq) \cdot GL_{n-r}(Fq) \cdot GL_{n-r}(Fq) \cdot M_{n, n - r}(Fq) \cdot M_{n - r, r}(Fq)$$$

(again the cdots should be x)

Now you're only left with some powers of q and some cardinal of $$$GLn(F_q)$$$ to compute.

This is easy to compute as we can see a matrix M in GLn(F_q) as a free family of n vectors of the space (F_q)^n (so a basis).

Thus, by the usual basis construction process, there are q^n — 1 possibilities for the first vector (everything except 0), then q^n — q possibilities for the second vector (everything that is not in the subspace generated by the first vector), then q^n — q^2 for the third etc

details about the final result

→ Reply

JeanBombeur

11 months ago, # ^ |

← Rev. 3 →

+49

Alternatively, to obtain a matrix $$$n \times m$$$ of rank r over $$$F_p$$$, you can :

Choose a subspace of $$$F_p^n$$$ of dimension r : there are $$$(p^n - 1) \cdots (p^n - p^{r - 1})$$$ ways to choose $$$r$$$ independent vectors, but each subspace is counted once for each of its basis, of which there are $$$(p^r - 1)\cdots (p^r - p^{r - 1})$$$
Given a basis of this subspace, you need to choose $$$m$$$ vectors in $$$F_q^r$$$ such that the resulting subspace is of dimension $$$r$$$, which is the same as choosing $$$r$$$ vectors in $$$F_q^m$$$ such that the resulting subspace is of dimension $$$r$$$ (this can be seen by swapping the rows and columns of the matrix). Therefore you have $$$(p^m - 1)\cdots(p^m - p^{r - 1})$$$ possibilities

In the end, you get the wanted formula $$$f(n, m, r, p) = \displaystyle\prod_{j = 0}^{r - 1} \frac{(p^n - p^j)(p^m - p^j)}{p^r - p^j}$$$ which can be trivially calculated in $$$\mathcal{O}(r)$$$ and easily in $$$\mathcal{O}(1)$$$ amortized over $$$r = 0 \ldots k$$$

By the way very nice draft pictures and even nicer profile picture !

→ Reply

bestial-42-centroids

11 months ago, # ^ |

+10

orz, I think this is roughly the same thing except you implicitly compute the cardinal of the stabilisator which makes things easier

I guess the power of a Jambon beurre is unfathomable

→ Reply

jonnnnnsinaga

11 months ago, # |

What's the proof for n+2 in problem D? When we have 2 number rhat we should fill??

→ Reply

11 months ago, # |

← Rev. 2 →

Here in problem B, I Understand the toturial and the code. But I don't know WHY ? okay we have two cases:

case 1 where (b%a != 0) , here LCM is the answer. but why? why X= LCM? Can't it be X>LCM or X<LCM ? WHY X=LCM ?

case 2 where (b%a == 0), Here we assume that there is a smallest factor P of X. Then we assume that this smallest factor of X makes the following rerlation (b= P.a) valid ..WHY ? Then we assume that X=b.P WHY?

IS there some mathimatical proof or only intuation?

→ Reply

bcollet

11 months ago, # ^ |

+10

If d divides x then x/d divides also x. a and b are the biggest divisor smaller than x. Conversely x/a and x/b are the smallest divisor bigger than 1. Here two cases are possible : either they are two DIFFERENT prime factor p and q, this corresponds to case 1. Either they are p and p^2 which correspond two case 2.

→ Reply

11 months ago, # ^ |

← Rev. 2 →

first, thank you bro for replying.

I get that If there are two largest factors (a , b) of (X), Then (q=X/b ,p=X/a) are the two smallest factors.

here you say "either they are two DIFFERENT prime factor p and q"

but the question did not obligate a a&b to be primes, much less p,q. I didn't understand this point. please explain more

→ Reply

vgtcross

11 months ago, # ^ |

← Rev. 2 →

Okay, you understand that $$$p$$$ and $$$q$$$ are the two smallest factors greater than $$$1$$$ of $$$x$$$.

but the question did not obligate a a&b to be primes, much less p,q. I didn't understand this point. please explain more

The fact that $$$p$$$ is prime and $$$q = p^2$$$ or $$$q$$$ is prime is just a general property of the two smallest factors greater than $$$1$$$ of any integer (that has two such factors). Here is the proof:

Claim: $$$p$$$ is prime.

Proof (by contradiction): Suppose $$$p$$$ is the smallest factor greater than $$$1$$$ of $$$x$$$ and $$$p$$$ is not prime. Since $$$p$$$ is not prime, it can be represented as $$$p = st$$$ for some integers $$$1 < s, t < p$$$. Now, $$$s$$$ is a factor of $$$p$$$ and $$$p$$$ is a factor of $$$x$$$; thus $$$s$$$ is a factor of $$$x$$$. But $$$s < p$$$, so $$$s$$$ is a smaller factor than $$$p$$$ — a contradiction. Thus, $$$p$$$ must be prime.

Claim: Either $$$q = p^2$$$ or $$$q$$$ is prime.

Proof (by contradiction): Suppose $$$q$$$ is the second smallest factor greater than $$$1$$$ of $$$x$$$, $$$q \ne p^2$$$ and $$$q$$$ is not prime. Since $$$q$$$ is not prime, it can be represented as $$$q = uv$$$ for some integers $$$1 < u, v < q$$$. If $$$u = p$$$ and $$$v = p$$$, then $$$q = p \cdot p = p^2$$$ — a contradiction. Otherwise, either $$$u \ne p$$$ or $$$v \ne p$$$. Now, both $$$u$$$ and $$$v$$$ are factors of $$$q$$$ and $$$q$$$ is a factor of $$$x$$$; thus $$$u$$$ and $$$v$$$ are factors of $$$x$$$. But $$$u < q$$$ and $$$v < q$$$, so $$$u$$$ and $$$v$$$ are smaller factors than $$$q$$$. One of them might be equal to $$$p$$$ which we already considered but one of them must be not equal to $$$p$$$ but instead, be a new, smaller factor of $$$x$$$ we didn't yet count — a contradiction, since $$$q$$$ was meant to be the second smallest factor. Thus, $$$q$$$ must be prime or $$$q = p^2$$$.

→ Reply

11 months ago, # ^ |

← Rev. 2 →

@vgtcross fantastic! thank you, bro. I'm presuaded that p must be prime and q must be either prime or p^2.

and form above, @123gjweq2 proved that ifb%a=0 and are the two greatest divisors of X, then a is the greatest divisor of b. Thenb/a gives the lowest divisor of b, which he assumed to be the lowest divisor of X which is p.

which gives the following equation: p= b/a thenx/b=b/a then x=b^2/a. All is well, if we proved that assumtion that the lowest factor of b is the same as the lowest divisor of X.

→ Reply

amansingh81757

11 months ago, # ^ |

For case 1 it is the lcm of a and b due to the reason that the lcm will be the smallest number to exist for a and b such that both a and b are its factors. get it?? that is like the definition of lcm.

for the second case we assume p is the smallest factor of X because it is given that b will be the largest factor of X. therefore by this relation b*p = x as b is the largest factor p has to be the smallest factor. for example for x = 64 its factors(except 1 and 34 ofcourse) are: 2, 4, 8, 16, 32. to make 64 we take one factor from left (2) and one from right (32) and so on.

→ Reply

11 months ago, # ^ |

first, thank you bro for replying.

LCM of a and b is the smallest number that can be devided by the two factor (a,b) of a givin number (X). But what problem B here asks us is to give him the number with largest two factors a,b . then we deducte that X can be devided by a and b. and LCM is the smallest number that can be divisable by a and b. But can we deducte that a and b will be the greatest divisors?

I feel there is a strong relation, but I don't see why LCM MUST be used logically or mathimatically?

here is an example, 63 has the following factors: 1 3 7 9 21 63 the largest two factors here (21,9) okay?

but if I give you (7,9) with your definition, you will give me 63, but 63 has (21,9) as largest divisors not (7,9)

do you see what I'm trying to get to?

→ Reply

SXZZ5

11 months ago, # ^ |

Your doubt is very valid. I see what you are trying to get to.
However the problem statement is not asking for a $$$x$$$ in such a general sense for any given $$$a < b$$$. The statement is more like: "If I take the guarantee that $$$b$$$ and $$$a$$$ ARE CERTAINLY the two greatest divisors of some $$$x$$$. Can you find that $$$x$$$ for me ?"

If you understood what I mean you will also understand that although you can calculate an answer for the case $$$(7,9)$$$, it is not a valid test input.
That is to say the case $$$(7,9)$$$ is beyond the scope for the problem.

→ Reply