Привет, Codeforces!
Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со стипендиями JetBrains. Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с учебной программой прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно!
Во 24.12.2024 17:35 (Московское время) состоится Educational Codeforces Round 173 (Rated for Div. 2).
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Артем Ferume Иликаев и Руслан AcidWrongGod Капралов. Большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces. Также мы бы хотели поблагодарить людей, тестировавших задачи: Um_nik, alex.dobleaga, Stanislau, Karabutsa, Golovanov399, Timur2006, shnirelman, adedalic.
Обратите внимание: раунд пересекается по задачам с очным туром Олимпиады КФУ, так что если вы участвовали в нем, пожалуйста, воздержитесь от участия в раунде.
Удачи в раунде! Успешных решений!
let's go another BledDest' Edu round
why are u getting negative vote
I wish I could read minds
Hope chenlinxuan0226 can reach Expert after the contest.
2 more contests for expert. Lets GO!
from Electricity is crazy
In Christmas eve :'(
Merry Christmas, and I hope my rating can get closer to MASTER.
Merry Christmas in advance my fellow CP'ers
Hi, this is my first time participating in an educational contest, so how is the contest organized?
similar to d3 in terms of rules regarding standings. problems are of d2
Merry christmas codeforces and evrybody. And I hope it will be good contest befor christmas.
Attention: the contest uses some problems from the onsite stage of the KFU Olympiad, so if you participated in it, please refrain from taking part in the round. Means ??
No one can prevent me from solve 3 problems in this contest I hope!
you can do it Good Luck
We got testers in Educationals before GTA 6
SantaForces
hoping i could get to 1700++
Hope chennie can reach Specialist after the contest.
Almost had me
Merry Christmas
Merry Christmas!
Merry Christmas!
where can i download KFU onsite olympiad 2024 problems ? I couldn't find it online.
I just want to practice those problems before round starts.
Thanks!
don't think this is a smart lie.
Why can I set my registration type to rated.
Why can I set my registration type to rated?
because you have too much rating
ZaEDUCATIONAL!
i hope all we become master
good
thanks
Can I become a Specialist in this contest ? (I dont think so, though, let's see)
I believe while registration there was achoice whether you want this round to be rated for you you or not and that could be chnaged later on
can it be changed once after contest is over or maybe right now as well
i first chose to keep it unrated for me but now i want to switch it to rated can someone help me in that?
I believe while registration there was achoice whether you want this round to be rated for you you or not and that could be chnaged later on
can it be changed once after contest is over or maybe right now as well
i first chose to keep it unrated for me but now i want to switch it to rated can someone help me in that?
According to the rules, no. Also even with common sense, the answer is still no. Like if it is possible then I can just participate as "unrated" everytime, then change to "rated" when I realize I have a good performance? That just doesn't make sense dude.
https://mirror.codeforces.com/blog/entry/133293
Wrong answer on test 4...
Can anyone prove a bound for problem D? I just did yolo n=1000 and was surprised it passed lol
I have a proof for 50 x 50 bound, but unfortunately it gets TLE
It just worked for me. Cool I guess, but still hate the problem If you care: 298307075
How did you do it?
The only difference between our implementations as far as i can tell is that i use __gcd(a,b) to find the gcd and break after finding the furthest r for each l [l, l+50].
1000? I kept getting TLE for 100, 70 and 50
It got accepted with 20 at the end.
wtf is test 4 of problem C :-(
When you are adding numbers with the Different one, you can only add an subarray that is adjacent to the Different number from both side. (it was my approach that got wa on 4)
I took that into account, I think, still getting WA on 4. Can someone please take a look? 298297481
i also got the same issue but finally got accepted
You can take 2 cases:
case-1: Subarrays to the left and right of x which do not contain x.
case-2: Subarrays that contain x.
For case-1, apply the kadane algorithm to get the maximum and minimum subarray sum. As the array is made of -1 and 1, all the numbers between this maximum and minimum value will be a part of our answer.
For case-2, calculate the maximum and minimum subarray sum to the left of x and to the right of x. Now we have two ranges, [minleft,maxleft] and [minright,maxright]. Therefore all our sums lie in the range [minleft + minright + x, maxleft + maxright + x]. Again as our array is made of -1 and 1, all the sums lying between the two values will be a part of our answer.
case-2 as you described, max and min subarray sums to the left and right of x, they contain x right?
i'll never participate in edu. rounds again
How to solve problem E ?
L Contest.
what is meaning of L bro ?
It means that the contest is bad. Too much math.
worst educational round ever
woah woah woah bro there has been much worse
D also has weak pretests
couldn't submit anything in the last 3 minutes.
G is a cool problem
How to solve it? I have no idea
First reformulate the problem into counting equal pairs rather than unequal pairs. Split into blocks of size $$$B$$$. We can maintain
block_ans[i][j]which stores the answer for all the blocks in the range $$$[i, j]$$$ (there are $$$\frac{n^2}{B^2}$$$ such ranges), andblock_prefcnt[i][j]which stores for each value $$$i$$$, its count in the first $$$j$$$ blocks. They can be updated in $$$O(\frac{n^2}{B^2} + \frac{n}{B})$$$ and using those values you can do queries in $$$O(B)$$$ (the idea is similar to square root decomposition). Then you just need to choose the right value of $$$B$$$, if you let it be about $$$n^{\frac{2}{3}}$$$ then the complexity is $$$O((n + q) \cdot n^{\frac{2}{3}})$$$ (I just fixed it to $$$1000$$$ though and that was fast enough).Clever solution!
After a small amount of hacking I now have first solve on G... although my solutions will most likely fail system tests to my own hack cases lol (they are vulnerable to being hacked in the same way)
thank you for giving worst ever-experience on Christmas in my life.
For problem F, I solved each query in a dp with at most $$$7*64*50$$$ operations, worst case $$$2.2*10^9$$$. 1109 ms.. The case when $$$r-l+1 \gt 50$$$ is easier, if there is any 0, then choose 0, otherwise there is some number with 2 or more reps, choose any pair of those.
nvm
You are legendary grandmaster. figure out yourself bro ...
...
I looked at your code, but I can't understand without comment. I can share the approach I have used.
1) Split the array in two parts from the "DIFFERENT" element.
2) Find out maximum subarray sum and minimum subarray sum, of those two partitioned arrays. ( for that, you can write single function, and then make a call to function twice ) .
3) [ a1,a2,a3 ... ai, X , a(i+2) , a(i+3) ... ] Find out minimum and maximum spans, such that rightEndpoint of your subarray is a[i]. Similarly find out minimum and maximum spans such that leftEndPoint is a[i+2].
https://www.geeksforgeeks.org/find-a-co-prime-pair-with-maximum-difference-in-a-given-range/
D ^
Edit: doesn't work oops
As we know that GCD(N, N + 1) is always 1 and we need to find the maximum difference of the pair with GCD 1 so GCD(L, R – 1) and GCD(L + 1, R) will be one as GCD(L, L + 1) and GCD(R – 1, R) will be 1 so there cannot be any common factors between (L and R – 1), and (L + 1, R).
How is this True? What about L = 15 and R = 64
gcd(15, 64) = 1 so use that.
But the statement itself is still false
It does not actually work, like a lot of stuff from geeksforgeeks
upd: for example, if you take $$$14$$$ and $$$36$$$:
Small request BledDest.
why not save these kind of tricky B problems for Div(1 + 2) rounds. It makes sense to use such an intellectual problems when GM and LGM's are competing rated.
Look at this past EDU history,
10k people solved C, only 4k solved B
8k solved C, only 7k solved B.
10k solved A, only 5k Solved B.
May be you have this thought process in mind that "during EDU round, each problem has equal points, so may be, if problem is difficult, then participants should skip the problem and solve next one". And from ICPC point-style, it makes sense also.
My humble request is, to save such an intellectually, math-involved problems for BIG-ROUNDS, and let the Div-2 people enjoy their life peacefully !!!!
You have a point, there have been some difficulty issues in the past. But I don't agree that today's B is really as intellectual and math-involved as your (and many others') comment suggests.
Yes, it has a solution which is very math-involved (checking all divisibility rules for $$$3$$$/$$$7$$$/$$$9$$$). But this is not the only way to solve the problem. There are other, much less "mathy" ways. I will illustrate one of them in the official editorial.
Today's B was fine for me, but many people struggled. So based on the data-points and opinion evaluation, I shared my thoughts.
I have seen much worse B problems in past EDU. so I am way above this discussion now. It's just my suggestion, to save good problems for Big contest...
last Edu. rounds have a lot of problems which u must get about 3-5 WA before getting AC.
I'm not saying that all of these problems were bad (i love a lot of them),
but they have a lot of corner cases / guesses / luck which ruins the contest especially when the contest have more than one problem like that, or these problems positions are B.
Thanks
Here is B solved by pure bruteforce, math'd only division by 5:298342531
Man I could have solved C if there was a little more time left. WTF was B ??? took me 1 hour.
Math forces but I respect to the point problems. No Alice wants a range and bob this blah blah. Problem D we have to find 2 most coprime numbers in the range ceil(l/G) and floor(r/G) is it the solution?
How to solve B? I feel like an idiot for not being able to figure out the trick. Finding the answer for 1,3,5,9 seemed simple but I couldn't figure out 7 to save my life
I can't prove that my solution works. But I found the first repeating number divisible by each odd number and compared it to the length of the repeated number.
If any number divides the given number for some n, then it automatically does for all n greater than that one. For example, since for n = 3, d = 3, 333333 is divisible by 7, all other numbers with d=3 and n>=3 will also be divisible by 7. You can see that by expressing the higher n numbers as sums of multiples of the previous ones by powers of 10. So, if you check for each digit you see that for n=3, 7 is always a factor. So for all possibilities with n>=3, 7 is a factor. Now for n<=2, the only possible case in which it is divisible by 7 is if the digit itself is 7.
in the question you can see the given number can be represented by d*11111111(n! times).So you can observe 11111..... (x times ) is divisible by 7 if and only if x is a multiple of 6 so when n=3 ,n! becomes 6 afterwards all the factorial will be divisible 6
Is D meant to be solved deterministically? I figured that the probability any two numbers are coprime is so high that we might as well try the first 1000 numbers in the segment. It passes.
Actually, prime numbers are pretty regularly distributed. So you can always find a prime number on a long enough segment. That's why yours and similar solutions work.
There is a fact that the distance between adjacent prime numbers isn't big. For n = 10^9 maximal distance is 282
Mathforces. Nice problems no Alice wants to stay on the left and bob doing some crazy thing and me shouting at my homie like whatttt. Anyways problem D is it find the 2 most separate coprime in the range ceil(l/G) and floor(r/G) is this the solution?
https://t.me/codeforces_answers
Cheating groups like these ruin the spirit of Codeforces and sharing of answers on these temper the ranking. Strict action should be taken against such cheaters.
A<D<C<B
I changed my name to gray, and it turns out that I will really become a gray in this round(Only passed one question. Is it magic?)
Second question was tricky
yes it was tricky
who is bro talking to
Never knew that Div2D could be solved with just two nested loops.
I guess Problem B that will go down in history ;)
My Solution of $$$E$$$:
First, each bit is independent. So we only need to consider $$$a$$$ and $$$b$$$ as binary matrices.
We observe that if the last operation is operation 2, then there must be a column in $$$b$$$ that is all 1s; if the last operation is operation 1, then there must be a row in $$$b$$$ that is all 0s.
We can find the columns in $$$b$$$ without any 0s and the rows in $$$b$$$ without any 1s, and set all the numbers in these positions to the wildcard
-1. Repeat this process until no more operations can be performed. Finally, compare $$$a$$$ and $$$b$$$.A brute-force simulation of this process might cause a timeout. Using BFS can reduce the complexity to $$$O(mn)$$$. 298292699
Bro, can you explain a little bit please. I tried watching the stream of youtubers who attempted this contest but nobody gave a way to arrive at a solution. Can you please help with the editorial until the official one is out.
Different approach, but I think it's easier to code and come up with.
I will really become a gray name in this round. Is it magic?
Sorry I have a sad Christmas Eve T_T
Can someone tell me where am i doing wrong in C. 298296633
wtf, i didn't write the number of elements in set for the case of (n == 1) I was handling and this costed me the whole problem... lmao (too much pain).
hehe, I did same for my C's first submission.
I was wrong A tests were trash for real
One of the most enjoyable
edu rounds imoIMO edu rounds.No, consider $$$[6, 9]$$$, the two numbers that are farthest apart and coprime are $$$7$$$ and $$$9$$$, both odd numbers.
cool , my greedy was wrong , ok thanks for breaking the illusion xD
Video of me solving this contest in rust will eventually be available here
Thanks for the christmas eve contest ! As usual, here is my advice about the problems
Overall, the problems were quite nice and educative. However, I believe the problem ordering is not correct at all + D should have been removed imo.
Great problem A. It's not A+B, it's not gcd(nzkjgbnsdjknf).
Bonus point: it can be viewed as a binary tree (which is probably cool for newcomers that want problems they can solve using "" concepts "" they learnt.
I guess it's ok as a problem B. Not particularly amazing but not bad either.
Probably the best div2 C I solved this year!! It is a great educative problem to learn about "discrete continuity". I liked the little twist (the value $$$x$$$ that is neither $$$-1$$$, neither $$$1$$$) which also teaches about multiple steps reasoning (solving the problem when $$$x = 1$$$ and then generalising). I also liked the fact that knowing the output it roughly linear in $$$n$$$ (as we're asked to print it) subtly hints to the solution.
Problems that rely on assumptions on prime numbers/guesses are not that good in my opinion. In particular, I think it's a bad idea to have such problems in the beginning of a round. One could argue that it's an educational problem but idk, I just feel like it's not very fit.
The problem by itself is a great problem to learn about non trivial applications of topological sort but I think it's way too easy for E ? In particular, I'm pretty sure if it was D it would have had way more solves.
Didn't have much time to try it but it looks cool. I wonder if the naive segtree/dnc with a pair $$$(minSz, cnt)$$$ in each node where we merge nodes in $$$64 * 64$$$ operations would pass ?
Bro, can you explain a little bit please. I tried watching the stream of youtubers who attempted this contest but nobody gave a way to arrive at a solution. Can you please help with the editorial until the official one is out.
Which problem do you need help on ? I don't mind sharing the intuitions to solve each problem
Well I wanted to ask mainly about D & E but now the editorial is out. I'll read that. Thanks for your reply though.
How to find condition for 7 in B
According to divisibility rule of 7, ddd...d — 2 * d (where ddd...d contains n! — 1 digits) should be divisible by 7, so take d common and we have d( 111..1 — 2). Now either d is divisible or other one. If other one is divisible then by rule 111..1 which contain n! digits is also divisible. Now just divide 1111.... by 7 and you will find that this is only divisible by 7 if length is of the form 6k. So n! must be divisible by 6 which means n >= 3.
So final condition is ((d % 7 == 0) || (n >= 3))
there are two cases :
if $$$d=7$$$ then it's trivial that it's divisible by $$$\underbrace{11111...111}_{n!}$$$
.$$$d \neq 7$$$ then $$$\underbrace{11111....1111}_{n!}$$$ is only divisible by 7 , if $$$n!$$$ is a multiple of $$$6$$$ then $$$n! \ge 6 \implies n \ge 3$$$ (why idk , I just bruteforced it and took pattern)
since $$$\gcd(7,9 = 1)$$$, so we have two cases:
$$$d = 7$$$, trivially divisible by $$$7$$$
$$$10^{n!} - 1 \equiv 0 \pmod{7} \implies 10^{n!} \equiv 1 \pmod{7}$$$
We note that $$$6$$$ is the order of $$$10 \in \mathbb{Z}_7$$$, by Fermat's Little Theorem (or Euler's Totient Theorem), we must have $$$6 \mid n! \implies n \geqslant 3$$$
$$$10^{x} \mod 7 (x \gt =0)$$$ has a period of 6: $$$1, 3, 2, 6, 4, 5, 1...$$$
The sum of the first 6 numbers is 21 which is divisible by 7 therefore $$$dddddd$$$ is also divisible by 7 and hence n-digit numbers (where n is divisible by 6 and all digits are the same) is also divisible by 7 because the period is 6.
my dream of becoming expert in this contest remain dream only :((((
Why make D, stop making proof by AC.
For D, if the answer exists, it is only necessary to check $$$(l_1 + k \cdot g, r_1 - s \cdot g)$$$ for $$$0 \leq k, s \leq 5$$$ where $$$l \leq l_1 \leq r_1 \leq r$$$ and $$$l_1, r_1$$$ are divisible by $$$g$$$ (that is, the minimum and maximum numbers in the range that are divisible by $$$g$$$).
submission
interestingly, you only need to check $$$[l_1, r_1$$$], $$$[l_1 + 1, r_1]$$$, $$$[l_1, r_1 - 1]$$$
Wait it's incorrect, isn't it?
Can you please tell me why and what is correct way to get to 5 instead of 1?
Clearly, the problem boils down to this: there is a segment $$$[l, r]$$$ find a pair $$$l_1, r_1$$$ in it such that $$$l \leq l_1 \leq r_1 \leq r$$$ and $$$gcd(l_1, r_1) = 1$$$ and $$$r_1 - l_1$$$ is maximal. Intuition tells me that if the answer exists, then $$$l_1 \sim l$$$ and $$$r_1 \sim r$$$, by $$$\sim$$$ I mean that $$$|l_1 - l| \lt C$$$ for some $$$C$$$. In contest, I got $$$AC$$$ by putting $$$C = 25$$$, but it's actually a lot more than I need.
In other words, it's hard to say why $$$5$$$ is enough, but right after reading this, my intuition tells me that the problem is solved like this.
Yes, I also fixed C = 10 but I don't understand why....I just made a guess... I want to know why this will work.
How to prove that?
hacked :D https://mirror.codeforces.com/contest/2043/hacks/1106554
thanks! :)
For D, what's bounds do you have to iterate on?
https://mirror.codeforces.com/contest/2043/submission/298219615
In problem D, why can we do $$$O(n^2)$$$ enumeration like this, is there any mathematical proof?
If you find two prime $$$p, q$$$, it's definitely good, and the distance between two prime is around $$$O(lg^2 C)$$$ so if you enumerate like that, it would stopped very quickly.
btw, it's known as prime gap
Max prime gap up to 1e18 is around 1600, Using that bound the solution will be too slow (1600^2 * 60 * 1000).
Check out Prime Gap.
No proof, imo. Just a matter of fact that primes are pretty frequent in the range and we'll find one soon.
You can check out this problem which uses the concept of prime gap Problem D , see its tutorial https://mirror.codeforces.com/blog/entry/20766. Even for n as high as 1e9, the difference b/w two primes is 282
Fantastic stuff
My max is master (currently cm going down horribly to expert)
Your handle perfectly explains the situation
Holy shit dude, i thought i had worst contest.
im so confused about problem D, am i misunderstanding the statement? why isn't the answer simply ceil(l/g) and floor(r/g)? (assuming you solve the case of gcd(floor(r/g), ceil(l/g)) == ceil(l/g))
Check this case:
The answer should be
7 10instead of6 9, becausegcd(6,9)=3. Therefore, it's not sufficient to check only two cases where you only decrease $$$B$$$ at most once.Looks like you are choosing A = ceil(l/g) * g & B = floor(r/g) * g. According to the statement, you'd want gcd(floor(r/g) * g, ceil(l/g) * g) == g. This will happen when gcd(floor(r/g), ceil(l/g)) == 1.
D is the worst garbage ive ever seen
Merry Christmas to everyone
Solution for B:
(10^{n!}-1) / 9) * dwhere the first factor is a whole number. Since 7 is a prime number at least one of the factors has to be divisible by 7. d is divisible by 7 iff (d == 7).(10^{n!}-1) / 9is divisible by 7 iff10^{n!}-1is divisible by 7. Further10^{n!} - 1 == 0(mod 7) iff10^{n!} == 1. And as usual 10^x mod 7 is periodid: 10^0 == 1, 10^1 == 3, 2, 6, 5, 1, 3, ... Hence 10^x == 1 mod 7 iff 6 divides x. So the second case is 6 divides n! which is n >= 3.Submission
Problem C is a bit harder to be Div.2 C also, in my opinion D is much easier than C (may be because I am a math lover XD ). However, Great contest as we used to from BledDest!
In Problem D
Can anyone explain the correctness of finding the co-primes within very less range i.e 10 iterations in this solution of mine .. sadly it got accepted after the contest :(
https://mirror.codeforces.com/contest/2043/submission/298300293
for problem-D, is it not possible to fix L to be smallest divisor of G in range L to R. can we prove it, test-case-3 has this case.
Consider G=1, L=15, R=21.
Then fixing L=15 will give you a maximum gap of 4 (19-15). While the best possible gap is 5 (21-16).
Something seems wrong with the testing script for problem D, my code for problem D fails on test case 2. I checked the part where it fails. for some reason the outputs of the 20th case and 19th case are getting swapped in my submission but works fine on my system.
I think you should check your system.
I checked it and I was at fault, lol.
Hey everyone so I faced a very weird issue today.
When I ran the following code using the c++ 17 compiler my code gave runtime error while the same code got accepted on c++ 20 compiler. LINK TO THE C++ 17 submission LINK TO THE C++ 20 submission
Any reason why it might have happened?
As you may know, the c++17 compiler is 32-bit, and the c++20 compiler is 64-bit. In the 32-bit compiler,
size_tisuint32_tand in the 64-bit compiler,size_tisuint64_t.Therefore, when you attempt
int i=a.size()-1on Line 127 whena.size()is $$$0$$$ (consider sample case 4), although both versions encounter underflow, the outcomes differ. In the 32-bit version, the underflowed result is $$$2^{32}-1$$$, which is assigned to along long(note the#define int long longin the front!), so $$$i$$$ becomes a huge positive integer and visitinga[i]clearly raises a runtime error. In the 64-bit version, however, the underflowed result is $$$2^{64}-1$$$, which is "correctly" assigned to along long, which will overflow again to the correct-1.Didn't participate in this round partly because of: I strongly recommend BledDest to reconsider his view on Div2 and Div3 rounds. I've noticed that almost each time he is a problemsetter, you should expect round to be unnecessary tricky. He's done it even in some of the previous Global Rounds, making guys even with higher rating than his to argue about unnecessary difficulty. And don't put it like 'Oh, you didn't solve problem, cry about it'. We are here to learn and difficulties should be. But people should not get discourage each time you decide to write a problem. If you really want to show your problemsetting skills, then create problems that are hard enough to make people think and not that difficult for people to fail. Especially for Div2, where so many people participate, from Newbies to Masters.
I really suggest the community to create a rating system for problems and rounds. If you make problems, that do not meet the requirements of the round, then you are a bad problemsetter.
who are you to decide whether problem is too difficult or not , and who are you to decide whether the problems met the requirements of the round or not . How can you even categorize someone as a bad problemsetter just because you could not solve the problems
You didn't get the point. It's not me the guy that "who is that guy to say these things?". It's me the guy that just summing up the overall reaction. Look at the comments first. It's much more easy to be kind-hearted guy and not being against anything and anyone than to reveal your honest opinion.
And if you really want to play this game, I am the guy who's seen a decent amount of negative comments to the BledDest's problems (and solved them too) previously and nowadays this is just a pattern. And I'm the guy who is going to participate in the next BledDest's rounds and hopes them to be interesting and solvable. And I don't comment badly about problems that seem to be difficult only for me. Here, I repeat, is a pattern.
And this is not only your first round, but also the first solved problems on CF. Problem A is already hacked. Man, just stay on top first, then arguing.
I mostly learnt from BledDest contests
And thats a good point too. Thanks for sharing.
I understand it and want to say that while problems should teach you something, they also should be balanced. I do not consider facing that much difficulty at B and C really worth it. Nevertheless, we can learn from it.
Maybe I was too categorical in my previous comment about BledDest being a bad problemsetter, sorry for that. I just want the situation like this day to be as rare as possible. And by this situation I mean... look at the comments. People are discouraged.
Which problems do you think were too hard today ? I agree D was not that great (especially since guessing helps a lot to solve it). Appart from this, ABC were perfect (and E was maybe even a bit too easy compared to usual div2 E).
Maybe you think that C should be easier since there have been recent rounds where #solves A = #solves C. However, it wasn't the case three years ago (and it shouldn't be the case). Ideally, you want a geometric solve count curve i.e every contestant can find a problem that is challenging for them. I think it was the case today.
If you're looking for rounds where you can solve more problems, then you can take div3 and div4.
It is impossible to have too many "easy" problems in every round which is why div3 and div4 exist!
Yeah, sounds nice and clean but look at the comments. It's not just my opinion. "Worst edu round ever" has 93 upvotes now and this number will only increase. You're sharing only your experience, but this round worked out only for small amount of people and you're among them. IMHO, while creating a Div2, problemsetter should keep in mind that most of Div2 participants are 1600- even if there are Div3 and Div4. It doesn't mean that all problems should be "easy" but not making even masters (look at Rising-coder) stuck on the second (gosh!) problem.
I would say it's a skill issue. I literally ranked 10000. It is me not the problems.
Unhappy people complain but the happy ones usually do not comment (which is why I force myself to comment, in order to also share positive thoughts to the authors).
In my opinion, in div2, slow ABC ~= 1500 — 1600 perf. That seems to be the case today. Note that there are > 3k people that solved ABC, I think this proves the problems were perfectly fine: there is roughly a factor 3 between C solvers and A solvers.
Finally, people all have bad days. I myself have had bad contests (going from +150 to -150). This doesn't mean the problem setters did a bad job.
Well, if you're not a lawyer already, you should consider to be one.
I feel like they should have swapped problems E and D, cuz honestly D is way harder than E
I feel like problems E and D should have been swapped,E is way easier than D.
For low rated people like myself, I feel like this round B and D was a big guessforces. C is nice though.
How is b guessing?it's maths
I think the same argument can be made for most problems about not being a guessing problem. But I don’t believe the majority of the people that solved B know the proof of to why that happens.
I think ABC is the normal. I don`t no why people hate B, this is not hard mathematical problem. D is very random. AC for proof for me and i think for many peoples. Round is the normal, but i was very stupid on D (+5).
I want to bring to attention a major class of testcases missed by the pretests of Problem C. I unfortunately missed a case when fixing my solution and didn't think much of it when it ACed. However I realized after the contest that it would fail.
Just a subset of this major class are the test cases with 1s and -1s such that all prefix sums are non-negative are not in the pretests, which is a major class of tests, with a few examples included below
and
I am unsure as to why these were not tested. When looking at test case 2, it seems that the test case -5 -1 was tested repeatedly instead of going through the small cases, which I thought was the norm. Unfortunately, it cost me and other contestants on this contest ):
So basically, (B, A) + (an imposter $$$x$$$ sneaking in among the $$$1$$$s, with a sprinkle of $$$G$$$ on top) = (C, D).
Hello all, how did you approach problem C? I'm looking at some other people's solutions, and I don't understand their approach. I did manage to come up with my own solution though, 298342429. My idea was to combine:
My main observation is that it's really easy to do it this way since you only need to consider adding or removing ±1, and then I threw a bunch of sets at the problem.
Find maximum and minimum subarray sum before x. Do the same after x. Now insert values with thin this range into a set. Now find maximum and minimum subarray sum for subarrays starting from x and going say towards left. Now do the same for postion right to x. Add the minimum of these two sets and maximum of these two sets. Insert all the values between this range of min and Max value into the earlier set. Can it the set values
In question E, I came up with a greedy approach of changing from column 1 to column m if necessary, which is clearly incorrect. I repeated this operation 30 times and randomly selected the order of attempts in column m, and it passed... (However, during the competition, I only performed it 15 times and eventually switched to a deterministic approach) Code
Does anyone has the prove for D.
Does anyone has the proof for D.
Honestly,the pure mathematical proof,i think most of the cp contestant cannot figure out,sometimes we just need to know the theorem state and which mathematician say that is enough,the prime number theorem state that for a given integer N,the prime number less equal than N is approximate n/log(n),in other word from 1 to N,there is around N/N/log(N) which is around log(N),this mean for avg 2 consecutive prime number distance is around log(n),so how about it related to our problem?The key is if gcd(A,B)=G,this mean A=k1G and B=k2G,and gcd(k1,k2)=1 because if gcd(k1,k2)>1 then gcd(A,B)>G which is not satisfy problem statement,so we know that l<=A<=B<=r -> l<=k1G<=k2G<=r ->ceil(l/G)<=k1<=k2<=floor(r/G) so our target is finding two number k1 and k2 which gcd is 1 in ths interval,and the fact is two prime number are coprime which is gcd(pi,pj)=1 (pi and pj are prime number),but is that only prime number gcd is 1?Obviously not for example gcd(8,27)=1 but they are not prime number,so according to previous result,if we start from lower bound (ceil(l/G) and upper bound(floor(r/G) to search the first and the last prime number the worst time complexity is O(logN) but if we find two number which gcd is 1 before found the prime number then the complexity will lower than O(logN) so overall for 1 testcase the worst complexity is O(logN)
Okay but why does searching first 50 mutiples of G and last 50 multiples of G in bound(l,r) works?
Actually it depend on the coder experience about solving this kind of problem,as i mention before there is around log(n) gap for n=1e18,log(n) around 18 but this is a avg so to prevent WA for some extreme case,most of the person will make larger value like 50,100 even 500 for me.
rubbish comments from rubbish. he asked for a proof, not for pointless ramblings.
298416491 The solution is more of intuitive/common sense then actual proof. The solution just happens to work within given range. My intuition would say have a look at prime gap, it increases by leaps and bounds as we move further on the number line.
Can someone give me a couple of hints for C
Hint 1: what would be the solution if abs(x)=1 for every x in the array?
Hint 2: now suppose that there is exactly one x in the array such that abs(x)!=1. X can split the array into 2 arrays (possibly one of them is empty). You can apply the solution found in Hint 1 to each array of them. This will include in the solution the sums of all subarrays not containing x.
Hint 3: Once you got the sums of all subarrays not containing x, you still need to get the sums of sub arrays containing x and add them to the solution.
Hint 4: Each subarray containing x is composed of a subarray starting from x, and a subarray ending at x. The sum of the subarray is the sum of the sums of both subarrays.
I hope these hints are useful. I tried not to be super clear to avoid giving you the solution directly. If you need more explanation let me know
For 1 I noticed that it's not optimal to mix 1 and -1s. Adding a -1 is the same thing as not including a 1, so the answer would already have been computed. Therefore, we can compute the sums with a two-pointer technique in O(n).
Now when including a different number I can apply the same technique in the two subarrays you mentioned and add the merge of some subarrays to the answer too (that way we're including the subarrays with the different element). Each half has O(n) sums, so excuse me as I think how to merge these subarrays in an efficient manner...
I don't think that it is not optimal to mix up 1 and -1
Consider this example:
If you don't mix -1 and 1, the max sum you can get is 6. But this is not correct because we can get a sum of 8 by adding up all the items.
I can give an extra hint to help with this:
Let's take an array containing only -1 and 1
Let's pick an arbitrary subarray (for example):
The current sum in this subarray is 1+1-1 = 1 Now what happens if we try to expand the subarray from the left?
1 1 [1 1 1 -1] -1 1=> adds 1 to the sum (sum becomes = 2)1 [1 1 1 1 -1] -1 1=> adds 2 to the sum (sum becomes = 3)[1 1 1 1 1 -1] -1 1=> adds 3 to the sum (sum becomes = 4)What do you notice? If we can get the sum from 1 to 4, we necessarily have subarrays that give a sum of 2 and 3 (any integer between 1 and 4).
This is correct because as we expand the subarray from any side, we will either add 1 or subtract 1. Thus, if, starting from sum = x, we can achieve sum y by expanding the subarray from either sides, we will get all integers between x and y as sums along the way (here I am supposing y>x, but it also applies if y < x for sure).
So to sum up...
If we know that we can get a subarray with sum X, and a subarray with sum Y, then we are guaranteed to have subarrays with sum X, X+1, X+2, ..., Y
Thus... if the array is only composed of 1's and -1's, the different sums that we can get can be obtained by determining the smallest subarray sum, and the largest subarray sum. The result will be the set of every integer between the smallest subarray sum and the largest subarray sum (inclusively).
Finding the largest/smallest subarray sum is a classic dp problem that can be solved in O(N)
How can my solution for D be hacked? The complexity is $$$O(T*50^2*60)$$$. 298249717
it seems that p = a + i*x can exceed long long, maybe that's the problem
Yeah that is a case. However my solution was hacked due to TLE, and integer overflow doesnt affect.
but then it's not clear what's happening with gcd, so it may well be TLE
Worst contest i ever seen__
I really like C, F. However, I think D is unimaginably bad, especially in a round that participants can hack each other. I also don't like B either, but I think it's still an okay problem.
I want to know how to hack D. I'm very curious. It seems like all the hack was done with making TLE which surprises me a lot, I thought its easy to make a WA.
How to do C?
I was able to figure out that values in the left subarray of the non 1/-1 and values in right subarray but I'm unable to find a way to get the sum of subarray including our non -1/1 element
I tried reading AC code but doesn't make sense ;-;
You already know how to do with arrays containing only -1/1, so our goal is to find the maximum subarray sum and the minimum subarray sum that includes the special element in the subarray. Let's assume that $$$id$$$ be the position of the special element and $$$s$$$ be the prefix-sum array of $$$a$$$.
We can record $$$A=\displaystyle \max_{0\leq j \lt id} s_j$$$ and $$$B=\displaystyle \min_{0\leq j \lt id} s_j$$$. Then calculate $$$\displaystyle \max_{id\leq j\leq n} s_j - B$$$ and $$$\displaystyle \min_{id\leq j\leq n} s_j - A$$$. That's just what we want.
This works cause for all $$$j\in[0,id), k\in[id,n]$$$, $$$s_k-s_j$$$ is equal to $$$\displaystyle\sum_{i=j+1}^{k} a_i$$$. $$$a_{id}$$$ is in the summation obviously.
Same as I thought. I remembered a theorem which stated that "from 1 to 1e18, the maximum distance between the two primes are at most 300", so I think that finding the left and right bounder after two loops of 300 will pass. But that gave me TLE, so I have to change to 100. Luckily it passed but I thought that it was easy to hack with WA verdict. P/s: sorry for my poor English. But I remembered the theory is called "Rabin-Miller theory"?
But according to wikipedia, 2,300,942,549 and 2,300,942,869 are both prime, so I think "from 1 to 1e18, the maximum distance between the two primes are at most 300" might be wrong?
Yeah not 300, but the max gap between two consecutive primes is atmost 1600 till 1e18. consecutive is the thing here. But even after reading that fact from wiki, I am yet to discover the usage of this fact in the solution.
A submission for Problems about GCD , having difficulty understanding why it is giving WA,expected TLE 298363085
how to solve G
why my code — 298375202 gave TLE but similar code - this one didn't can you please tell me the reason i am very confused. Thanks in advance.
you need to end the for loop if second — x <= mxdis or y — x <= mxdis. Plus, 4 variables(first, second, x, y) should use long long. This don't affect TLE, but you will get WA. check this.
In your code first=(l+g-1)/g which is ceil(l/g) and second=(r/g) which is floor(r/g) but under the constraint l and r up to 1e18 and min g is 1,in other word second to first can up to 1e18,so if you run through a loop about 1e18 definitely will be TLE,the other code is is checking around 100 number only,summary is the other code check for the number around 100 times but your code check 1e18 times which is 1e16 times than other code so it will TLE
Mine code is also checking 100 numbers only check it see this 298375202. why its not working
Your code have a small mistake. Since x <= x + 100, x <= min(second, x + 100) equals with x <= second. So you gets TLE. you need to change this to x <= min(second, first + 100)
Silly me.. thanks ☺️.
Get a life bro
I'm a newbie, would appreciate if you don't go too hard on me. Coding is not mt strong suit, I'm working on it
Do a Binary Search on your code:
WA -> range too small
TLE -> range too big
Until those ranges overlap (with no point which would AC), in which case you need to search for other solutions :)
My worst performance in a div2 edu till date. Problem C was very nice, learnt a lot while solving it. I think problem B was un-necesssary, imo a div2 B should'nt be math heavy to the point that most solves are proof by AC.
I don't think so b was tough at all. It was just basic number theory.
It was indeed, i am just bad at math.
Now worries just buy a number theory book and finish it you will be good to do.
why A test are so weak ?
I mean how on earth the authors let someone got hacked on A because of precision issues ?
for real that's a bullshit
Why ratings are not updating?
system testing hasn't started yet
I have seen system testing 100% :)) when the contest ended . so another one coming up ?
Oh maybe I could have missed system testing... thanks for telling
The system testing will happen after the open hacking phase, where all submissions are tested with test cases used for hacks. I don't think it has started yet.
where is my rating bruh
F is totally shit. the O(nv^2) sol is naive and should't appear at this pos actually. if u see the rankings u can find a lot of sols using very complicated algorithms (and some get TLE).
if u swap D and F I bet there will be much more solves.
(P.S Me myself wrote a sol using DP and FWT in contest, which is O(nV*log^3V). although it passed i'm so sad.)
bro it’s your problem if you can’t notice it. calculating time complexity is also a part of competitive programming.
I mean that put such a naive problem at F is not proper. Maybe it's suitable for C or D i think, putting here will only make ppl confused and solve it with methods too complicated.
u can look at the standings, almost half of all participants solved it in a way too complicated way, just have a look at their codes.
Editorial please
Please do the system test faster! I have waited for a day.
I am happy for you and everyone expecting a +ve delta. Being someone who is (a big) maybe getting de-rank, it's getting more intense as the time passes. Please update the ratings...
Well, the system test is now starting.
Bro how my solution to A failed (cries): 298206354
That's because you are only flooring the final result, but in the problem statement, there are these flooring brackets ⌊x/4⌋. One way you can do this is to simulate the divisions, and floor on each iteration.
Maybe something like this:
Advice for authors : don't put a code that have precision issues on A , how the huh on earth you put $$$(1 \le n \le 10^{18})$$$ For A ?
I mean I was ~$$$1300$$$ perf , now I'm $$$400$$$
I don't think all the hate for D is warranted. The fact that primes appear frequently is a common topic used in problems and is suitable for an educational contest: I've solved two problems recently using this trick and I barely solve any problems
I think the problem with EDU rounds still mainly lies in the conflicting nature of EDU rounds being rated: the regular div 1/2s aren't "educational" and mostly promotes ad-hoc problems. But obviously making EDU rounds unrated would mean you lose a lot of participants
The fact that there are no testers contribute to the problem as well. The backlash would definitely be smaller if the pretests were stronger and there weren't that many FSTs — testers help a lot in this case
For someone who doesn't like doing casework (like me).
Solution for B — 298416560
Problem E 298249227 TLE when n=1000,m=1
after deleted solve() function it still runs over 1000ms in custom innovation
Probably a cache hitting issue? hmm
Yes, changing a[k][i][j] into a[i][j][k] should speed things up. Also don't pass vectors by value.
passing $$$a$$$ and $$$b$$$ as references to solve function indeed makes it faster 298429050, it is near to TL tho.
After solving A,B,C today my A gets hacked… At least now I know not to use log_2 ever
Please show the Editorial!
Is this rating calculation fair?
1957 rating get +158 points, whereas 1771 only +157?
1957 rating get +158 points, whereas 1959 only +99?
People get more points in their first five contest(for the original rating is in fact 1500),to cover up these points.(Nowadays the rating is counted from seemingly 0 instead of 1500 to avoid just dropping ratings for newbies)
Just one correction: the initial "real" rating is 1400, not 1500.
Editorial seems like Santa's present. It won't ever come ig, smh.
Setting the TL to 1s in E is such a bad call
My solution for problem E:
Code : Submission 298439422
How did you get the idea to go from point 3 to 4? Also, how do you get the construction of operations from the graph if there are no cycles?
Each row, column represent a unique operation and one operation can imply need for another operation because it flips some bit which shouldn't have been flipped thus creating a dependency graph.
If there are no cycles, you can take the topological sorted order in the graph which will represent the order operations.
Where is the editorial? Aren’t edu rounds supposed to have them? Anyway, merry Christmas to everyone!
why this solution for E works? 298487266, it will choose the AND and OR value of each row and column greedily and repeat 100 times!
I just repeat min(n,m)+1 times
i am solved 3 problems, why i dont get rating?
Problem E 999ms :)
https://mirror.codeforces.com/contest/2043/submission/298279193
I still haven't received a rating for this competition, is that ok?
Hello,
I want to address a concern regarding my solution (298251853) for Problem 2043B and its similarity to the solutions submitted by BlackIce666 (298251853) and enze_qwq (298260333).
I would like to clarify that any resemblance between these solutions is purely coincidental. The problem was straightforward and could naturally lead to similar approaches from different participants. I have no knowledge of these users or their submissions, and I can confidently state that my solution is entirely independent.
Given the simplicity of the problem, such overlaps are not unusual as the implementation mostly involves basic conditional logic. I hope this can be considered when reviewing the matter.
Thank you for your attention and understanding.
Sincerely, Tanbin Hasan Ador (BlackIce666)
BledDest MikeMirzayanov
This is regarding an unfair plagiarism check that has occurred with respect to 2043C - Sums on Segments. I have explained below my solution to 2043C - Sums on Segments and the way I have implemented it. Please find my submission link 298237538.
I first check if there is an element in the array that is not 1 or -1 which is what the first for loop corresponds to.
If there is no such element, I run Kadane's algorithm to find the maximum and the minimum subarray sums in the whole array.
The implementation I have followed is quite standard and is similar to the one described in pg 104 of Competitive Programming 3 by Steven Halim and Felix Halim.
As the array is made up of only 1 and -1's, the possible subarray sums are from minnsum to maxxsum which I output using another for loop. After this I return from the function solve().
If there was such an element(at idx), I first try to find possible sums corresponding to subarrays not containing that element, for which I use two more runs of Kadane's algorithm, one from 0 to idx-1 and another from idx+1 to n-1. And after each of these runs, I insert all the possible subarray sums into a std::set to ensure I output only distinct elements at the end.
To find the set of sums of subarrays containing the element at idx, I run two other for loops to find out the maximum and minimum sums, one starting from idx+1 and another ending at idx-1 using which I find whatever sums are possible in subarrays containing the element at idx. And again to ensure unique elements, I add them to a set which I use to print my final output.
The above approach is quite easy to think of and is certainly something one can opt to code up under a time constraint. It can also be seen that once one has decided to proceed in the above direction, there isn't much he can do than write the requisite for loops and use the necessary variables.
It is however very disheartening and demotivating to see that my solutions have been skipped stating that there have been similarities with the codes submitted by lexapex5 and code_coffee. I don't know either of them and I'm quite sure they too have honestly solved this problem on their own.
Kindly review my code and do not penalize me for a mistake I have not committed.
Thank you.
MikeMirzayanov BledDest Hi, recently I just got this message:
Your solution 298228434 for the problem 2043C significantly coincides with solutions lexapex5/298228434, aryak05/298237538, code_coffee/298267063. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I believe this is just purely coincidence, I do not use ideone.com during this contest and I believe I do not cheat at all. Firstly, I think I got AC faster than them, so there is no way I could cheat to their solution. Secondly, the idea I think is so common to check the maximal and the minimal of possible sum of the sub array. Thirdly, I do not know any of them. I also used vscode and not any online IDE. Please take a look on this case and contact me if you require anything to proof my innocent.
Dear Codeforces Team,
I have received a notification regarding my solution for problem 2043B (submission ID: 298215717) being flagged as significantly coinciding with other solutions (Abhiraj/298215717(Myself??),abhinab_roy/298219844, anonymous_uzbek/298248796). I would like to clarify the situation:
Explanation of My Solution:
I developed the solution independently based on my understanding of the problem. My approach centered on deriving the divisibility rules for the numbers 1, 3, 7, and 9, and implementing the logic using modular arithmetic and the properties of factorial numbers. However, I did not share my solution with anyone at any point during or after the contest. I refrained from using public platforms, such as Ideone (with public settings), or using any LLM models like ChatGPT or Claude or any other model and did not intentionally disclose my code to anyone.
Regarding Coincidence:
The similarity in logic could be attributed to the common strategies typically employed for solving such problems, as divisibility rules for numbers like 3, 7, and 9 are well-known and widely used. I assure you that I neither copied someone else’s solution nor shared mine with any other participant. I am also unaware of any potential leak of my code, if such an incident occurred.
I kindly request that you review my case and take my explanation into account. Please let me know if there are any additional steps I need to take to establish my innocence.
Thank you for your understanding and for maintaining fairness in the community!
Dear Codeforces Team,
I have received a notification regarding my solution for problem 2043B (submission ID: 298215717) being flagged as significantly coinciding with other solutions (Abhiraj/298215717(Myself??),abhinab_roy/298219844, anonymous_uzbek/298248796). I would like to clarify the situation:
Explanation of My Solution:
I developed the solution independently based on my understanding of the problem. My approach centered on deriving the divisibility rules for the numbers 1, 3, 7, and 9, and implementing the logic using modular arithmetic and the properties of factorial numbers. However, I did not share my solution with anyone at any point during or after the contest. I refrained from using public platforms, such as Ideone (with public settings), or using any LLM models like ChatGPT or Claude or any other model and did not intentionally disclose my code to anyone.
Regarding Coincidence:
The similarity in logic could be attributed to the common strategies typically employed for solving such problems, as divisibility rules for numbers like 3, 7, and 9 are well-known and widely used. I assure you that I neither copied someone else’s solution nor shared mine with any other participant. I am also unaware of any potential leak of my code, if such an incident occurred.
I kindly request that you review my case and take my explanation into account. Please let me know if there are any additional steps I need to take to establish my innocence.
Thank you for your understanding and for maintaining fairness in the community!
Dear MikeMirzayanov,
I recently received a system message stating that my submission 298211934 for the problem 2034B - Rakhsh's Revival significantly coincides with this submission 298213898.
As I mentioned in this blog, I believe the solution to this problem is limited in diversity, making it highly likely for different contestants to produce nearly identical code.
Kind regards, cos-tel-bi-ju
What should I do if I was mistakenly thought to be using third-party code?
Dear MikeMirzayanov, i still still haven't received a rating for this competition. what could be the reason?