কি অবস্থা ব্রো? আবারও চলে এসেছি! (That's Bengali for "What's up bro? I am back again!")
I am super excited to invite you to participate in CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!) which will be held on Nov/23/2024 17:35 (Moscow time). This round is rated for both divisions.
The contest will feature $$$8$$$ problems, with three of them divided into two subtasks each. You will have $$$3$$$ hours to solve as many as you can. The problems are authored and prepared by me and wuhudsm.
I would like to thank -
- TheScrasse and Kaey for their jaw-dropping (
literally) coordination of the round, giving valuable feedback and improving lots of problems. - wuhudsm for being kind enough to use one of his cool problems in the round.
- Alpha_Q and Raiden for discussing tons of problems with me and improving some problems.
- antontrygubO_o for sacrificing his TON by not participating in the round as he knows some of the problems as my past coordinator.
- dorijanlendvaj, _istil, Alpha_Q and nfssdq for being our MVP testers and improving the round immensely.
- Thienu, wuhudsm, jdurie, Farhan132, Soumya1, redpanda, Friedrich, upobir, AlephZero01, NemanjaSo2005, tb_ro, Kawchar85, waidenf, serotonin, dazlersan1, NightW0lf, Too_Weak_To_Anything, Raiden and LipArcanjo for testing and improving the round as well.
- redpanda for creating awesome Manim video editorials for some of the problems.
- The great MikeMirzayanov for the amazing Codeforces and Polygon platforms.
- You, for existing and participating in the round. Also, thanks for giving your best and not quitting. You will get what you want prettyyy soon. Just hold right there
.
Score distribution:
$$$500 - 1000 - (1000 + 1500) - 2000 - 2750 - (2000 + 2000) - 4250 - (2250 + 2500)$$$
Wishing you TONs of luck — hope you have a TON of fun cracking the problems!
UPD: Editorial
UPD: Congratulations to the winners!
And here is the information from our title sponsor:
Hello, Codeforces!
We, the TON Foundation team, are pleased to support CodeTON Round 9.
The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.
Since July 2022, 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 9 will receive valuable prizes.
The first 255 participants will receive prizes in USDT cryptocurrency in the TON network:
- 1st place: 2,560 USDT
- 2–3 places: 1,280 USDT each
- 4–7 places: 640 USDT each
- 8–15 places: 320 USDT each
- …
- 128–255 places: 20 USDT each
All participants will receive Soulbound Tokens (SBT) that reflect their developer rating
We wish you good luck at CodeTON Round 9 and hope you enjoy the contest!
And here's something special: Solve problems and make a difference! Yes, you heard it right, just like my last contest, this time as well you can help the world just by solving problems. I will donate money to the underprivileged people in my neighborhood based on the solve count of each problem by the following measure:
You can check how it went the last time I did this: https://mirror.codeforces.com/blog/entry/96333#comment-907470
Also, the top $$$5$$$ Bangladeshi contestants will receive $$$1000, 800, 700, 600,$$$ and $$$500$$$ BDT respectively from me as a small gift!
Note that neither TON nor Codeforces has anything to do with the donation or the gift.
Great initiative vai.....
Not me guessing difficulties by USD
Then I donated 0.001 + 0.001 USD, I am so happy with that.
I'm proud of the fact that I'm worth at least 0.012 USD :)
Then I donated nearly 0.01 USD...that's amazinggggg
As a tester, I can confirm that this round does indeed have problems.
Best wishes to the round, contestants, and problem setters.
As a tester, I tasted many flavours from the problems.
A tester or a Taster?
toaster
In case of toaster, can I have a slice?
change time/day icpc india clash
Where is the prize for top 256 — 511 and 512 — 1023? :(
As a taster, I found the problems very delicious.
What is the rating distribution??
Bro can't you read?
I have just realized from automated polygon emails that I already seen a problem from this contest (and even have access to it on polygon) since TheScrasse has just commited on it. No one has told me before this that I could not participate...
wuhudsm please do better.
Actually you were coordinating wuhudsm's round but you gave it to me, so this time it's normal you have already seen the problems :)
That's not the point. Also, why should I assume it's a problem I've seen before? The annoucement said that wuhudsm only contributed 1 problem. It's quite likely its a new problem???
No one told me that I have already seen problems before. That is not ok. If polygon didn't send the above email (and you didnt suppress emails), I might have participated?
I only received the message yesterday that YouKn0wWho's round requires an alternative problem, and the coordinator needs to select a problem from my round (which you previously coordinated). We are struggling with selecting problems and fixing bugs. We only confirmed the final problemset a few hours ago. And I expect to notify you after participating in today's codechef round. Overall, I apologize for not communicating with you in a timely manner.
Sorry, I overreacted. I didn't consider that the problem could have been just added......
As a participant, I'll participate!
Why are prizes in USDT instead of TON? Not that I will get them lmao.
MAKISE KURISU!!!!
KURISUTINA!!!
Let's all pay respects to Makise_Kurisu
As a participant I'm Excited!
clashing with icpc prelims india
if possible please change the time/date of the contest as icpc india preliminary contest will be held on the same day 23rd nov 21-23:30. so that we all can take part too!!
After reading this comment we considered moving the round, but unfortunately it cannot be done anymore.
why not if i may ask? just shifting by 150minutes would work ( i have no clue about the underlying things and complexities of rescheduling but yes just curious)
If the round is held at an unusual starting time, the participation usually decreases (maybe also in this specific case).
I see tourist registed for this contest！
easy money
Is there supposed to be a score distribution or is ranking based on # of problems solved (ICPC format)?
div1+div2 is tooooo hard,I always try my best,never beat it:(
The timing of this contest overlaps with the India ICPC Prelims, and I really want to participate in both. Unfortunately, I’m torn between the two. :'(
cringe profile pic sir
better than yours
clashes with Icpc India preliminary round
Looks like a lot of people here don't like India.
wuhudsm orz
Unlike the TON round 8, 256-1023 places lose their prizes, and 20 USDT is much less than 8 TON (8 TON > 8 * $5 = $40 = 40 USDT), which 128-255 places got in round 8.
Their settlement is also without TON now.
What happened to TON?
I wouldn't say it's fair to take CodeTON R8 as a basis for prize comparison. That exact reward system was introduced in CodeTON R2 and didn't change until now. And the average (or actually median) Toncoin price for that time period was ~ $2 which gives 128-255 places in CodeTON R2-R7 less money (at the moment of receiving the prize) than they are promised here. Also, if we keep counting having $2 in mind as a pivot — we'll see that the total prize funds for almost all previous CodeTON rounds are really close to the current one ($20480). R8 is the only significant exception from this rule. What's also interesting about it is that Toncoin price at the moment of publishing R8 announcement was again ~ $2 but jumped 2.5x till the moment when contest actually held. Not sure what was the further story behind it and if TON Foundation actually paid everything in Toncoins like they did before and what was the price of it at that point if they did. But I believe this case (sudden 2.5x jump of prize fund in 1 month) is the reason they decided to switch to stablecoins and it seems pretty reasonable. Yeah, payouts in Toncoin were a good additional advertisement of their own crypto but it got too expensive last time and I would actually be grateful that after R8 incident they switched to another way of doing things instead of dropping it entirely (how many other companies do you know, who were so generous in sponsoring CF rounds and did it so many times?).
That way or another it doesn't explain removing the prizes for 256-1023 places so I agree with a first part of your comment (and couple others below and above). In previous rounds they were able to make happy 4 times more people (kudos to TON Foundation for it!) with the same amount of money so it feels a bit disappointing to see this changing now. But we have what we have so good luck to you and other reds in the race for a prizes this time!
why 256-1023 places no prize this time :(
Let's make it to Specialist this time :)
Fun fact: 11 scoring opportunity is the unique largest for modern (= after CGR1) rated Div1+2.
Should we solve problem in order $$$A-B-C^1-C^2-D-F^1-F^2-H^1-H^2-E-G$$$? Why $$$H^2$$$ is even easy than $$$E$$$?
No, I believe it's more precise to assume that P2 relative complexity is described by P1+P2 score. So the current order does make sense to me although people might want skip some P2's and jump straight to the next P1 in the list
Less prize :(
Will finally take part in another CodeForces Round. Very fun way to spend time. Hope to reach expert.
sorry for asking but what's a Soulbound Token? :/
Is there a penalty for wrong submissions?
All participants will receive Soulbound Tokens (SBT) that reflect their developer rating
What is the SBT Here Brother ,how its works.
hope to continue my form today as well
Hope we all get TONs of TONs!
mathforces
edit: GCDforces
tourist might no longer be Tourist :(
Funny that E can be OEIS'd with a little bit of heavylifting.
I'm not sure if anyone tried OEISing F1 as well, but bruteforcing small cases for F1 is too troublesome. (wait, now I just realized F2 only raised a bit of constraints comparing to F1, this cheese shouldn't be possible ever...)
omg I tried OEIS but failed. but I solved this...
I tried looking on OEIS but unfortunately with the wildcard query
1,2,5,19,_,682which doesn't match the transformed sequence T_TYeah, I fell into the same roadblock as ya. Had to bruteforce as far as I did in the link, and even that would only give me the series of their deltas.
Really liked E
I really like how problem D boils down to a such a simple formulation.
The observation in E that the relation becomes trivial for arrays with inversions $$$\gt 1$$$ is also really cool. Still a bit salty I spent ~1 hour failing to calculate the number of arrays of length $$$x$$$ with 1 inversion correctly but that's totally on me since both the logic and the resulting formula aren't math / case-work heavy at all.
On the other hand, I'm not really a fan of C2. At least with my solution, it feels tougher than D (and definitely more irritating than either D or E) due to the associated case-work.
So it's not just me that suffered E.
Yes, I spent more time to solve C2 than D or E
Animated Video Editorial for the Contest! Problems [A,D]
Link: https://youtu.be/elRvvUbk1J4
Bad C2.
How to D?
using a sieve type of algorithm
292980591
if n is greater than or equal to $$$2^m$$$, then the answer is -1
otherwise, you have to calculate to each index, how many prime numbers it have in its prime factorization, assume this number is in $$$cnt$$$ array
then the result for this index is $$$S_{cnt[i]}$$$ (you have to reverse the set S)
(the first index should have $$$S_0$$$)
I admire Shohag for his consistency in creating inelegant problems
E was availabe on OEIS
How did you find it? I just typed
5, 19, 102, 682and it didn't show anything.https://oeis.org/search?q=1%2C2%2C5%2C19%2C102%2C682%2C5321%2C47071%2C464570&language=english&go=Search
Ough, I just didn't read (and didn't used OEIS before)
what??
I brute forced then searched for it but couldn't find it .
Thank you for AtCoder Regular Contest!
gcd round
Loved the round, cool problems
I donated a total of 0.009 USD (0.001 + 0.001 + 0.002 + 0.005), and I feel so happy about it!
ANIMAL
Why didn't I get TLE with this code?? For C : https://mirror.codeforces.com/contest/2039/submission/292955782
There's an upperlimit on total itarations in the for loop, that is actually
min(2*x, m), so in the worst case scenario there are only2*x = 2e6operations. Moreover, the statement says that the sum of all x from all test cases is at most 1e7, so the complexity of your algorithm isO(1e7).couldn't solve D in 160min, my brain ... 🙃
My brain was absolutely fried on B, I was considering the wrong definition of subsequence even AFTER the announcement came out... even submitted my solution onto a different problem once by accident lol
WA on B round
The bulk of the problems look... too much alike :) .
However, problem H is very nice, and a welcome step away from the prevalent topics.
Thanks for the contest!
I genuinely do not know how to solve C1. For the case x <= y, simply get the factors of x in O(sqrt(x)) time and get all those values XOR x in some set S. Then get all values in S >= 1 and <= y.
How do I solve for the general case? Surely O(sqrt(m) + sqrt(x)) is too slow, right?
y is no more than x * 2(or 4, something like that)
Observe that after y reaches 2*x, y^x will forever be bigger than y/2 and x/2. So you can just iterate up to 2*x and count
Of course every time I get near expert, some bitmask problem comes around and screws me over...
That should tell you something.
Yeah I know I gotta practice bitmask problems then... what annoys me is that they are always so ad hoc that there is not much transferability of knowledge amongst such problems.
I totally disagree with you, the ideia in this problem is very recurrent. Y^X will always be bigger than Y/2 because you will never turn the MSB off and that is the main point. Most of bitmasks problems is usefull to look at the MSB or try to solve bit by bit. Good luck on hiting expert.
too low participant, it's slightly less than 9000 is CF is in decline ?
Perhaps they don't want to participate in the math Olympiad.
Thanks for low time limit in C2
correct me if I am wrong, I tried problem D and I think in the notes the gcd was calculated incorrectly, it was actually lcf..
were we supposed to solve it as if the lcf was gcd?
maybe I just did not understand the problem since I am newbie TT
I'm not totally sure which part you're referring to, but one part of it said $$$a_{gcd(2,3)}=a_1=6$$$, which is correct because $$$gcd(2,3)=1$$$.
ohh yess I thought it meant.. nvm I was too dumb, thank you for pointing the logic, really appreciate that,
I really need some sleep I think, not to mention I spent 1h on that while assuming things that did not exist :)
competitive programming? nah, we gonna do some math olympiad..
can anyone explain d in detail
I just counted throughout the round, liked problem E tho:)
CodeForces ❌ GuessForces ✔️
CountForces today for counting problems in E,F,G
What was this with C2? I have no idea what I did for the solution, just stress-tested and ifed found cases until it passed.
Gcd round indeed.
(x ^ y) must be divisible on min(x, y). Let's calculate y <= x normally so now (x ^ y) must be divisible on x. So we have some i (>= 2) * x, x < ((i * x) ^ x) <= m. If i increases, ((i * x) ^ x) should GENERALLY increase but not always. So let's first assume we get all Is from 2 to m / x(ans += m / x — 1) and then calculate 1e5 before i = m / x and 1e5 after it manually. 1e5 is some random constant so it may fall on systests
No, it worked on systests. No idea why tho
It is indeed clear you do first $$$cx$$$ normally and then you should only get the ones that are divisible by $$$x$$$, and there will be somewhat like $$$\frac{m}{x}$$$ of them. However it can be y > m that converts to y $$$\oplus x \le m$$$, and you also need to if this. But then it turns out your $$$[0;cx]$$$ can be intersecting with your $$$[m-x,m]$$$.
So you start if-ing cases when they are overlapping and then you just add even more ifs found by stress tests.
Not saying it is a bad problem overall, but it is definitely an overkill for C2. There probably is an elegant way to solve without that many corner cases, but I dont believe that's a problem that is always solvable by not that experienced participant even after they got the main ideas.
Also i think 1e5 is a bad constant as $$$x \le 10^6$$$. $$$x$$$ should be enough, and less than $$$x$$$ is not enough -- imagine $$$m = 10000{x}_2$$$ (having $$$x = \ldots101_2$$$), than you can take $$$m - x + 2$$$ and it will give you xor bigger than $$$m$$$.
Probably the easiest way was just to solve $$$m \le 4x$$$ the naive way and do first $$$2x$$$, last $$$x$$$ and then formulas otherwise.
In problem D, why aren't the three biggest elements in S enough? My construction is as follows: let a, b and c be the three biggest elements in S, let a_1=a, a_2=b, and from now on a_i=b if i is odd and a_i=c if i is even. I haven't found any clear contradictions.
then how about $$$a_{15}$$$, for $$$a_{\gcd(3,15)}=\gcd(a_3,a_{15})=b$$$.
Oh yeah, i completely missed that, my bad. So what is the solution?
we can first sort $$$S$$$ in descending order.
$$$a_1$$$ must be the maximum element $$$S_1$$$. From $$$a_2$$$ to $$$a_n$$$, they can't be $$$S_1$$$.
consider $$$a_2$$$, it should be $$$S_2$$$, and all elements $$$a_j$$$ with $$$j=2k$$$ can't be $$$S_2$$$.
So here's the pattern: we can let $$$a_i=S_{b_i}$$$ for every $$$1\le i\le n$$$. Then you can find $$$b_i=\operatorname{mex}_{j|i}{b_j}$$$. Here $$$\operatorname{mex}S$$$ stands for the minimum possitive integers which didn't appear in set $$$S$$$.
so you can solve this in $$$O(n\log^2n)$$$.
maybe I'm a little dumb for using this silly algorithm, but it did reflect my thoughts during the contest.
Countertest:
(Actually the set $$$S$$$ could be any set of $$$4$$$ elements)
You will fail because $$$\gcd(a_4, a_8) = 2 = a_{\gcd(4, 8)} = a_4$$$.
I actually tried using only 4 elements but i got WA on test case 2, this is the submition: https://mirror.codeforces.com/contest/2039/submission/292984209
Yeah, the worst case isn't bounded at $$$4$$$ only.
Think of an Eratosthenes sieve.
n = 8
[a b b c b c b c]
gcd(a_4, a_8) = c = a_gcd(4, 8) = a_4 = c
C2 is bad at all...
$$$CF2039E(n)-2\times CF2039E(n-1)+CF2039E(n-2)=A079752(n)$$$
How to c2?
I had 60 * x and it tled
Had 2 * x and enum (y mod w)? [w = 2 ^ k / w > x]
after y reaches 2^(biggest signicant bit in x)-1, then there will never be a x^y, that y will divide because y will always be larger than (x^y)/2. so we can count up to that, and then we can see that the rest of the numbers must be divisible by x, so we can check how many numbers are divisible in the range of [2^(biggest signicant bit in x),m]. there is an edge case where the last number in the range may not be achievable(because the y that is needed exceeds m), and that the first number outside of the range might be achievable(because the y that is needed actually might not exceed m), so you can just check those 2 edge cases, and thats it.
My solution is $$$O(X)$$$ but relies on a fair bit of casework:
For a fixed $$$x$$$, notice that for any value $$$r$$$, there is some $$$x \oplus y = r$$$ with $$$r - x \leq y \leq r + x$$$.
Note that for numbers divisible by $$$y$$$, we require that $$$x \oplus y \geq 2 \cdot y$$$. Using $$$x \oplus y \leq x + y$$$ we get $$$x + y \geq 2 \cdot y$$$ or $$$y \leq x$$$.
Code — 292947242
Why not allowing digit dp to pass C2? time complexity is 60*x*2, which would work if the sum of x on test cases was bounded by 10^6.
My solution to problem C2.
If $$$x \oplus y$$$ is divisible by $$$y$$$, then $$$y$$$ is less than $$$x$$$. Check it trivially.
If $$$x \oplus y$$$ is divisible by $$$x$$$, then $$$x \oplus y = x \cdot k$$$, hence $$$y = x \oplus (x \cdot k)$$$. We have a sequence of numbers $$$x \oplus (x \cdot k)$$$, all of them are divisible, but the sequence itself is not increasing. Assume, at first, that for $$$k \le \lfloor \frac{m}{x} \rfloor$$$ the constraint $$$x \oplus (x \cdot k) \le m$$$ is satisfied. Then iterate on segment $$$k \in [\lfloor \frac{m}{x} \rfloor - x \cdot 2, \lfloor \frac{m}{x} \rfloor + x \cdot 2]$$$ and check it there manually.
I solved C1 but and spent about 1 and a half hours on C2 but didn't get a single idea. Can someone provide hints?
$$$y-x \le y \oplus x \le y+x$$$
After this, we can come to some conclusions divide in cases.
Can you please elaborate a bit, since the range is still too large??
we can divide in two cases: $$$y \lt x$$$, $$$y \ge x$$$
As we know, $$$x \oplus y \le x + y$$$ So if $$$x \oplus y$$$ is a multiple of $$$y$$$, then $$$y \le x$$$. Solving in the range $$$1$$$ to $$$min(x-1, m)$$$ is a loop (we don't need to count $$$y=x$$$ now.)
We also know, from $$$x \oplus y \le x + y$$$, if $$$x \oplus y$$$ is a multiple of $$$x$$$, then $$$x \le y$$$.
We need to count multiples of $$$x$$$ that can be written as $$$x \oplus y$$$ and $$$y\le m$$$
Now using $$$x - y \le x \oplus y \le x+y$$$, we know all multiples of $$$x$$$ less than or equal to $$$m-x$$$ (There are floor $$$\frac{m-x}{x} + 1$$$ multiples) can be written as $$$x \oplus y$$$ for $$$y\le m$$$. Now we need to check for multiples within the range from $$$m-x+1$$$ to $$$m+x$$$. Then subtract 1 for $$$y=0$$$ 292996452
Why my approach failed for D ?
Let largest 3 values in set be a>b>c, res[1] = a, res[i] = b if i is prime, else res[i] = c. and handling m<3 with casework.
You need more than 3.
Your code prints
3 2 2 1 2 1 2 1, but for the 4th and the 8th element, $$$gcd(4,8)=4$$$ and $$$gcd(a_4,a_8)=gcd(1,1)=1=a_4$$$ so it doesn't satisfy the requirement.I see, so you need to put decreasing values in each increasing multiples.
UPD : AC!, thanks.
Tourist be like oh shit I am going to be LGM.lol
I hate these contests filled with maths. Almost every ques was XOR or GCD
Solution Problem E here
https://oeis.org/search?q=1+2+5+19+102+682+5321&go=Search
Can you please explain how you got to this solution? Did you brute force for small values and try to find the sequence?
Bingo, because when I saw the statement, I knew that it is impossible, but a lot of people solved it, so I think I should use something like google search :))))))
How do you solve F1? I reduced it to finding the sum, over decreasing sequences of positive integers at most m where all prefix GCDs are different, of 2 to the power of (the length minus one), which I found can be encoded in a DP with O(mlog(m)) states (DP[m][x] represents this sum where the current prefix GCD is m and the last element is x) but I can't figure out how to transition fast enough.
What is wrong here? In C2 i isolated all possible $$$y$$$ values into three groups, smaller, equal, or bigger than $$$x$$$. smaller equal is trivial, while for bigger than $$$x$$$ i claim that only $$$x$$$ can be the divisor, so i count all the multiples of $$$x$$$ which have an MSB which not higher than $$$m$$$'s msb and strictly higher than $$$x$$$'s MSB. Then i subtract all multiples that would result in a $$$y$$$ value which is bigger than $$$m$$$, by saying that for each such multiple, as its xor is with $$$x$$$ bigger than $$$m$$$ there is a prefix of bits where the xor of $$$x$$$ and this multiple is equal to $$$m$$$ in all bits but last, and in the last it is $$$1$$$ while $$$m$$$ is zero. so then i go over all prefixes of $$$m$$$, and if the prefix ends with zero, then i know what the prefix of the multiples that would result in an issue with this bit, and so i subtract the number of multiples of $$$x$$$ which have this prefix.
WA on pretest 2 https://mirror.codeforces.com/contest/2039/submission/292987386
Why put so many problem in a contest? C2 is much harder than D, and I wasted a lot of time on it. Please make the problem set in the right order.
we should have both paid attention. C1 + C2 has more score than D.
Please explain d
a[i] is the biggest number in S where a[i] ≠ a[divisors of i],
We can loop over S to get the largest possible number, since i <= 1e6, then the max number of different divisors of i is 240, then we can break the loop after at most 240 iterations not 1e18.
number theory forces
Can someone explain E? I see a lot of people posting about OEIS but I have never heard of this before. Can anyone explain?
OEIS — Online Encyclopedia of Integer Sequences basically you put in the first 5-6 terms of a sequence and it gives you the formula or recurrence and literature
However I don't understand people that solve problems that way.
How does checker of B implemented?
With a suffix automaton.
It is also possible with a vanilla suffix array
No offense, but one of the least enjoyable rounds to participate in a while
Nice A, pretty cool B, but here it all ends
??? C1? ????? C2? Guessed (with proving it only after submitting when checking for possible fst) both
Really cool idea for D, but once again guessable-and-i-still-have-no-idea-why-it-works. Combined with exactly same impression from C, barely leaves any enjoyment from solving it.
OEIS'ed problem E. This says all about it.
Problem F is really cool, but seeing "output modulo 998244353" right after OEISing E left me just desperate (even though later still had fun solving it and almost managed to debug it before the round end)
Not saying any problem in particular was bad, uninteresting etc. Any of them would be highly appreciated if it was a single such problem in round, but not when they are four (five, six?) consecutive math problems in the problemset
Nothing is bad with math itself, but when 3 consecutive problems involve divisibility and 2 next problems ask for something mod 998244353 it should probably tell you you should mix the problemset with non-math problems too =)
Anyways, thanks for the round and thanks for GM :)
how do we OEIS this kind of problem. can you please detailed steps ? many people like me would be interested in learning.
Bruteforce for smaller n values. Search the pattern in OEIS.
damn, hence you proved. i am dumb.
prob H is brilliant atleast
I liked H, but I only went for H after skipping everything from E onwards because they looked tedious.
Yeah, i didn't get to H so can't have opinion on it, but it seems like many people expressed their appreciation of problem H,
as well as a bit differing opinions about E-G xd
i need small help.can someone please just add 'LL' after '1' in the reverse for loop in this code. https://mirror.codeforces.com/contest/2039/submission/292987555 . sorry to ask, but i m travelling and i cant submit with phone. and i really want to know if my code works or not.
WA on test 2
thanks bro. i guess upsolve needed then.
dang, I completely missed
in C1, and solved it without this constraint
Can you explain the approach?
if (x^y) is a divisor of y, then y must be <=2*x. why? well because if y>2*x then lg(x)<lg(y), so __lg(x^y) == __lg(y) and then (x^y) can't be a divisor of y as 2*(x^y) > y.
now that we know y can't be that large. Let's do a prime sieve loop up front of size 2M:
so there's O(2M log(2M)) value-divisor pairs total. For each one, we can let x=j, and (x^y)=i, implying y=i^j. (and similary for let y=j)
and here, sort queries by x, then by m, now each value-divisor pair affects a continuous range of queries
292967375
Bruteforce, which helps you find a solution to problem E on oeis
Forgot to mod 998244353 in problem E and got FST :(
sorry, I didn't know about alt account before.
why I am getting downvotes?
because you're using alts in Codeforces
Sorry for the rough feedback but I think this contest could have been better.
Problems C1, C2 and D were about, like, pattern recognition.
I solved each of them as follows:
So the editorial for C2 was very cool, but since the input size is so small (just 2 numbers), you could just try to bypass that thought process, like I did. I think it's counter-productive to have problems where you can just "oooh... just notice that you can there are never answers above
2 * x". Why is that? Nobody knows, but it works, so let's go.Contrast that with, for example, a problem like 2036F - XORificator 3000 where you had to, like, manually do the counting. There was no sneaky way around at least doing some of the work. Also literally any other problem with inputs of at least 1 dimension (at least one array), however, in today's D, I spent 40 mins on unsuccessful thoughts and just found patterns in 10 mins by generating answers for arrays with slight changes, seeing how the answer is affected.
That's not to mention E, it is very sad when you can just do the bruteforce and input the result into OEIS. You could take it as an enforced rule during problemsetting, whenever you have 0-dimensional input (like 1 or 2 numbers), generate answers for small inputs and input them into OEIS. If you find something interesting, chances are many contestants will, too.
Till the next contest, I guess :)
it feels really bad to see number theory after number theory
How can we claim our prizes? Is it enough if we insert the TON wallet code in our profile or should we do something extra? Thank you!
293013531 vs 293013930
>POV: you're trying to squeeze in time limit
Any one has proof for A as to why printing odd numbers works.
as $$$2k-1\equiv k-1 \pmod{k}$$$, the remainder would be $$$k-1$$$ for each $$$k=1,2,...n$$$, and the value of $$$k-1$$$ are all distinct among these values of $$$k$$$.
YouKn0wWho's head is a picture with tourist, but u let him down from T xD
Вздраствуйте. Мой друг нашёл пароль от моего аккаунта и украл код от задачи C1. Я хотел-бы сказать что я не был читером но у меня нет доказательств... Но у меня есть одна зацепка! Посмотрите на мои посылки на задачу C1, и посмотрите что я отправлял их дважды во время контеста, если посмотрите на код то заметите что они одинаковы! Думаете я бы отправил одинаковые коды на одну и туже задачу? Конечно нет! Это был мой друг. Он отправил его случайно, и поэтому я понял что он украл мой код. И можете посмотреть что он отправил на свой аккаунт тоже этот код после одной минуты... Пожалуйста я не был читером!
So prize when
Great problem d
Please take a look at my submission and try to check what is wrong in the code, what test case it might be failing ?! Any help would be highly appreciated, trust me, it would really be!
https://mirror.codeforces.com/contest/2039/submission/293983985
Will the prizes be sent with USDT, which might mean we should change a wallet, or it will be transfered into TON?
Have anybody received ton? I haven't yet.