Hello! Codeforces Round 828 (Div. 3) will start at Oct/16/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of **open hacks**.

You will be given **6-8 problems** and **2 hours and 15 minutes** to solve them.

Note that the **penalty** for the wrong submission in this round is **10 minutes**.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participant of the third division*, you must:

- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work, pashka for help with ideas for problems and for coordination of my work. Problems have been created and written by MikeMirzayanov, 74TrAkToR and pashka.

We would like to thank: Gornak40, meowcneil, Vladosiya, senjougaharin, efimovpaul, powergee101, tanus_era for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

**UPD**: Editorial

As an enthusiastic coder, I will comment first :)

Finally, my first Unrated

Div.3!!But imagine what might happen...

Spoilerplot twist: the rating for global #23 gets applied and suddenly you become rated

I'll go at least +30 in

Global 23, soNo, still Unrated...Oh well, congrats! Hope you have fun on your first unrated Div.3

Spoileryes i did forget to look at the predictor

Thanks!

It's better.

Classical + Mathematics

Can anyone tell me why I am getting TLE on this submission? https://mirror.codeforces.com/contest/1665/submission/176381750

Use map instead of unordered_map

But unordered_map operations have time complexity O(1) which is less than map operations time complexity O(logn). How this worked?

This is due to collisions. When the collisions become more then it generally takes O(n) for an operation in unordered_map Read this blog for clarity https://mirror.codeforces.com/blog/entry/62393

Fell down below 1600 due to FST. Getting a chance to rise, the very next day! Thanks!

aaaaaa

Source

-_-

-_-

Wow, I thought to give Div3 Tommorow but became an Expert today :)

SpoilerSuffering from Success

become specialist

The current number of upvotes is 74, and the announcement was sent by 74traktor. Leave a message to commemorate it.

Quick, upvote this comment so when it has +66, we can commemorate it as well!

I don't really care about that, but 74traktor is a very high level coordinator, and we're working with him, and I think the problems he set must be great.

SpoilerHoping for Positive Delta.

It is so good that contest are hold often :)

Wishing everyone positive delta, although that is technically impossible.

I think the number of participants will be less than the average due to EL CLASSICO time which is the same as the round

Spoilerwell i am one of the people who will watch the match and not participate but i am already unrated LOL

GL everyone !

Good Luck!!

Custom Invocation is broken, runs forever.

Did 6/7, but the overall user experience is rather poor compared to Leetcode. Custom invocation was crushing for the first hour, making it impossible for me to test my solutions. Sure I can get an external interpreter which I guess I will have to do next, meh. Adding a dedicated problem discussion would be really nice, to compare ideas and solutions.

These math rounds always make me revisit my high school math. Nice questions though

Hint for E1 Please

HintBruteforce $$$x$$$ on $$$(a,c]$$$. You can find a lower bound of $$$y$$$ using the LCM of $$$ab$$$ and $$$x$$$. Now the actual value of $$$y$$$ has to be a multiple of that lower bound.

