Привет! В 16.10.2022 17:35 (Московское время) начнётся Codeforces Round 828 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией моей работы, pashka за помощь с идеями для задач и координацией моей работы. Задачи были придуманы и написаны MikeMirzayanov, 74TrAkToR и pashka. Также стоит отметить, что в этот же день будет проходить командная олимпиада ЮМШ, где будет большая часть задач раунда.
Также большое спасибо: Gornak40, meowcneil, Vladosiya, senjougaharin, efimovpaul, powergee101, tanus_era за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.
Всем удачи!
UPD: Разбор
As an enthusiastic coder, I will comment first :)
Finally, my first Unrated Div.3!!
But imagine what might happen...
plot twist: the rating for global #23 gets applied and suddenly you become rated
I'll go at least +30 in Global 23, so No, still Unrated...
Oh well, congrats! Hope you have fun on your first unrated Div.3
yes 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://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://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 :)
Suffering from Success
The current number of upvotes is 74, and the announcement was sent by 74traktor. Leave a message to commemorate it.
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.
Hoping 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
well i am one of the people who will watch the match and not participate but i am already unrated LOL
GL everyone !
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
Bruteforce $$$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.
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 think my solution for E1 is hackable, can anyone try to hack it?
https://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).
for (int i = 0; i < n; i++) { cin >> a[i]; pr *= a[i]; } while (!(pr & 1)) { k++; pr >>= 1; }But now, I send this, and it got "OK". Can someone answer me — "WHY?":
for (int i = 0; i < n; i++) { cin >> a[i]; while (!(a[i] & 1)) { k++; a[i] >>= 1; } }You overflow pr. So it presumably become 0 and now you have infinite loop
Thank 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://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 >= nis fulfilled, you always iterate over alltwoarray: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://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://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://codeforces.com/contest/1744/submission/176557816 https://codeforces.com/contest/1744/submission/176570918 https://codeforces.com/contest/1744/submission/176579287 https://codeforces.com/contest/1744/submission/176580294
WHat 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 benefit you in educational rounds by point Like in general div2 round it will increases your points.
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.
I think I applied your idea just by a different way.
I pushed all the prime factors of a*b in a vector and generated different combinations so that the factors can be distributed into 2 sets for x and y, but would not it cost us (2^size). In problem E1, size can go upto 32 at max, so still it gave me TLE.
I think I am missing something.
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 Stress for a counter example.
nice round