Hello!
It is a pleasure to invite you to CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)! The round will take place on Mar/24/2022 17:35 (Moscow time). The round will be rated for all participants. The problems of the round were authored by FelixMP, and they were prepared by FelixMP and xpov1LL.
I would like to thank the following people:
- Baqtraqking for having the idea of preparing a Codeforces Round and helping with the solution to one problem; Baqtraqking, izanbf and xpov1LL for early help and discussion of problems, and Baqtraqking, xpov1LL and OneStone for proposals that did not make it to the final problem set.
- 74TrAkToR for coordination of the round.
- MikeMirzayanov for the great platforms Codeforces and Polygon.
- Um_nik, Monogon, AlexLuchianov, generic_placeholder_name, TeaTime, EdgarMM19, cescmentation_folch, metatron, plagues, mathusalen, javierlc2000, DIvanCode, Farrius for testing the round and providing feedback.
There will be 9 problems in the round, with score distribution $$$500 - 1000 - 1500 - 2000 - 2500 - 3000 - 3250 - 3750 - 4500$$$. Hope you have fun!
UPDATE: Editorial.
Here is information from our partners:
Hello, Codeforces!
We, the TON Foundation team, are pleased to support the CodeTON round and invite you to the TON Smart Challenge 1 competition, which will be held on our platform.
The Open Network (TON) is a fully decentralized blockchain created by the Telegram team for a mass audience.
The TON protocol was designed by Nikolai Durov — who is a two-time ICPC world champion, a three-time IMO gold medalist, a multiple IOI medalist, and a co-founder of Telegram — and other winners of international competitions. Now TON is being developed by a community of independent developers and teams.
The winners of CodeTON Round 1 will receive valuable prizes.
The first 1,000 participants will receive prizes in TON cryptocurrency:
- 1st place: 1,000 TON
- 2–3 places: 600 TON each
- 4–10 places: 100 TON each
- 11–100 places: 15 TON each
- 101–1,000 places: 8 TON each
Also, the top 15 participants of CodeTON Round 1 will receive branded hoodies.
In addition, a separate TON Smart Challenge 1 contest will start on our platform on March 28. We invite you to join this competition as well.
You can read more about this competition here:
We believe that the problems of optimizing the efficiency of smart contract code execution on the TON blockchain may be of interest to participants in algorithmic competitions. The development of smart contracts is a case where the experience of optimization earns money by definition because a network fee is paid for each operation on the blockchain.
We wish you good luck at CodeTON Round 1 and hope to see you among the TON Smart Challenge participants!
UPD: If you have got into prizes or just want to join the TON, then register a wallet, follow one of these links: https://tonkeeper.com/ or https://wallet.ton.org/
It seems that a TON of interesting tasks are waiting for us
Another cryptocurrency contest
Good luck everyone!!!!!
25 USD for the first place? 37 cents for the 11th place? What a joke
Edit: forgive my ignorance, there's two currencies both listed as TON, if it's the other one, then the prizes are quite decent
I think it's ~1800 usd for the first place
ton coin and ton token are different , i guess
Yeah...ton token is a crypto currency that operates on the Ethereum platform and Ethereum is a decentralized blockchain platform.
TON to USD: https://coinmarketcap.com/currencies/toncoin/
Yes, I was confused by this: https://coinmarketcap.com/currencies/tontoken/
Why is the prize distribution so weird :/ For example, 1000th and 101st places are totally different levels of skills, I believe it would be better if they were distributed like global round points.
omg Catalan round
Are you talking about Spanish lottery?
There are two different competitions being announced. I didn't notice that at first.
Organized by spanish olympiad problem setters, willing to meet you in the final next week
How many problems will there be in the round? Is the score distribution available?
Still no information, sad…
you guys preparing 16+ hours for contest by score distribution?
Well by that you will know some difference between problems and like now you see that you have only 2 hours for 9 problems, which is kinda weird
All the best to everyone
Wow, crypto rewards
Problem A: write a protocol, Problem B: write a protocol .... last problem: write a superhard protocol
Please don't make this as the recent Codeforces Rounds where everyone from newbie to expert can easily do ABC and D can be done by only CM+.
From the past few contests, the difficulty gap between C and D is very high compared to any other problems. I request the setters of the upcoming contests to make the rounds balanced for everyone. Hoping it to be a good contest. ＞︿＜
This might be a stupid question, but is Codeforces moving to 7:35 as the standard competition start time? I checked the upcoming contests; all of them are starting at 7:35
If my googling serves me correctly, Russia does not observe daylight savings time (while the USA does), so CF contest times shift for Americans when DST begins and ends.
Oh, that makes a lot of sense! Thanks!
What about system of contest ?! Held of Regular codeforces Round Or ICPC Rules Also, what about number of problems :(
Just curious, I want to ask how the bonus is distributed, is the winning user providing the cryptocurrency wallet address, and then you send the currency to the wallet?
How To become Specialist in this round ?? Wrong Answers only
Submit Wrong Answers Only.
Step 1. Kidnap Tourist
Step 2. Go to the nearest Park Area.
Why to trouble tourist when you can just kidnap the author himself. Don't get offended but you guys are pretty bad criminals
9 problems contest o_O
Is tourist participating?
I am tourist, scuza
He has registered
Do you think tourist is gonna make record by achieving >= 4000 in this contest if yes then upvote, if no then don't vote
Ninja technique of increasing upvotes
He learnt from the best
Yes : No :
Tourist got TLE'ed
How much is 1000 TON?
1800$
Scuza
9 problems for 2 hours, what could possibly go wrong..
A lot of those problems will probably be speedran by top ppl.
Good luck everyone!!!!!
I know I won't win anything but I hope I keep my color XD
Good luck guys, it'll be fun.
The Spanish Olympiad last year was really interesting, so I'm excited for this round!
Probably the shittiest round of my life
same
I hate
Problem B(:i found B harder than C :(
but I liked the challenge and it was a good feeling when I found the idea and solved it.
what is the logic behind problem C?
Having a predicted negative delta even when currently in first place is so sad. :(
And then he strikes again with a hack.
Then he failed system test
where is the rating change page.
Wait for the system tests
Legendary battle!
Mathforces
you was warned:
The TON protocol was designed by Nikolai Durov — who is a two-time ICPC world champion, a three-time IMO gold medalist,How to solve D?
I submitted my solution when it was 0.03 s but it said contest is over. So can't say if i am right or wrong. But i think it should be,
If n is odd, the ans is 2.. If n is a power of two, then -1 Else n can be written as 2^r * q... where q is odd.. then min(q, 2^(r+1)
Can someone say if i am right or wrong. If I was right, i would be very mad as I just got wrong answer at first by accidentally giving max in the place of min. And when i submitted it said contest is over
You are right
.
where q is prime
If N=42; Then 42=2*3*7 . So min=(2,21)=2 ; According to your logic the ans is 2. How can we make 42 with 2 elements having remainders {0,1} ?
well he said min(2^(r+1), q) in case of 42 r = 1 so ans is 4.. you can make 42 by using 4 elements 9 10 11 12
sorry for my wrong eyes:) yes ,you are right.
Thats why i wrote min(q,2^(r+1))... sorry for writing wrong at first
It can be shown that any number x can be obtained by defined operation if and only if 2x can be written as product of two numbers a and b with the condition that a and b are of different parities and none of them are 1. k is equal to the minimum of them. You can obtain this by observing the following: 2x = k*(k+1)+2nk = k(k+1+2n) where n is an integer. My AC.
Minimum sum with k numbers is $$$k*(k+1)/2$$$, and remainder will be 0 if $$$k$$$ is odd and $$$k/2$$$ if $$$k$$$ is even. If $$$n = 2^k$$$ answer doesn't exist, otherwise let $$$n = 2^k * p$$$, if $$$p*(p+1)/2 \leq n$$$ (since p divides n) answer is p else answer is $$$2^{k+1}$$$ (since $$$n = 2^k$$$ (mod $$$2^{k+1}$$$)
A fact holds: $$$N$$$ is a $$$k$$$-good number, if and only if $$$N \le \dfrac{k\times (k+1)} 2$$$ and $$$(N - \dfrac{k\times (k+1)}2) = 0 \pmod k$$$.
Let's look at the second equation. if $$$k$$$ is odd, it means that $$$k\ |\ N$$$, otherwise $$$\dfrac k 2\ |\ N$$$. and with the first equation, we can make a guess:
Expressed $$$N$$$ as the product of an odd number $$$p$$$ and an even number $$$q$$$, and one of $$$p$$$, $$$2\times q$$$ works.
It's easy to explain why it's true. From the previous observation, we know that both two numbers satisfy the second equation. As the first equation can be transferred into $$$k \geq \sqrt {2 \times N}$$$，but $$$p \times (2 \times q) = 2 \times N$$$, so if both of them obey the equation, then $$$2 \times N = p \times (2 \times q) < \sqrt {2 \times N}^2 = 2 \times N$$$, which is absolutely wrong.
Some corner cases here:
if $$$N$$$ is smaller than 5, we can just add some if-else to deal with them.
if $$$N$$$ is an odd number, and it's greater than 4, then $$$N$$$ must be a 2-good number.
$$$2^x$$$ is not $$$k$$$-good for any $$$k$$$.
i don't see any pattern in D x_x
Problem D is solved by prime factorization?
No, isn't possible to factorize number up to 1e9. I think there is idea to make ansers 2, 4, 8... or some divisors of n
I submitted my code when it was 0.03 s but it said contest is over. Can anyone say why?
Maybe there is a delay between your computer and the site.
lol, tourist prevented rating loss by hacking. Also he's still in div 1 after halving his rating
Wow, just tying 1st place causes rating loss for him
tourist got TLE'ed
I hate Number Theory :(
Come on, Number Theory is pretty interesting
1 hack attempt made a plot twist
press F to pay respect
How to do F? I kinda figured out you need to find an MST where the $$$a_i + a_j$$$ part of edges add up to 0. However, I am not sure how one would do that though.
They don't need to, as long as there exists lines (representing tree costs) going up and down it'll be bounded from above. Your idea doesn't apply in test case 4. That being said, I don't know how to solve it.
The number of possible MST is at most n-1.
That is :
sort the sequence .
There is a number k :
for all i<=k, there is an edge (i,n) .
for all i>k ,there is an edge (1,i)
I think B is much harder than C
B is easy! You just need to find 2 numbers whose difference is k
Tourist surpassing 4000 today.
He got TLE'ed.
Can anybody tell me the predicted rating for tourist....i don't have the chrome extention
my extension is showing +60
Guess forces
Totally agree! I made lots of guesses when solving problem B, D, E and F.
It's like, intuition tells me this algorithm is right, so I write it down.
ad-hocforces.
I found a mistake in my code for G in the last minute but I failed to submit it:(.
I think the contest time could be a bit longer.
It passed, getting a bit sad:(.
Same happened with me in F, my solution was overflowing and I realized it after submitting (WA solution) in last 20 seconds. I got AC now :(
What in the world is problem C???? I'm probably the only one who could do D but not C. (cries for 9 consecutive contests)
if not exist 1,all number can mod themselves if exist 1, for Ai,it need to mod Ai — 1,if exist Ai — Aj == 1 then ans is NO else YES
how you solved D
Found C way easier than B and D, everyone is different
If you choose x as maximum number in array then only x becomes 0 and others remain same. Repeat few more times and all will be zero. there are corner cases with 1. Help me with D please!
First, think of the condition of an integer $$$n$$$ to be a k-good number.
$$$k=2$$$, $$$n=3+2x$$$
$$$k=3$$$, $$$n=6+3x$$$ (For all multiples of 3!)
$$$k=4$$$, $$$n=10+4x$$$
$$$k=5$$$, $$$n=15+5x$$$ (For all multiples of 5!)
$$$k=6$$$, $$$n=21+6x$$$
$$$k=7$$$, $$$n=28+7x$$$ (For all multiples of 7!)
(where $$$x \ge 0$$$)
and so on..
You can run a brute force for all $$$n$$$ from $$$1$$$ to $$$100$$$ on your computer. You will notice that: if $$$n$$$ is an odd number, than it will always be a 2-good number. If $$$n$$$ is an even number, then $$$k$$$ can be determined by $$$n$$$'s lowest bit.
For example, we have the condition $$$k=8$$$, $$$n=36+8x$$$, which works for $$$n$$$ which have $$$4$$$ as their lowest bit. If $$$n \ge 36$$$, then $$$k=8$$$ is definitely an answer. If $$$n < 36$$$, then we will have to check the divisors of $$$n$$$. We can divide $$$n$$$ by its lowest bit, the result will definitely be $$$n$$$'s divisor.
^_^
Where can I take my 8 coins and how often will you do same rounds?
I am the guy hacked by tourist... no just kidding.
Congrats, to the king!
Edit: Oups, that aged badly :(
I solved A,B,C but my score is very poor kkkk..
Maybe I have witnessed history that the T God reached 4000
Is there any polite way on codeforces to express the thought "I didn't like the contest/problemset" so that MikeMirzayanov wouldn't come in the comments and write a huge paste, how am I wrong to belittle the work of the authors and coordinators?
When has he done this :O
Surely hasn't happened to me
For example this commentary...
I hope you do not seriously think this comment is an acceptable way to express your dislike towards the contest.
Saying "I didn't like the contest" is totally fine. Adding a few more explanations and constructive criticism would be better. You can actually find an example below.
thanks for the great tasks
The main idea of G is very similar to this problem: https://codeforces.me/problemset/problem/325/E
But I'm not mad as it is quite an old one and actually is one of my favourite problems ever.
I have quite funny story about it. That problem I linked is actually exactly the algorithmic version of 6th problem from finals of 56 PMO. When I participated in that Codeforces contest back then, I didn't like the mid-difficulty problems and decided to ragequit midway through (I guess I was just bad lol). After 10-15 minutes I thought "maybe I will at least read E" and came back to read it only to realize that it is one of my favourite problems ever and started coding it frantically. I was really tight with time and in the end I managed to implement it only to lack literally a second, because I did not manage to click "Submit" on time. And of course when I was allowed to submit after the contest it indeed turned out to be correct and would bring me from ~300th to ~30th position and would be my first ever Div1E problem accepted (I did not manage to get one for 3-5 years after that)
Pollard Rho algorithm passes pretests for D... :(
D is very simple. Here not need any such algorithms
please share your approach on D
so krvk55 has become a celebrity
How do I redeem my TON?
whats wrong in this logic for c ans is yes when:- 1. all are already equal. 2.arr does not contain 0 and 1(we can divide each number with itself to get rem 0). 3.if 0 is present, 1 is absent(0 and 1 cannot be changed). 4.if 1 is present,2 is absent(1 cannot be changed, 2 can be changed but only to 0).
try n = 3
1 11 12
if 1 is present, there should not exist ai = aj + 1
Just for my curiosity, if tourist did not make a successful hack and shared the first place with jiangly, would he still got -38 delta as CF predictor says? If so, how is it even possible?
I guess its since he tied with someone with a lot of rating below him(?)
Here is some feedback on the problem set:
Thanks to the authors.
D can be solve in $$$O(\log n)$$$. It's just enough to divide into $$$2^x \times p = 2n$$$ where $$$p$$$ is odd, and the answer would be $$$\min(p, 2^x)$$$, with a failure if $$$n$$$ is a power of 2.
Thank you for your feedback. Could you please elaborate on why you thought F was standard, for example linking to a similar problem?
You are welcome.
Regarding F: The statement is artificial.
The solution has three independent ideas:
A problem which can be split in three independent ideas, unless one of such ideas is clearly more deep than the others, it's not the best problem as it ends up being the sum of three standard problems. But let's go deeper:
I don't see why you gave the problem with an arbitrary $$$t$$$, instead of asking to compute the MST for $$$c_{ij} = a_ia_j + a_i + a_j$$$ (or even for $$$c_{ij}=a_ia_j$$$). With $$$t=1$$$, Step 1 and step 2 are exactly the same (with $$$t=0$$$ Step 1 disappears), but step 3 disappears and the implementation becomes easier (which is a plus in a contest with 6 problems to solve in 2 hours). If the answer is "Because the problem would have been too easy", I would answer with "It's never a good idea to make a problem harder just by adding an obfuscation layer which requires also some implementation effort".
Thank you for the detailed feedback. I agree that the statement is somewhat artificial.
Also, I have seen how you have posted those problem-by-problem feedback in each of the rounds and I must say it is very helpful for problem authors.
I understand where you're coming from, but just to put a counter-weight — I don't share your views and I think this problem is totally fine. Maybe not the most exciting one, but not one that turns me off either. For me adding the $$$t$$$ parameter surely makes the problem more attractive. A bit different way of looking at it was that "each spanning tree gives a linear function and we take minimum out of all of them, hence we have piecewise linear concave graph". Investigating whether it is bounded was a nice starting point to get some understanding and since it is concave we can ternary search. Tbh I did not even think of a $$$(a_i+t)(a_j+t) - t^2$$$ reformulation even though that should have definitely crossed my mind, but I managed to get around without doing it either way.
Why such logic for C doesn't work?
We can transform any number x to either 0 or 1 by % x or % (x — 1) (We have sorted all of them and now making tranformations from higher to lower x). We have some limitations such as we can't transform 0 -> 1, 2 -> 1 and 1 -> 0. So the answer is "no" <=> we have (0 in array || 2 in array) && (1 in array). Otherwise the answer is always "yes".
Where am I wrong?
150748690
what if two numbers are adjacent? try 1 4 5
Check this test:
The answer is
NO.F! Thanks!)
For n = 3, 1 4 5 answer is NO.
A
constructive algorithmsC
constructive algorithmsD
constructive algorithmsE
constructive algorithmsF
constructive algorithmsG
constructive algorithmsA
competitive programming problemB
competitive programming problemC
competitive programming problemD
competitive programming problemE
competitive programming problemF
competitive programming problemG
competitive programming problemH
competitive programming problemI
competitive programming problemThe only problems out of these that I would classify as constructive problems are E and G. The rest as constructive problems is a super stretch
No important algorithms were involved in the solutions, atleast for us div 2 participants. Almost all problems could be solved in 4-5 lines of code. Overall the contest was not balanced I would say
That I can't refute. However that does not imply these were constructive problems
I must say I like the problems. So clear, concise, and to the point. I kinda don't like the problems which revolve around a story or too much information to even just understand input and output format.
FST moment for tourist
Tourist system test failed T_T
problems a,b,c,d need only math skills not programming
Got FST on D , from less than <1000 before system testing to 1765 ;(
same...but I went from 1200 to 1800 :(
D. Strange, but it works...
could you prove/explain your approach when n is even and not of the form of 2^k
nope, my intuition could, but I'm lazy ;)
Basically, the task asks us to find a $$$k$$$ where $$$k$$$ divides $$$(n - \frac{k(k - 1)}{2})$$$. Also, there is an extra constraint that $$$\frac{k(k - 1)}{2}$$$ should be less than $$$n$$$.
A simple observation is that if $$$k$$$ is odds, $$$k$$$ divides $$$\frac{k(k - 1)}{2}$$$. Otherwise, $$$\frac{k(k - 1)}{2} \bmod k = \frac{k}{2}$$$.
Suppose that $$$n = 2^t q$$$ where $$$q$$$ is odd number. If $$$1 < q < \sqrt{n}$$$, using $$$q$$$ works, because $$$q$$$ divides both $$$n$$$ and $$$\frac{q(q - 1)}{2}$$$.
On the other hand, $$$2^{t + 1}$$$ also works. The reason is that $$$(n - \frac{2^{t + 1} (2^{t + 1} - 1)}{2}) \bmod 2^{t + 1} = (q - (2^{t + 1} - 1)) \bmod 2 = 0$$$.
One more hack to 1000 TON. The lesson learned from the contest the bucket count is different for different versions of C++.
Thank you for participating!
If you have got into prizes or just want to join the TON, then register a wallet, follow one of these links: https://tonkeeper.com/ or https://wallet.ton.org/
Tomorrow, I will ask all prize winners to fill out a form with their wallet address (48 character string).
UPD: Here is the link to the form: https://codeforces.me/userForm/203c74605996e40f
21 hours have gone
30 hours have gone...
Did I miss Mike's message or did Mike forget about it?
36 hours have gone..
45 hours have gone...
Did I miss it?
46 hours ago have gone... Where is form?
LMAO It seems you all have won a prize here for the first time LOL XD.
I understand we have a long wait?))))
prize comes with a wait
where is the form
41 hours now,where's the form :(
45 hours have gone.
More and more hours, what should I do?
More and more hours, what should I do?
More and more hours, what should I do?
More and more hours, what should I do?
More and more hours, what should I do?
I believe that before distributing a prizes you should take a closer look on participants who made to top 1000 with newly created CF account (after round announcement to be precise). It looks like some already existing users may have created alts and rewrote their solutions a bit to not get caught in order to get more coins for making into top 1000. One such suspicious user is forcoin (even name is suspicious, doesn't it?). Looking at his submission 150775063 you may notice declaring variable
long long y=n;with further usage it instead of n without any change. Typical obfuscation thing.Found even better example 150736946:
int x; cin >> x; f[x]++; a[i] = x;without further usage of xif (f[a[i] - k] > (a[i] - k == a[i]))— the audience award for the most sophisticated way to say0considering that k always positive :)BTW, account was created half an hour before a contest start. At the same time forcoin's account was created 3 minutes after contest start.
do you try to find 7 most strange participants among 1000, baka?)
You caught me! :)
But at the same time I'm always trying to fight plagiarism and rules violation (especially when it's not just "virtual points" at stake) and this time I'm sure there is some illegal stuff going on.
maybe yes, but it is not ok to suggest that some solutions is not honest because them looks like not honest and on them is label "not honest"
I'm not asking to consider these solutions not honest just because it looks so, I'm just pointing that they are suspicious. MikeMirzayanov may have some better criteria of checking that then just a code analysis. E.g. if CF servers store IP of every session — he may look if these users were accessing the website from same IP and judge if I'm right based on that. Or if there were some other users taking part in the contest from same IP as one of these (to prove that they are alts) etc. The code weirdness is just a signal for further investigation — not a resolution. And all what I'm saying is that these users are suspicious enough to do such investigation.
IP-checking is bad too. maybe two people have solving contest from one IP but from different monitors. in some university, for example.
Why i failed a system test in B and my complexity is O(n log n) searching for a pair whose difference is k??
unorderset and unordermap in c++ is bad sometimes and take o(n) as it uses not good hashing
So what is a good replacment to use in the future to guarrantee the O(1)
:'(((
custom hash https://codeforces.me/blog/entry/62393
or dont use unordered and just use ordered — O(logn) > O(1) shouldn't matter too much
Anyone failed B due to unordered_map / unordered_set ?
A legend (user slime) used it and got TLE :(
lol, count me in.
First time?
Don't know why, but this one worked out. https://codeforces.me/contest/1656/submission/150739997
UPD. Now it's failing TLE, same code :) https://codeforces.me/contest/1656/submission/150813434
Me : D
I will never use unordered things on Codeforces for problems with > 100 solved in the future.
Todays contest was quite easy i think
No. Your rating will be updated soon
I mistakenly thought $$$n\leq 10^5$$$ in B (actually $$$2\times 10^5$$$) and passed the pretests. How could it be so weak like this...
I think I can avoid this problem if I use
int a[100002],n,k;instead ofint n,k,a[100002];. Is it almost correct?Thanks for the great problemset! This is one of my favorite CF rounds.
I am really having a hard time figuring out if this is a joke or you actually mean it ?
He never tells a joke on Sunday
problem E has a weak system test.
My solution https://codeforces.me/contest/1656/submission/150810889 can pass both the pertest and the system test, but it works in O(n*a[root])
A graph like 99999 nodes connecting with one node directly can hack this solution
Such a case was already present in the system tests. However, in that testcase the central vertex is not $$$1$$$, so your solution passes.
Do you know if it is possible to construct a case against your solution if you start from a random vertex instead of vertex $$$1$$$?
No way, cause it can probably choose a vertex with minimal edges. By the way, the solution can be fixed easily by choose a good vertex
but if a use a leaf as a root then i'll get WA because a[i] is out of [-1e5,1e5]
Highly appreciate the person who writes the problem Statement.To the point and easy to read,no unwanted story and other stuff. Highly NJoyed
No sane coordinator would accept a round where the first 7 problems are geometry, DP or data structure bash, but somehow this is acceptable?
I think that the problems individually are fine, but I absolutely hated the set as a whole, there is no variety at all. None of these problems involves any consideration of time complexity, it's just "figure out a single idea and then write a trivial implementation". No data structures, no algorithms, no DP, just simple greedy, ad-hoc observations and constructions. DE would be better suited for a IMO-style contest with the statement changed to "prove that this is always possible".
Though I know that it is futile to ask given where the platform's contests are heading, I once again have to ask, please, no more rounds like this in the future. It's on the coordinator to ensure that the problem set is balanced over topics, and this round absolutely fails on that metric.
Given your rating and your position in the final standings, I understand you are annoyed because of your performance in this contest. In this contest the most typical topics such as known algorithms or DP were not present as you mentioned, and I assume this is the kind of problems in which you perform the best. However, the most common themes don't need to appear in every contest, so you shouldn't blame the coordinators for your dependence in said themes to perform at your usual level.
Stop making assumptions! All he is saying is that a contest shouldn't contain problems based on just one topic.
and which was the topic on this one?
Given your rating and your position in the final standings, I understand you are happy because of your performance in this contest. In this contest the most typical topics such as known algorithms or DP were not present as you mentioned, and I assume this is the kind of problems in which you perform the worst. However, the most common themes don't need to appear in every contest, so you shouldn't blame the coordinators for your dependence in said themes to perform at your usual level.
I think it is ridiculous to try to refute my complaints by just pointing to the fact that I lost rating. If you think I am complaining just because I did badly, you might want to see the last time a round like this happened. That time I got +14 rating.
Yes, absolutely. I do not dislike this round because this round didn't have DP, because it didn't have data structure problems, or because it didn't have anything algorithmic. My issue is that this round had only ad-hoc problems, which by the way are by far the most common theme on codeforces. When was the last time you saw a round without ad-hoc problems?
Once again, I want to state that I think the problems are not bad. The issue is that there is no variety.
Glad to see someone against Constructive-force.
I have to admit ad-hoc tasks often amaze me, though I barely solve them personally.
Also I would like to add another point that putting the task I in a 2-hour long contest is ... insane. Given the number of definition and lemma in the editorial, may I ask if it was taken from some Algorithmic Graph Theory textbook?
For those, who solved E. Just curious, how did you came up with the solution?
Reading the editorial, I understand the proof of correctness, but don't understand the intuition behind it.
I first rooted the tree. Then I tried to think if I could make each subtree of even distance from the root have sum 1, and each subtree of odd distance have sum -1. Then the only thing left is to make sure the root has sum 0. I believe this ends up as the same construction in the editorial.
(To see why alternating +1,-1 is desirable, try drawing it out on a decently large tree, and examining what each component looks like after removing a vertex.)
Sounds solid. Thanks!
I quickly realized that if S is the sum of all weights of vertices, then S — W[v] must be divisible by deg[v] for all vertices v. My first instinct was to try to force S — W[v] = 0, but this clearly can’t work for all v. As a result, I suspected that the construction would depend heavily on deg[v], and writing out the sample case after that was enough to come up with the construction.
I ended up characterizing all solutions to such a tree. Let $$$s_u$$$ be the common sum of the components when $$$u$$$ is removed. Let the sum of values of all vertices be $$$S$$$. Then when you go from a vertex $$$u$$$ to an adjacent vertex $$$v$$$, you get $$$s_u + s_v = X$$$, so if you color vertices in an alternating manner (say in red and blue), you get that $$$s_u$$$ is the same for all vertices with the same color. Now inductively, you can show that if $$$x$$$ is the $$$s_u$$$ for red vertices, and $$$y$$$ for blue vertices, then $$$a_u = x - (d_u - 1)y$$$ for blue $$$u$$$ and $$$a_u = y - (d_u - 1)x$$$ for red $$$u$$$, where $$$d_u$$$ is the degree of $$$u$$$. This clearly works if you set $$$x + y = 0$$$, and the intended solution uses $$$(x, y) = (-1, 1)$$$.
I considered a case of a path on 4 vertices. First solution I found was [2, -1, 1, 1], but that doesn't look particularly nice, so I kept searching for nicer solutions. Then I found [-1, 2, -2, 1], which looked much nicer. I noted that prefix sums are [-1, 1, -1, 0] what led me to that path IanDeHaan described
Newbie here,
can someone tell me why with unordered_set is giving tle 150812826 but not on set 150813232.
https://codeforces.me/blog/entry/62393
TL;DR — the input is adversarial and the .find() function is reaching an O(n) time complexity
I think tests for D are weak. It's not hard to generate counter cases of naive prime factorization on $$$n \le 10 ^ 9$$$ or pollard-rho on $$$n \le 10 ^ {18}$$$.
Before the contest: Wish tourist to cross 4000 line
5 minutes before contest ends: Rank 2, no hope to cross 4000.
contest ends: Tourist hack others, rank 1! First contestant to cross 4000 !
After system test: Tourist failed in problem G, rank 8, drop back to 3800+.
Life is drama.
Video editorial for problems A-C
Solution to D: It's obvious that when n is odd, we can just let k == 2 be the answer, so the following steps are cases that n is an even number. It's easy to have the equation: k(k-1)/2 + mk = n, m is a arbitrary number. If k is an odd number, then we must have n/k > (k-1)/2 + m. If k is an even number, we can change the equation into 2*n/k = k + 2*m — 1. We can see that the right part is an odd number. So an idea is to divide 2*n into sum * odd, in which sum is a power of 2. If odd is smaller than sum, we can see that 2*n/odd > odd, n/odd > (odd-1)/2=odd/2 so odd is the answer. If odd is bigger than sum, we can let k == sum, 2*n / sum > sum, which 2*n/sum is the odd number k + 2*m — 1.
150775598
Your code is very neat. Thanks for sharing.
Why your code is not that clean. Code Link binarybard257 Why there are so many comments in your code?
I did not understand why n/k > (k-1)/2 + m when k is odd
No m behind.Just to ensure that m > 0
thanks for the clear explanation.
Why is my code giving TLE for problem B? submission:150815444
Please read this: unordered_map is an associated container that stores elements formed by the combination of key-value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined.
Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O(1).
Note: In the worst case, its time complexity can go from O(1) to O(n2), especially for big prime numbers.
It is advised to use Ordered_map instead of unordered_map
Can anyone help me with the corner case for which this might fail(Problem C): https://codeforces.me/contest/1656/submission/150819310
1
3
0 0 1
your code print: YES answer: NO
Thanks Mate!!
Hello everybody! Thanks for your feedback!
I would like to invite you to the online mirror of Spain's Olympiad in Informatics which will be held on 2 and 3 April. Check this blog post to see details. Note that if you want to participate, you should register before this Saturday.
If you liked the problems on this round, be sure to participate! And if you didn't — well, there are some additional different problemsetters in the Olympiad other than me, so you should participate anyways.
Cheers!
Nice, more constructive problems
Good short statements. Everything was easy to understand.
ABCDE were a bad combo of mathy/constructive problems. F was ok and H was nice, but I would enjoy them more in a div1 contest as B and D, with some time left for a more difficult problem.
Please stop using linear scoring distribution in combined rounds. If every next problem is only +500 extra points, you discourage people from switching to hard problems. Spending an extra minute while solving ABC is already more important than spending an extra minute in H. And it hurts a lot if somebody fails a medium problem because it's worth more than a hard problem (~2500 for F and ~2200 for G and H today).
Geometric scoring is much better. If you don't want to use values as big as 6000 points, just decrease A to 250 points.
Strange instructions. We should do this and the prize will magically appear?
It's hard to find Mike's comment among these 250 comments.
"Tomorrow, I will ask all prize winners to fill out a form with their wallet address (48 character string)."
https://codeforces.me/blog/entry/101056?#comment-898377
Geometric score distribution can lead to a strategy, where you solve a problem from G to A. Maybe the contest writer didn't like these kind of strategies.
Why is it bad?
Because that's more like ATCoder: some coders just set a goal(like 4 problems in ARC for me) and solve the target problem first. If that problem takes too much time, they just abort the contest and get unrated. For ATCoder, they set a rule called "rated/unrated participation" and I think this rule is worse than the current one :(
Good point. You indeed can try a hard problem and skip a contest if you don't come up with a solution fast enough. But it's less extreme in CF because the sum of submission times matters. You shouldn't solve multiple problems and wait with submitting. (So I still think geometric scoring is a better option.)
How to redeem the prizes?
I have a TON Wallet now, so what should I do to deal with it?:D
May you generous enough to give it to me?:D
NO, I mean how to get the prize.:)
https://codeforces.me/blog/entry/101056?#comment-898377
Oh, thank you very much.
where is the form for wallet-address? It will be in personal messages?
F can be solved by gradient descent https://codeforces.me/contest/1656/submission/150860293
This might follow from the fact that $$$f(t)$$$ is convex.
Шёл 2022 год, люди до сих пор используют unordered_map и их решения падают на систестах
Jiangly YYDS!!!!!
jiangly yyds！
Is it a joke that the I problem is rated 1800 ? UPD : Now it's rated 3500 xD