I almost got it :((( but is this problem we have to find lcm?

no you have to divide a*b by gcd(a*b,x). This gives minimum value of y, now find if there exits a multiple of minimum y in the range (b,d]

gcd(xy, ab) = ab -->

y * gcd(x, ab) = ab--> y = ab/gcd(x, ab).Is this how you deduced the formula? If so, is it a know fact that you can factor a number out of a gcd expression (bolded part) or did you just figure that fact out on your own?

No, I don't think the formula gcd(xy,ab) = y*gcd(x,ab) holds true. For x=2,y=3,ab=2 gcd(xy,ab) = gcd(6,2) = 2 y*gcd(x,ab) = 3*gcd(2,2) = 3*2 = 6

The way i approached this problem is : iterating x from a+1 to c, now finding the minimum y such that xy divides ab, now finding if any multiple of miny exists in range (b,d]

I got it! Thankyou!

Bruh!! after that? I have a gut feeling that it is going to be insanely easy

got it, thanks As I guessed, it is insanely easy

check for all possible x(or y).

I used sieve. You can also think of solving it with sieve

How to solve problem E2?

Think about prime factorization of a * b

x must be divisible by the product of any divisor of a and any divisor of b. So for all divisors of a and b check if there is a corresponding x and y or not

Video Solution for E2.

how to solve problem d??

Some number $$$m$$$ is divisible my $$$2^n$$$ if it has $$$n$$$ twos when you break it down into prime factors.

Firstly you need to count the number of twos in product of all numbers in $$$a$$$. If there is less then $$$n$$$ twos, you will need to multiply some numbers by $$$i$$$. It is best to multiply with $$$i$$$ s with most twos when you break it down into prime factors first. When you have number of twos greater than or equal to $$$n$$$ you are done. You just need to output have many times you multiplied with $$$i$$$.

My submission: 176530693.

As an alternative way (simpler implementation), you can generate an array of all numbers in $$$[1,n]$$$, sort them in decreasing order by the number of trailing zeroes they have in their binary representation (this is essentially the same with the number of $$$2$$$ in its prime factorization), and do a simple iteration on it. My submission is 176524669.

Please help me with this solution. I pretty much did something similar but it got hacked 176544364

You are iterating over an array of size $$$2\times 10^5$$$ on every test case. This is $$$O(NQ)$$$ (given $$$N=2\times 10^5$$$). You need to reduce this number of iterations to $$$n$$$ on each testcase, to use the fact that the sum of $$$n$$$ in all test cases is not bigger than the maximum value possible.

178050351 chromate00 please help me to see why my submission is wrong, I can not understand, thank you very much

It's hard to exactly point out the issue on this solution, but I think it should be an overflow issue. (You could use addition instead of multiplication in this problem.)

Thank you for having wonderful Div 3 Test. Thanks to all concerned who organized the test.

It is to inform that in Question "E1 Divisible Numbers (easy version)" I have submitted my code in python.

In third test, there is a possible answer 9 16. But autorun rejected my code on test 3. It is informed that it is valid answer as per your conditions. Kindly check and please accept my code. You can restrict the answer if there are multiple answers.

Thank you.

It says Test 3, not the subtest 3 of test 1.

how to solve E2 ?

it's not hard you need the a*b divisors but since it's too large you could get the divisors of a and b and then multiply each two elements of both numbers divisors and put it in the array of a*b divisors and the rest is the same

can anyone please tell me why in question D in this case 4 13 17 1 1 the answer is -1 after (13⋅1)⋅(17⋅2)⋅(1⋅3)⋅(1⋅4) this operation for 1 time if i choose i=2 and do (17,2) again then what will be the total number of factor in the multiplication there will be 4 factor of 2 and the multiplication is divided by 2^n as n=4 here so why the answer is -1 here as here it is said i can do the operation as many times but in each operation the chosen index should be different?

You cannot apply the operation repeatedly to a single index. In other words, all selected values of i must be different.I guess, you didn't pay attention to this sentence.The statement stated that you can apply the operation on each index only once.

You can do at most $$$n$$$ operations. You can't choose any $$$i$$$ more than once.

I don't quite understand how to solve e1 :(

I think my solution for E1 is hackable, can anyone try to hack it?

https://mirror.codeforces.com/contest/1744/submission/176559805

Anyone here who knows Java and has solved Traffic light problem?

Why are you assuming n is a digit?

Hello guys. I want to cry. LOOK AT THIS PLEASE. I just send this code in the round and it got TL (problem D).

But now, I send this, and it got "OK". Can someone answer me — "WHY?":

You overflow

pr. So it presumably become 0 and now you have infinite loopThank you very much.

Such a unlucky contest for me. Spent more then 90 minutes combined on $$$A$$$ and $$$C$$$ trying to figure out why I am getting WA, reimplemented both problems in a little different way and got AC...

I Wanna shoot my HEAD .. I spent half an hour trying to understand wtf is wrong with my E2 Solution and in the end I realized i wrote in the for loop divo2.size() instead of j<divo2.size() .. I wanna **** my stupid code .

after reading your code I also want to shoot your head

I would say shoot yours but it's empty

https://mirror.codeforces.com/contest/1744/submission/176594390

can anyone show me a testcse where my solution not fits?(problem c)

You can print the specific test case by modifying your code.

I liked B, especially D.

Solved the last task of the round for the first time!!!!!! Indeed its a new exciting day!

What is your approach for problem F?

Well,

First realize that for MEX > MED, the first t elements should be 0 1 2 ... t-1

Now, save the tighest bounds for {0} ,{0 1}, {0 1 2}, ... using two arrays, to be used on demand

Iterate on t [from 1 to (n+1)/2 ]

The sub array size could be 2t or 2t-1 and so, calculate the left and right slacks, you can get the possible number of subarrays for this t.

I felt the base testcase which they gave was veryy good, I corrected 4~5 bugs using it.

How did this solution get hacked? 176544364 I'm certain my solution was correct. For every power of 2 I will take the largest 2^i which costs me 1 unit and gives me a lot of 2's. Even positions will also give me 1 unit of cost for a single 2. I combined both and sorted based on largest 2 giver. Then took prefix count.

When the condition

`twos >= n`

is fulfilled, you always iterate over all`two`

array:`for (auto [i, j] : two)`

. So complexity of your solution is $$$O(t M)$$$, where $$$M = 200000$$$. So, it is obvious that this solution will most likely get TL.One of the hacks that works for E1: 10 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 99999 100000 100000 1 99999 100000 100000 1 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000

176594240 It says that my answer is wrong in 17th test case but when I am running on my compiler and other online compiler I am getting correct answer. Someone please help my solution was correct still I had to stuck in this question because of this error. Thank you in advance!

Don't use floating point operations unless you have a concrete proof that the result will be exact.

At least, your rounding

`(long long int)log(...)/log(2)`

doesn't always work...Why isn't there score distribution in Div.3 and Div.4 rounds like in Div.2 and Div.1 rounds?

Because Div. 3, Div. 4 and Edu rounds follow ICPC rules

It follows the format of Extended ICPC, meaning that rank is first determined by solve count, and then by penalty. Still, there is a reason why solving (subjectively) easier problems first is more beneficial. We need to understand that the penalty is the sum of the penalties on each problem. Now to simplify things, lets assume you can solve A in $$$5$$$ minutes and B in $$$10$$$ minutes, and there are no more problems than these two. If you solve A first, the penalty will be $$$5+(5+10)=20$$$ minutes. However if you solve B first, the penalty will be $$$10+(10+5)=25$$$ minutes. Therefore in this simplified model, solving the easier one first is ideal. We can generalize this to more than 2 problems, and understand that it is ideal to solve problems in increasing order of difficulty.

I know what format of Extended ICPC means, but why format of Div.2 rounds isn't used?

I wish I knew. IIRC Div.3 was planned to be Ex-ICPC format from its first round and on, but I don't exactly know why they decided it that way.

Solution for F:

Enumeration $$$i$$$ from $$$1$$$ to $$$n$$$,consider subarray $$$Sub$$$ which's median is $$$a[i]$$$.

To make $$$MEX(Sub)>MED(Sub)$$$,$$$1,2,...,a[i]∈Sub$$$ must be hold.

Use binary search to find the min subarray $$$Sub_{min}$$$,which contains $$$1,2,...,a[i]$$$.

Next,we have to make sure that $$$a[i]$$$ is the median.We can add some numbers on the left and right sides of $$$Sub_{min}$$$ to achieve it.Then we can easily count it.

nice problems

Can you rise TL on E? So many hacks by TL, that should not happened

Nvm, i am just fcking stupid...

How to solve E2? Can someone explain in a easy way?

You can get the prime factors of a, and b. Then create every possible pair of numbers with those factors.

For example, if a = 2^2 * 3, b = 2^3 * 5, then a*b = 2^5 * 3 * 5. all possible pairs are

1 480

2 240

...

In the end, check if the pair has the constraints. (if x <= a, then make x to (a/x + 1)*x).

Prerequisite: Maximum number of divisors of n if $$$ n \leq 10^9 $$$ is 1344, you can refer oeis and this comment.

So first calculate all divisors of a and b. And iterate over all possible pairs of divisors of a and b, be l and m. Try to set x as multiple of l*m and y as a multiple of $$$ \frac{a*b}{l*m} $$$

Overall complexity would be : $$$ O(\sqrt{A}+\sqrt{B}+A^\frac{1}{3}*B^\frac{1}{3}) $$$

Epic tests for problem E1, thank you!

10 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 99999 100000 100000 1 99999 100000 100000 1 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000

I hacked 31 Solutions of E1 problem using this testcase.

Unfortunately.your solution on E1 has been hacked:(

rainboy Can you please explain your solution for Question 1744F - MEX vs MED ?

I could have been an expert, but my E1 got hacked...TAT

A job is free for you, 15$ per hour during contests so you remind me to use long long for all variables.

The second contest this week I get WA because one of the variables is int

can anyone help me debug C? https://mirror.codeforces.com/contest/1744/submission/176567867 found it

Why do you set first to true when i==n?

What about rgr?

View your code on a mobile phone without custom test. Forgive me if I were wrong.

Editorial?

hello phineas

Hello pussy cat

meow

isn't it a rated contest? When it will changes our rating?

I guess, tomorrow at the latest (2 div3 contest ago they took 1 day to update rating, as cheaters were being eliminated)

Why is this code only gives YES as output?

## include <bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while(t--){ int n,k=0; string s; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } cin>>s; map<int,char>m; for(int i=0;i<n;i++){ auto it = m.find(a[i]); if(it==m.end()||s[i]==(*it).second){ m.insert(pair<int,char>({a[i],s[i]})); } else{ k++; } } if(k==0){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } return 0; }

Comment out Yes. It will produce only No

How to solve F ?

Assume a segment s of size k. To have mex(s) > med(s), s must atleast have the elements 0, 1, 2, ..., k/2. With this knowledge, we can now keep track of the index at which each p_i occurs, Now we iterate k from 1 to n, and maintain two variable l and r to keep track of the leftmost and rightmost index between which 0..k/2 are located. If r-l+1 > k, then we have no good segments of size k. Else the number of good segments would be given by min(l, n-k) — max(0, r-k+1) + 1. The expression above is simply the number of segments of length k that contain the range l..r

You can see my submission here: https://mirror.codeforces.com/contest/1744/submission/176616730

Why is this code giving tle? it was working fine in the local editor code-my submission

E2 passed , E1 failed :(

I'm talking about the coincidence with the decisions of other participants. This is not fair, I wrote the code completely by myself, it took more than an hour.

You can see the evolution of my code and attempts. I do not understand at all how someone could copy my code, please do not ignore my attempts, since this is only my second contest in the rating. I have not logged into my account for a long time, I will try to change the password. Please at least update my rating, i been waiting all day for this and at the end of this. Next time I'll be more careful with my account. https://mirror.codeforces.com/contest/1744/submission/176557816 https://mirror.codeforces.com/contest/1744/submission/176570918 https://mirror.codeforces.com/contest/1744/submission/176579287 https://mirror.codeforces.com/contest/1744/submission/176580294WHat happened? I cant understand

How to solve the problem of E1????

My naive solution was , iterate on x from a+1 to c and try to calculate y by taking x.y = a.b.1 or a.b.2 or .....

This passed the system tests at first, but got hacked later on

It is so pity

too ez! try harder next time.

How to solve problem B? I get TLE on test 5

Just have one variable for the sum of whole array. You also need to keep track of number of odd elements and number of even elements. If you iterate over the array every query that will be $$$O(nq)$$$ which is too slow.

At the beginning you need to count the number of odd and even numbers in an array and calculate the sum. In every query will add $$$x$$$ multiplied by number of odd/even numbers to the sum. Note that number of even and odd numbers changes so try to update those numbers without iterating over the whole array. Try to think about the parity of

$$$2k+2k$$$,

$$$2k+(2k+1)$$$,

$$$(2k+1)+(2k+1)$$$

to calculate new number of even and odd numbers after each query.

How hacking will increases your points in div 3 or educational round Like in general div 2 round it will increases your point by 50.

Getting hacked sucks! I fell from rank 200 to 1000... Regardless...the round was GG

can someone explain the E2 for me,I got no idea on this problem,thx!

E2 is quite simple. You first use Sieve to find all the primes in the range 1 to max(sqrt(a)+1,sqrt(b)+1). Then, you do prime factorization on both a and b and push back all of them into a vector. After that just use somewhat like a knapsack dp to find all the factors of a*b. Try if the pair of factors can fit into a<x<=c and b<y<=d by multiplying a constant k. If it is possible output the answer, else output -1 -1.

finally Expert!!!

Hi, can anyone please help me with my solution to D solution. I've been debugging it for some time, but idk whether it is the way I found largest power of 2 below n gives the wrong answer. Thanks a lot in advance!

Take a look at Ticket 16394 from

CF Stressfor a counter example.nice round