Hello, Codeforces! Or, as we like to say in Romania: Nu îmi amintesc să fi adresat întrebări, Codeforces!
I am glad to finally invite you to participate in CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!), which will start on Nov/06/2022 17:35 (Moscow time). You will be given 8 problems and 2 hours and 30 minutes to solve them. It is greatly recommended to read all the problems, statements are short and straight to the point.
I would like to thank:
- Artyom123 for prodigious coordination.
- AquaMoon, mejiamejia, ugly2333, Ecrade_ for huge help in preparation and authoring one of the tasks.
- errorgorn for being a VIP-tester.
- Lemur95, Gheal, Perpetually_Purple, Everule, IacobTudor, andrei_boaca, lucri, AlperenT, Kuroni, prabowo, lis05, Alon-Tanay, jeroenodb, Juve45, denis2111, Brodicico, Fanurie, huangzirui, satyam343, tfg, Sugar_fan, SlavicG, Vladithur,KrowSavcik, kevinxiehk, sharkycode,Alan, TimDee, Rhodoks, dannyboy20031204,TomiokapEace, Qingyu, lxlxl, ChthollyNotaSeniorious,PinkieRabbit, jerryliuhkg, valeriu, Chenyu_Qiu, jampm, izlyforever, njupt_lyy, RUSH_D_CAT,azureAmarantine, Erkhemkhuu, wh030115,ak2006, dorijanlendvaj, spookywooky, arvindf232, absi2011, AlexLorintz for testing the round and providing invaluable feedback.
- freak93 for morning refreshment.
- MikeMirzayanov for great platforms, codeforces and polygon!
Scoring Distribution: 500-750-1250-1750-2250-2500-3250-3500
The editorial has been published here!
And here are our winners!
- Benq
- zh0ukangyang
- WYZFL
- MagicalFlower
- feecIe6418
- QuietBeautifulThoughts
- p_b_p_b
- conqueror_of_tourist
- jiangly
- tourist
And here is the information from our title sponsor:
Hello, Codeforces!
We, the TON Foundation team, are pleased to support CodeTON Round 3.
The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.
Since July, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.
The winners of CodeTON Round 3 will receive valuable prizes.
The first 1,023 participants will receive prizes in TON cryptocurrency:
- 1st place: 1,024 TON
- 2–3 places: 512 TON each
- 4–7 places: 256 TON each
- 8–15 places: 128 TON each
- …
- 512–1,023 places: 2 TON each
We wish you good luck at CodeTON Round 3 and hope you enjoy the contest!
Good luck in LeafTON round 3.
Omg Green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
(-_-)
Broke the chain
omg green round
What does "omg green round" mean? Thanks in advance and good luck to the participants!!
it means omg round with green problemsetter
omg green round
omg green round
omg green round
omg green round ;)
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
ahahahah
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
omg green round
rmg oreen gound
Please stop this nonsense, every time I read the round announcement I have to scroll down things like orz, as a tester this round is great, etc... And this thread is too much
As a tester, I am sure you will find some interesting problems whatever rating you have and I wish you good luck and high rating!
First of all, as a tester, I tested. Secondly, I strongly recommend this round!!!
As a tester, I'm already yellow, not purple!
Upd: Good luck to all participants! tibinyte orz
The contest's duration is 2.5 hours in blog but 2 hours in Current or upcoming contests?
As a tester I suggest everyone to participate in this contest. Even I want to participate in it but I obviously can't :(
I wish everyone good luck and a good experience
As a sad I can't participate in the round myself I'm a tester too!
good luck everyone! hope you find some interesting problems and have a good time
As a tester, Problem A is one of the problems of all time.
Okay I will start with B then :p
GREEN>>CYAN
statements are short and straight to the point. finally it's in the blog. Thanks
As a newbie , it will be more fun to participant in a green author round . Best of luck all.
As a tester I tested
As a tester, I haven't tested yet
Leaf forces
I appreciate your dedication
Excited for a green round :)
Well, it's obvious that tibinyte is a talented programmer, but he just managed to get negative deltas to become green to pretend to be weak. Also, he is just the blog sender, not one of the problem setters.
So, I wish you guys get positive deltas & have fun!
As a tester, tibinyte is the main author of this round. Please do not spread misinformed opinions.
I can confirm that.
Capital L
As a Tibinyte's friend I can tell you that he has been developing this round since long time ago and he's the main author of round. Please do not spread misinformed opinions. (and reach master)
As a Leafeon supremacist, I can confirm that this claim is baseless. Also green is the best color because Leafeon is the best Pokemon
vanilluxe is better :3
Okay I'm sorry for that, I apologize for this.
Personally, a round is the result of everyone's joint efforts. Whoever thinks of the idea, who thinks the solution, who proves the correctness of the algorithm, who perfects the statement, who creates the powerful test data, and who fixes the issue is actually unnecessary so clearly. What matters is our joint efforts and our friendship.
I believe you had a huge surprise...
Is it rated?
How do they'll send cryptocurrency? We have to have crypto wallet?
This Medium blog gonna help you creating one.
As a tester I have nothing more to add than "Good luck!" and "May the God have mercy on you", because the problem setters surely don't know the definition of this word.
I assure you, tibinyte knows what mercy is, it is the only hero I can play on overwatch
Time to become CM now ;)
Sa nu iti fie cu suparare dar...
yup, you can Shivu!
G Gaming
Time for Remontad
Oooh wow! 58 people contribute to making this round happen.
Aiming green in the green round... Wish me luck :)
Wish me luck hope i become green after this contest.
Hope I will get GM. :)
Oh.. you are close to 2400. Wish you luck for today's contest, hope you become GM..
Same D:
Frate, iti zic io, ajungi si tu (grand)master.
Marinush
I have just realized that I read statement of problem E incorrectly, I thought that we can shift only whole string D:
You too? Me too!11!!1!!!1
Yeah, so sad :(
Congratulations on reaching GM!!
Thanks!!
round need to be unrated, because it is round
How do they'll send cryptocurrency? We have to have crypto wallet? someone can answer to this question plz!
Create a wallet on this app; this'll give you a wallet address
https://tonkeeper.com/
P.S. Checkout the TON username market on telegram : https://fragment.com/ where you buy and sell in TONs
I've created my wallet address and update my profile but did not receive the prize yet. Would you like to tell me the reason or what should I do to receive the prize?
Yes, you'll have to provide your wallet address to receive prize.
Here is the list of TON wallet applications: https://ton.app/wallets
Who should I provide my wallet address to?
In CodeTON Round 2 there was a Codeforces message from System, containing link to form. So I think you should wait for that message (it will be visible in notifications panel).
me
Will score distribution be announced briefly before the beginning of the round?
It will be posted along with the editorial as to not spoil anything about the round
Hope that I will be Pupil after this round
Score distribution?
it is unrated
In the previous CodeTON rounds, I lost my rating. Hope Today I will gain plus point.
Love to see short statements and straight to the point.
let's go
time to + 100
Haha prediction
Last few contests gave me cancer
What is the conversion ration TON to INR ??
How to optimize E from O(n^2) to O(n) or O(nlogn) ?
Good problems, very good D and E was easy
How to solve D? please!! QAQ
whats the logic for D ?
There arent any logic just print("Hello world")
How to calculate the number of numbers from 1 to M coprime to N ?
Factorize N, and then calculate how many numbers between 1 and M are divisible to any of the number factorized using the Inclusion-Exclusion formula:
https://www.geeksforgeeks.org/inclusion-exclusion-principle-and-programming-applications/
Can be done Using Inclusion Exclusion For Example Let prime factors of N be 2,3,7,5 Then ans = M — M/2 — M/3 — M/5 — M/7 + M/(2*3) + M/(2*5) .... — M/(2*3*5) — M/(2*3*7) ..... + M/(2*3*5*7) Given the range of Number we are working on this problem , There will be max 10 distinct prime factors of N so we can generate all 2^10 combinations and get the answer
I did this and I TLEed on test 12??
You factorize every $$$v_i$$$ and it obviously exceeds time limit $$$O(n \sqrt{m})$$$. You only needed to find prime factors of $$$\frac{v_{i - 1}}{v_i}$$$ because there are $$$O(\log m)$$$ such elements greater than $$$1$$$.
There may be a large number of a[i]=a [i+1]. In this case, you only need to do: ans=ans*[m/a[i]],which only do O(log n) times calculations.
https://cp-algorithms.com/combinatorics/inclusion-exclusion.html#the-number-of-relative-primes-in-a-given-interval
https://www.acwing.com/blog/content/19417/
using principle of inclusion and exclusion.
Took me 40 minutes to search and read about Mobius function(Problem D). Not sure if there is any solution that doesn't utilize it.
Use the Inclusion-Exclusion Principle.
Yeah, I thought about that one too. But I believe that I won't be able to implement in time.
I thought that would maybe time out. Took me an eternity to get the Mobius solution to work.
It won't be time out. Think about this, this principle works on a[i]/a[i+1], and the product of them is a[1]/a[n] which isn't more than 1e9.
It won't time out because, you will apply factorization and inclusion exclusion stuff only when $$$a[i] != a[i-1]$$$. The prefix gcd can only change $$$O(log(m))$$$ times, because everytime the gcd changes, it has to reduce at least by a factor of $$$2$$$.
What was logic for C , Solved D but was not able to process C's logic.
Consider the xor of the two arrays, you will notice something ...
Some useful observations are:
How to round number in D?
If you think of the number I think of, you have to round it down :)
Upvoted the contest for the story behind Problem E. I couldn't focus on the Problem, because I had to show the story to my fiancée and my brother and needed to hype it. Beautiful Daemon Targaryen. I would upvote more if I could.
I still didn't watch episode 10 of HOD :(
Did anyone solve D using Euler's totient function?
I used about 10 minutes to think about the conclusion of problem E but used more than an hour on coding. Anyway, I think this round is the best round I've ever participated.
UPD: after I solved problem D I got rk20. :) (though my final rank is 200 :(
HAHAHAHAHAHAHAHA
Literally dying atm. Could get a grasp on D (Yes, I did think of inclusion-exclusion here and there but did not find a way to preprocess the values of the mobius function. Did I want to copy paste an overkill $$$O(n^\frac{2}{3})$$$ method to preprocess prefix sums of the mobius function? Hell no.) but couldn't finish. C felt hard, like, very hard. Might be even convinced that C > D if C was after D.
The answer is only possible if for all i either a[i]=b[i] or a[i]!=b[i]. Just make all a[i]=1,you'll observe that all b[i] become either 0 or 1.If they are all 0 just do 1,n so all a will be 0 and b will remain 0,else if all b are 1 then do (1,1) (2,n)
Yes. I did operations on $$$[i,n]$$$ for all $$$i$$$ such that $$$b_i$$$ and $$$b_{i-1}$$$ are different. Then $$$b$$$ consists only of $$$1$$$s or only of $$$0$$$s. The same goes for $$$a$$$. Then you just need to look at $$$a_1$$$ and $$$b_n$$$ (they did not get changed yet) an accordingly make everything $$$0$$$.
I always lose rating in div 1+ div2 contest any suggestions…?
I guess, in div 1 + div 2 contests it is more important to solve the earliest problems fast enough (since there will be more people solving the same amount of problems, relatively speaking). Interestingly, for me it is the other way round: I always win rating in the joint contests...
How to solve E ?
Take a segment. Let's call $$$C$$$ the number of closing brackets and $$$O$$$ the number of opening brackets. Let's call $$$M$$$ the minimum value the prefix sum of the segment reaches (Opening bracket is $$$+1$$$, closing is $$$-1$$$). The cost of a segment then is $$$max(0, O-C)+min(0, M)=max(0, O-C)+M$$$.
$$$M$$$ is the amount of mismatched brackets. We can use a rotation to fix one of them. If we have opening brackets left to distribute, we can also use them.
$$$max(0, O-C)$$$ comes from the need to balance the amount of both, opening and closing brackets. But we only need to calculate more openings, because more closing ones is already taken into account by $$$M$$$.
You can calculate both parts of this sum for all segments idependently by iterating and doing confusing calculations. See 179633595 the two blocks after
long long ans=0;.For me it was easier to visualise the bracket sequence as a graph of the prefix sum and then look at area on the graph which both of the terms contribute.
Very clean code and solution, thank you! I knew that the solution is very clean, but did not have the skill to find it tho.
E was nice. Until the last 40 minutes, I thought that the first operation can be only applied to the entire string. That led to a much more complicated problem. :(
Wow... I was thinking and thinking with that misunderstanding of the first operation for the whole contest. I got to read the statement a bit more carefully.
Me too, I have written two brute-forces to understand that it's not the case...
And I realized only after reading your comments that we can apply to any substring :(
How to solve problem E? The most I can do is a brute force O(n^3) solution.
Great contest!Congrats to the authors!Cool problem D, unfortunately I didn't solve it.I'm waiting for editoiral!Thanks!
Очень классный раунд, большое спасибо авторам, задача D просто супер!
Один из моих самых худших раундов
Me After Solving A & B :')
Can anyone please explain how to solve problem C with intution?
Consider A^B. Every time we conduct an operation A^B would be XORed by 111...1. So for a YES case, A^B would either be 000...0 or 111...1 after whatever operations. Now you just need to make A to 000...0. In the end, B is either 000...0 or 111...1. Then it's easy to make a few more operations to get job done.
Why the time limit of G is 3s... My FFT solution passes. It does not seem to be the intended solution.
Congratulations to conqueror_of_tourist for not only living up to their username, but also becoming LGM with Python!
you also achieved the goal of your username with python only.
Countforces
OMG bicsi the legend
I wasn't able to solve A, with just looking at the problem and understanding it, I saw that in the correct cases, position 0 had an 1 or position 1 had a 2, so intuitively I went on and did an algorithm that checks that case. Too bad for me it was just when it started with 1.
But can someone explain why is it when it starts with 1? I did it so if it's 1 or 2 at the first 2 positions, i.e. arr[0] == 1 or arr[1] == 2 then yes, else then "No".
before u completely look at my answer read the question once for clarity..... constraint : i < j < k 1st position element has to smaller than kth position element element at 1st position cannot be changed.... but using 1st position you can swap any positions of j and k .
so the smallest possible element that can take 1st position must be one .
Problem D is similar to this problem which I proposed to codechef before.
Sorry, but I didn't like this round at all:
A: just one simple observation
B: just one simple observation
C: just one simple observation
D: just find number of coprime with n not greater than m (testers in comments, is it interesting? Really?)
E: closed this problem as soon as I've read. Yet another "count some *** for all subsegments"
Can say nothing about F+, because didn't read
No, don't misunderstand me, each problem is good. But as set of problems in one contest...
I'm sorry that you found the first 2 problems of the contest(which are supposed to be easy) too easy for a candidate master / master, I will talk to tibinyte and kindly ask him to give out some smart and well hidden minimum cost maximum flow with a lot of observations and implementation details for problems A and B in his future rounds. As of C, consider it a simple observation for you, judging by the counter of solves it was just as hard as it had to be and I also needed some time to figure it out(but I might also have some skill issues so ignore me if you want). I really liked problem D because of its "smooth" solution that included some simple math and observations, so I found it interesting and I am sorry that this does not fit your view. Your argument about problem E is probably by far the dumbest thing I read on the internet today and this really means something as I've seen a lot of dumb memes today. Anyway, I am sorry that you didn't enjoy the round and wish you good luck in the next ones.
First and foremost, L
Second, this is not how you argue, this is how you correctly argue this is satire, by all means the purpose is not to offend anyone
*: (although, admittedly, it can determine the quality of the round as you stated-- I won't argue with that because I am not in the mood for jejune disputes)
Where have I said this?
It's my point: this is "one observation problem". You either find this observation->"ez ac" or you don't find this observation at all->you can't solve problem. This argument is applied to A and B
It's your personal opinion and I've shared mine.
It's not argument, it's my personal opinion. I don't find problems which require some counting on all subsegments interesting. I didn't solve D incontest because I'm dumb, but if I solved D, I would skip E.
The dumbest thing is "This contest is the most bad/good/... contest ever" comments without any details. I tried to share my opinion about whole problemset why I didn't like this contest. And seems that you misunderstood my initial comment. Once more: every problem is good. But you don't find problemset good if every problem is about, for example, geometry, do you?
"you found the first 2 problems of the contest too easy for a candidate master / master" — I just wanted to point out that it is a normal fact that you found them easy because you have a higher rating than the people that should find them challenging, I didn't want to say that you mentioned this, because you didn't.
"It's my point: this is "one observation problem". You either find this observation->"ez ac" or you don't find this observation at all->you can't solve problem. This argument is applied to A and B" — I find this quite common in the modern day competitive programming where problems are more and more based on tricky observations, I wouldn't say that I love it, but we should adapt to these kind of problems if we want to do CP, and if not, as we say in Romania, "ayaye".
"It's your personal opinion and I've shared mine." — I respect that.
"I don't find problems which require some counting on all subsegments interesting." — I get that, but in a contest(especially in a serious one with a higher stake like OI or ICPC) you can't just say that you don't like a problem, you just have to try to solve it because you wanted to take part in that competition(I will assume that no one can force you to take a contest if you do not want that).
"I didn't solve D in contest because I'm dumb" — I know this is a bad feeling, but you probably just missed out on something, it happened to all of us, no need to be so harsh about it.
"The dumbest thing is "This contest is the most bad/good/... contest ever" comments without any details" — I agree that this is usually toxic and people tend to say that after a round that got them positive delta, but my opinion as a tester was just that the round was good and recommended others to try it.
"But you don't find problemset good if every problem is about, for example, geometry, do you" — No, I do not. I also recommend that you spend some time analysing the problems with editorials and realize that they are not just some combinatorics / dp problems, but also require some clever observations. Also, A-C are not counting at all and E and H are not combinatorics / dp(as I know).
Anyway, I think we discussed more about this than it was necessary. The contest is done and others will come.
Thank you for discussion!
Just one correction: in ICPC you have wider set of topics to choose from and what is more important you have teammates. This allow you to skip/delegate some problems if you don't like it more often, than in personal contests.
Great contest
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Hope updated ratings would changed my rating by 2 points
Hope updated ratings would change my rating by 54 points
problem : https://codeforces.com/problemset/problem/1750/D
input : 4 1000000000 60 30 1 1
output: 595458194
how? can anyone explain?
Personally, I think this E is very good. I can use BIT or segment tree, or even deduce the expression O(n) directly. I really like this problem
in problem D
if m was <= 1e6 , could we solve the problem using Möbius Function?
http://acm.hdu.edu.cn/showproblem.php?pid=1695
It's Möbing time!
My friend rating is 1110 and rank in contest is 9000 by solving only problem and by rating is 926 and got 8200 rank by solving 2 questions...But the worst things my rating decreases only by 6 and my rating decreases by 28....How is it even possible.....Please help anyone
You get more rating points than you should first 5 or 6 contests you participate in, which is most likely to be the situation with your friend.
Alsalam Alykom,My solution for A,B is skipped and i swear i didn't use ideone or another account or anything its my clear solution ! I swear to god i didn't cheat why something like that happen to me ? how to avoid this MikeMirzayanov tibinyte
How do I receive my money?
Where is my ton please?
How can I receive my money?
Has anyone received the prize yet?
Has anyone received their TON yet? The deadline was supposed to be on Nov 26.
Hi. The wallets were collected and sent to TON. Of course, they need several days to process the data.
Is the team still in the process of sending prizes? Or is it already finished and I didn't receive anything due to some mistake from my side?
I didn't receive it either.
same, still havent got anything
I just received my prize a minute ago. Maybe you guys will receive it soon
I also just received the prize :)
I also just received the prize :)
Will this round send NFT trophies? Like the kind of NFT trophy in round 1 and round 2.