Hello Codeforces!
feecIe6418 and I are glad to invite you to Codeforces Round 729 (Div. 2) which will start on Jul/03/2021 16:05 (Moscow time). Note the unusual start time of the round.
The contest will last for two hours, and you will have five tasks to solve. The tasks are prepared by feecIe6418 and me. This round is rated for participants whose rating is not higher than 2099.
We would like to thank:
Aleks5d for coordinating and helping us with the problems.
dorijanlendvaj, waaitg, Imakf, alexX512, Akulyat, talibmohd, Starlight-Sailor, andr0901, nnv-nick, Delmos, kassutta, wxhtzdy, 4qqqq, for testing the problems and providing useful feedback.
amgfrthsp for translating the statement
finally, MikeMirzayanov for great platforms Codeforces and Polygon!
It's the second time we hold our contest, our previous round Codeforces Round 670 (Div. 2).
We tried our best to make the statements short and clear, pretests strong and problems interesting. We hope you like the problems!
Score distribution will be announced shortly before the round.
Score distribution: 500-1250-1500-2000-(2000+1000)
Editorial is published Editorial
Congratulation to the winners:
Div1+Div2:
1.Nilou_
2.244mhq
3.jiangly
4.Benaive
5.Ormlis
Div2:
1.Nilou_
2.Benaive
If you are nerd who is on cf all day, lets be thankful for the resources we have ! Quick question : How ? Ez, just participate and enjoy this great round ! Wish you enjoyable contest :)
Also, as a person involved in testing, I can assure that problems are interesting with statement being kept short and crisp. Make sure you register :)
how to become a tester?
A common question and yet answered a lot of times. There are no rules for this. You should either be friends with setters or have experience of being a setter(the main thing is to be trustworthy).
It's been a long time since (shirt and crisp) in contest. Can't wait for this!!!
Now I really have to say problem B was really harder than A :(
Nice start time for Chinese! Wish I can be purple in this round :).
YOUR PRECIOUS UPVOTE :>
hoping not too difficult.hoping getting high score
I loved this, Thank You!
We tried our best to make the statements short and clear, pretests strong and problems interesting. We hope you like the problems!you will have five tasks to solveNeither problems nor questions, tasks seems good.
Boogaboos were best.
How does one "solve" a task?
You complete or perform a task, and to complete a programming task you need to solve it
I appreciate this.
We tried our best to make the statements short and clear, pretests strong and problems interesting
Hope i am able to solve B.
Chinese Round! But it's sad that I couldn't participate in it because of my courses TAT
tianbu is a genius. stO tianbu Orz
Was waiting for this contest eagerly to come back to expert
same here expect to go back to specialist
UPD: I made it :)
cool
Chinese round means get ready for FSTs.
If you FST feecIe6418 will swallow a battery
does the offer still hold if anyone other than BlueTulpis FST ?
For each of the other FST gyh20 will swallow a battery.
Wasn't that funny or is it my color? :)
Nice problems! Solved A,B,C. Let's see if I get FST .
UPD: ALL PASSED, I saved his life.
Edit:Why downvote me guys?? Did I speak something wrong?
ok so I found an FST
I am not a regular on codeforces. what does FST's mean
Failed system tests
A lot of testers!!!,I am afraid of paper leak.:) kidding never mind
Only $$$13$$$ testers!
Here's a list of 40 testers.
Lamo!
Yet another codeforces contest, Yet another unusual timing contest
As not a tester I'm waiting really good contest with brilliant problems.
Wow, another Chinese round and friendly time for Chinese! I'm looking forward to problems written by feecIe6418!
Note the unusual start time!
2 hours and 5 problems ? My rating is expected to have a negative expectation value.
The best thing is the honesty between the programmers!
RESPECT!
5 problem contest means C will be a good problem to solve.That means people will not get away with speed solving + short statements(My advantage as I am a big fan of AtCoder type problems).Can't wait for this contest to start.
What are AtCoder type problems?
Atcoder Is a platform similar to codeforces with problem statement not exceeding 10 lines
the code does not exceed 10 lines as well
Code driving logic less than template size lol
Nice start time (for UEFA Euro :) )
I love codeforces!
Hope to have a good experience.
At your last round, I became master for the first time. I hope I will become again tomorrow.
Strange 38 Comments Done but Nowhere I can See 1-Gon.
PS: Not Tagging him he might be busy it seems :-)
He is probably busy taking over the CF Empire.
Mono-Gon Empire
Looks like a nice name. Orz
And I thought he was busy setting up the Monogon Forces UI this whole time. Didn't he already take over CF?
I don't think so. Not yet, at least. As he mentioned before, he is working on that. He has to beat a strong opponent like Mike, after all.
Well please explain why he is the top contributor and not Mike. :\
Mike's contribution is +231 and mono-gon's is +210. I guess you know that 231 is greater than 210. Mike didn't add himself to the top contributors page.
Of course I did, I was simply trying to point out precisely that fact. :) Mike should add himself to the contributor list to halt the revolt.
I think he doesn't add himself willingly. If I'm not wrong, he did mention it once, but I couldn't find his comment.
yes, with this time frame I can participate without worrying about missing EURO.
Hope to become expert this round!
I hope I will raise my rating in this contest))))))))
I hope to become a specialist after this round
waaaait a second
careful what you wish for...
My comments getting contribution after having been removed completely baffles me...
Cool, good start time, I think this will be my first contest, I hope I enjoy it as much as all of you.
Is this rated contest?
Yeah! Finally a contest after a long break. :)
We hope the problems be interesting and balanced
starting my cf journey with this contest wish me luck
I think you should know that others can see your colour and contest history.
Copy-pasting Same Comment since 3 contests I guess:-)
PS: This one 4th.
Nice observation bro
I think you should know that others can see his comment history.
Ok,thanks
Note the unusual start time of the round.Well, for the Euro cup, actually :>
Yuhao Guo is a genius prob. setter! orz
Actually, I don't think that's my name QAQ
Oh no it's not, I mistyped QAQ
Looks like I am not the only one who gets distracted and uses o instead of i with that scire distribution.
Scire distribution.
oops
Seems like the authors are too excited about the contest..xD
Now, after reading comments i understand why they were so excited...xD
Does (2000+1000) mean that E2 will be as easy as 1000?
No
What is (2000+1000) difficulty? Not the same as 3000?
There are two subtasks. The first one gives you 2000 points and the second gives another 1000 points.
how to become cm ?
u will never know untill u become cm
Coming back to participate after 5 July'19.
all the best. all i can say is problems have got harder probably.
And saw this shit.
Can't agree more. Was this mathematics exam?
Observation exam
Hope my ratings increase this time.
R.I.P. your rating
Mathforces.
It actually does not feel like a coding competion at all. I mean, the term "coding competion" somehow implies that the problems should be solveable using codings skills.
With todays problems coding skills are not relevant.
Don't be salty, just work on your math skills and you'll do better next time :)
It is more likly I quit.
They are relevant — go take edu rounds. Other problem setters will always be a hit or miss. I know personally, I will never take an Omkar round because I will never succeed in those math-y rounds, and the problems are often severely underrated in my opinion (how was Diluc 1500?)
I think also, for someone with your experience, you should know this already.
Your point that "coding competion somehow implies that the problems should be solveable using codings skills" is nonsense. That's like saying "physics competition somehow implies that problems should be plug and chug formulas". Get over it, physics competitions have been about manipulating algebra >10 years ago.
I agree, math is hard. If you want to quit, go ahead. But complaining about CP in general is your own opinion and projecting it on others is lame.
Why just math? We can hone our physics and chemistry skills and have corresponding rounds here.
Those are empirical sciences, it's not at all the same.
You can solve all of today's A-C without any special knowledge or tricks, you just need to look at some examples and find a pattern.
Problems in the contest are complete shit and very commonplace and ugly.
agree
the greatest contest i have seen.
why downvote me ??? brrrrr. I only said that contest is good :))
When offering an opinion you are always at risk of it turning out to be an unpopular one. :)
anyone else buckling up for a FST on B ?
yep, me. But time limit on test 2 :)))
did you handle a == 1?
yep, both a == 1 && b == 1. even n % b == 1. if you pass through problem B could you give me solution ?
Contest is over, so all the solutions are available for you.
I missed the case a==1...got infinite loop thanx for telling....99% of my solution for B was correct except a==1
PS:Need a handful of water to die away right here.
what's FST
Problems were nice but giving 3 problems purely based on maths is not a good idea. Many people can only solve top 3 problems and if all the top 3 problems are based on maths than how can people enjoy the round?.
Since CP mainly consists of Math, problems like this should be expected. But seeing that I got obliterated by those problems today, I agree. Today's round was Math-heavy.
After this round, I've made it a point to read all the questions before submitting even 1 of them. If I find so many math problems, I'll just leave instead.
I have seen CP contests for Russian school students. This feels like Russian Mathematics Exam for class 8 or whatever.
contestants eagerly waiting for the next cf round.... Chineese question setters!!! Take this maths test
someone plzz kill me i took 7 attempts and more than 1 hr to find out that my first submission's logic was correct on problem B but getting wrong answer due to overflow :(
Well, if it is because you were using int, how about using long long everytime? If you're not doing it because of TL or ML issues then all I can say is, it is much easier to correct these errors rather than getting a WA on pretest 2.
bro, I was using long long only but while storing the powers of a it overflowed. In the loop I was checking for all the powers of a but I should've break the loop when power of a becomes greater than n because then u can't reach n from that power but I kept on checking all power in which due to overflowed value it was giving wrong ans, that was my mistake :(
well, we learn by our mistakes :')
are these the good ideas they were talking about... looolllll
And, problemsetters, please consider that these "tell me the formular" problems are very cheater friendly.
Yet we see so less number of submissions
Those 3000 AC submissions of problem C are hurting me from inside was this problem that easy ?
After seeing Um_nik's solution, yes. But before that, I had no idea how could do that in almost constant time.
I didn't got Um_nik's solution. (Problem C)
I didn't get the code, Ik that we need to iterate over answer and check how many numbers out of n have the answer 2, how many have answer 3, etc.
It would be a great help if you or Um_nik can explain the implementation, I mean how he solved it?
I wrote an explanation of Um_nik's solution here: https://codeforces.me/blog/entry/92410?#comment-811677
I think that my solution is not different from editorial? You can also check this comment.
The main idea is that for any sum (of non-negative integers) $$$\sum_{i=1}^{n} A_{i}$$$ it is equal to $$$\sum_{k=1}^{\infty} F_{k}$$$, where $$$F_{k}$$$ is the number of $$$A_{i} \ge k$$$. You can imagine it as follows: draw rectangles with height $$$A_{i}$$$ on 2D-plane, then $$$\sum_{i=1}^{n} A_{i}$$$ is the total area if you calculate it by columns, but also $$$\sum_{k=1}^{\infty} F_{k}$$$ is the total area if you calculate it by rows.
In this problem it is very easy to calculate $$$F_{k}$$$ and their sum, and that's exactly what my code is doing.
MATHFORCES
Found this research paper from which C appears to have been lifted directly (?). Still can't comprehend, too tough this. Feeling dumb AF
"Coding requires good amount of math"
...and we took that personally! ~ today's contest setters
MEET AN EXPRIENCED & SHAMELESS CHEATER This is how Master_Jiraya bypasses Plagiarism testing.
i reported to codeforces and MikeMirzayanov about him from past 4 contest and he does cheating in it also and got plagiarism , thanks to u for upvote my comment so that he got punished . and today again he cheated in the contest , pls again upvote my comment ......
Master_Jiraya does cheating from starting and i reported about it to MikeMirzayanov and he got plag in last 3 rounds , he abused me in private chat becz i reported him https://ibb.co/JmhSwKL . guys show your support and again upvote my comment so he again got punished.
People like Master_Jiraya are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible . MikeMirzayanov sir pls ban him and skip his solutions .
his todays contest submission 121219128 121218241 , saw his submission timing , he submitted 2 solutions within 2 minutes , tourist your new competition ,lol and also see this dummy variables snippet to bypass the plagarism . ban this Master_Jiraya , i urges the admin of contest to help me to skip his submissions gyh20 feecIe6418
FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}
How come 2900 people solve C??!!
Open OEIS.
Stare the pattern for 30 mins.
Write a formula based on the pattern.
Done.
However this doesn't work on E :(
yeah i saw that ... the formula was n*phi2 , where phi is golden ratio. But using double has some precision issues. Did you use some other formula?
I observed the pattern. Didn't used OEIS more than that. Formula goes like (n/(x-1)*x)*pp, where pp is prime power and x is the only prime factor of prime power. Basically n*1/2 numbers will have f(i) = 2 and n*2/3 numbers will have f(i) = 3 and so on.
That formula is incorrect. I got it after calculating values for 5,6,7...
I did it. But couldn't find any formula to 2,5,7,10,12.. how did OEIS helped?
should be this: 1,2,6,12,60,...
link: https://oeis.org/search?q=6%2C12%2C60%2C420%2C840%2C2520%2C27720&language=english&go=Search
But I couldn't find the pattern on OEIS..
ig, it was
2,5,7,10,12,16,18,21,23,26,28,33Link : https://oeis.org/search?q=2%2C5%2C7%2C10%2C12%2C16%2C18%2C21%2C23%2C26%2C28%2C33&language=english&go=Search
You need to see this
https://oeis.org/search?q=2+3+2+3+2+5+2+3+2+3&sort=&language=english&go=Search
Big F
Still It's not correct. Smallest divisor need not be prime
i just solved this task for some small Ns in my mind and then came up with the formula
can you tell me the formula?
i can give you a code:
goddddddddd.............
I was thinking just like this....but I wasn't able to converge on the step to take gcd of num and i.
let us now consider the number i. then those numbers that are not divisible by all numbers from 1 to i are divided by their lcm. we can calculate how much before this number i was divided by all the numbers from 1 to (i-1). let it be X(n/lcm(1...i-1). We also know how many numbers are divisible by all numbers from 1 to i (n/lcm(1...i)) = Y. then the number of numbers with i = the minimum divisor = Y-X
let $$$F(i) = lcm(1,\cdots ,i)$$$.
The number of numbers in the range $$$[1,N]$$$ with $$$i$$$ being the smallest non-divisor number is equal to $$$\lfloor N/F(i)\rfloor - \lfloor N/F(i+1)\rfloor $$$? Is this what you want to conclude?
no, The number of numbers in the range [1,N] with !!i+1!! being the smallest non-divisor number is equal to ⌊N/F(i)⌋−⌊N/F(i+1)⌋
Oh, yeah my bad it should be $$$i+1$$$.
so did you understand the solution?
Yes, completely. I was doing the same, but the template ruined everything.
There was an extra
MODvariable which was set to $$$998244353$$$ and I could never get correct result for large $$$n$$$ * smiles in pain *.omg bashkort > Java
wtmoo why are you not purple, scam
Gosh I wish there was a USACO tutor that could help me get to purple.
How to solve B? I know it would be some trivial shit >_<
If you don't multiply by a, you can generate 1, 1 + b, 1 + 2*b etc, and all will have remainder 1.
If you multiply once, you can generate, a, (1 + b) * a, (1 + (2*b))*a etc, and all will have remainder a % b.
So you just need to check if there exists a^k = n (mod b) where a^k <= n.
You can show that $$$n$$$ will always be of the form $$$a^x + by$$$ so you just subtract the powers of $$$a$$$ and check if the result is divisible by $$$b$$$.
Be careful with the case where $$$a = 1$$$
suppose we first multiply , then add and then again multiply will that not change the formula?
No, since (x * a) === (x+b)*a (mod b) === x*a + b*a (mod b). Still, you wouldn't like to add first. Only x * a can change reminder (mod b), so check if there one equal to n%b. And beware of corner-cases like a = 1, b = 1, and/or n = 1.
n will always in the form
n=a^i+b*jProof:- Let at any pointn=a^x+b*ynow1) If we multiply a —
n=a*(a^x+b*y)=a^(x+1)+b*a*y = a^i+b*j(let x+1=i and a*y=j)2) If we add b —
n=a^x+b*y+b = a^x+b*(y+1) = a^i+b*j(let y+1=j)Thanks! This proves that every number that belongs to the set can be represented as $$$a^x+by$$$.
But how can we prove that every number that is representable as $$$a^x+by$$$ always belongs to the set? I mean, can't there be a bad pair of $$$x$$$ and $$$y$$$ values, which will result in a wrong "yes" answer?
Edit: Now I see it myself, $$$a^x+by$$$ is just obviously reachable from 1 by first multiplying it $$$x$$$ times by $$$a$$$ and then $$$y$$$ times adding $$$b$$$. So any non-negative integer values $$$x$$$ and $$$y$$$ are good.
"""
I fail to understand why it is giving me a TLE. plz help!. Ignore execution time checking in main(), leaving that too gives TLE.
You have not checked for when a is 1. This means that when a==1 the pow will never update and it will be an endless loop.
Also next time try using spoiler tag to hide your code.
You should put your code in spoiler tags.
MATHSFORCES
I declare problem D unsolvable. This won't change even if I am presented with a solution.
Would you read it?
I would. But as I said, once the declaration has been made, it shall not change.
I came up with an approach which I could not fully execute because I was running low on time, but here's my idea if anyone is willing to try it out.
Instead of trying out every single subset, let's just consider the probability of a number being included in the final result and then add $$$P(i) \cdot Total \cdot val[i]$$$ to the result, where $$$P(i)$$$ is the probability of its presence, $$$Total$$$ is the number of subsets and $$$val[i]$$$ is the value at given place in initial array.
By doing some DP with two states, in $$$O(N^3)$$$ we can determine the probability of $$$k$$$ lower numbers being present in the final multiset, for each $$$0 \leq k \lt N$$$. Could someone let me know if this approach would work?
Maybe in a similar way you could count the number of times the number will appear in the final result, instead of his probability
My idea was: for each
+ xcount how many subsequences up to indexihavexin thekth position. But I ran out of time working out / implementing the DP.Great problems! I really enjoyed this contest. Maybe a bit math-heavy, but I like that.
Problem B Had me :)
Task C was quite similar to Problem 2 of the 3rd level of the Argentinian Regional Mathematical Olympiad 2012
math & dp round:(
$$$10^9+7,998244353,mod,mod$$$
this is a completely math round:(
lol
L.O.L problem D with repeated value is kind of hard to understand, can anyone show me how to deal with this situation? (sorry for my bad en).
You can just assume that operation — removes minimal number with first occurence, so all numbers will be unique.
You can just make everything be distinct values. Instead using $$$A[i]$$$, you can use the ordered pair $$$(A[i],i)$$$. Now everything is distinct.
Great contest! Thank you feecIe6418 gyh20.
Did you like the questions too?
The problems were interesting i liked them :)
I regret giving this contest :)
International Codeforces Maths Olympiad !!!!!
I hope the person who set limits for E stubs his toe.
And ofcourse, code passes with pragmas -_-
as expiation you should stub your toe
What does it actually do? Is it something that one should use in generic template or can it also have bad influence on something?
No clue. I just know it makes code faster sometimes.
Was D a dp problem? I could not figure out the states for like an hour and half :(
I came up with something but was struck at a point if we maintain for every index the minimums possible with their count we can add that to the answer in case of '+' case. But I am struck with the '-' case, we can only track the minimums, but in '-' case we have to expose the second minimum, but I don't have track of that :(
I did Problem D it with dp.
I mark
-with-1and+ xwithxin an array. We chose one positioncheckwithnum[check]!=-1which we are going to check now: what will be the final contribution of only this number to the answer. We replace all other numbers in the array. If the number is less thannum[check]we replace it withS. If the number is more thannum[check]we replace it withG. It it is same asnum[check]we replace it withSif it is beforecheckand withGif it is aftercheck.Now we start a 2D-dp
dp[pos][S]. We will check the positions from left to right and thedpcounts for positionposhow manySwe still have,Sbeingt the amount of numbers smaller thannum[check].num[check]itself also gets added toSat positioncheck. If we passed positioncheckthen allnum[pos>check][0]are set to0, because we lost ournum[check], it can't contribute anymore.In the end we sum all
dp[n][S]overSand multiply it withnum[check]. Repeat for all positionscheckand we got our answer.My submission: 121349216
Thanks for the explanation!
Can you please explain again what exactly does the dp state dp[pos][S] implies? For example, what will dp[4][3] mean?
Also, why did you say that for pos>check, num[pos][0] = 0?
Thanks.
I got an image for you:
You always add following the the arrows. The blue arrows mark not taking the number. It doesn't change
S. There are no blue arrows to $$$+5$$$ because we need to take it. Red arrows decreaseSon-or keep it equal, if we are atS=0(see on thefirst-), increase it onSand don't change it onG.If we take
+5at some point and laterSgets reduced to0then we have lost the+5. Thats why we delete the values in the red fields.In this example
dp[4][2]=2means, at position4(the second-) there are 2 subsequences of $$$[-,S,+5,-]$$$ such that we have 2 Elements in our set and we haven't los our+5yet. Those subsequences are $$$[-,S,+5]$$$ and $$$[S,+5]$$$.Hope this helps!
Thanks a lot man, this makes sense.
For the extra case of num[pos][0] = 0 for pos>check, I think you need not explicitly write that, as the algorithm will take care of it.
How will it take care of it? If I wouldn't do that, e.g.
dp[5][1]would take contribution fromdp[4][0]which it mustn't! I'm going to add an arrow there in an edit.How long did it took you to understand a statement?
What are S and G?
oh got it...smaller or greater?
Yes exactly. I'm going to post a visual example later to explain more in detail.
Thanks a lot!
Can you also share how you got good at dp, as I have read your dp solution to the problem "Armchairs" and it was really good?
And where you practice dp from? Thanks again.
There's no recipe for this. Keep practicing and keep doing maths. :)
Where will you post the visual explanation? In the editorial blog?
I posted it here.
Yes, it is. Let
C[i][j][k]be the number of subsequences ofSup to indexisuch that thejth value is/would be thek-th highest element in the multiset. Then the answer is the sum ofS[j] * C[n][j][k]for alljandk.how to solve problem B ?
a(x + b) = ax + ab
therefore if n is in the set, n = a^k + mb.
for all a^k <= n check if (n - a^k) mod b = 0, if so then return Yes.
i don't understand n = a^k + mb. you can again explain
Every Number will be of the form:
according to allowed operations ((((((1*a^n1 + m1.b)a^n2 + m2.b)a^n3 + m3b)....)
So if u expand it it becomes: a^K + Lb = n.
I figured it out very late I was foolishly trying to solve the expanded polynomial.
A, B & C are solved in less than half an hour and only 3 problems are solved in 2 hours :(
i solved A in 2 minute. and only 1 problem solved in 2 hours.
i solved A in 1 min. nothing in next 2 hrs I was approaching C taking 2 for all odd and 3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 factorial for even can anyone tell what wrong in approach
you have to take lcm instead of factorial.. i was also doing same mistake earlier. consider f(12) ans is 5 for this.
This is not a contest for begineer.
What was that C ? I came up with a lot of stuff but all led to inclusion exclusion which I am very weak at. This round made me love and hate math.
$$$f(i) = x$$$ means that $$$i$$$ is divisble by $$$(x-1)!$$$ and not divisible by $$$x$$$. let $$$ans_i = n/lcm(1, 2, ..., i)$$$, start from end and subtract $$$ans_j$$$ from $$$ans_i$$$ where $$$(i \lt j)$$$ and add $$$ans_i * (i+1)$$$ to the answer.
how to solve C?
If you plot out the first few terms of $$$f(k)$$$, you notice that the sequence is "almost" periodic:
The changes to the pattern are at certain threshold indices $$$t_k = 1, 2, 6, 12, 60, \ldots $$$. These are precisely the values $$$\text{lcm}(1, 2, \ldots, k)$$$ where value $$$k$$$ appears for the first time.
Let $$$r_k = t_k / t_{k-1}$$$ and $$$g(n) = \sum_{k=1}^{n}{f(k)}$$$. Then we can use the pattern we noticed to compute the sums for each threshold:
In other words, the sequence up to $t_{k-1}$ repeats itself $$$r_k$$$ times up to $$$t_k$$$, except $$$f(t_k)$$$ is different.
Suppose $$$t_k \lt n \lt t_{k+1}$$$. Then we can observe that:
Using these two formulas we can efficiently compute $g(n)$ for any $$$n$$$.
Ok, how do people solve it in 3 (or even 10) minutes though?
If I knew that, I'd have a higher rating. :) It took me about 30 minutes with the above approach. I can see that Um_nik found a brilliant solution which is way simpler to implement.
Suppose $$$f(n) = i$$$. Then we know that $$$n$$$ is a multiple of $$$t_k = \text{lcm}(1, ..., k)$$$ for all $$$0 \le k \lt i$$$ (letting $$$t_0 = 1$$$). In fact, we can express $$$f(n)$$$ as the count of these divisors $$$t_k$$$:
So to compute $g(n)$, we can just count up the multiples of $$$t_0, t_1, t_2, \ldots$$$ up to $$$n$$$. This can be expressed as:
I didn't get this line Then we know that n is a multiple of tk=lcm(1,...,k) for all k<i. Can you elaborate the process please.
If $$$n$$$ is a multiple of all of $$$1, \ldots, i$$$ then it is a multiple of $$$1, \ldots, k$$$ for all $$$k \lt i$$$. And if a number is multiple of some set of numbers, then it is a multiple of their $$$\text{lcm}$$$.
I love how they used A to lure participants XD
How to solve C ? I found this on OEIS but not able to solve it. Thanks.
let us now consider the number i. then those numbers that are not divisible by all numbers from 1 to i are divided by their lcm. we can calculate how much before this number i was divided by all the numbers from 1 to (i-1). let it be X(n/lcm(1...i-1). We also know how many numbers are divisible by all numbers from 1 to i (n/lcm(1...i)) = Y. then the number of numbers with i = the minimum divisor = Y-X
I don't know why I am getting TLE in question B.
...
Because n might be a + 10000000*b for example.
The only line describing each test case contains three integers n, a, b (1≤n,a,b≤10^9) separated by a single space.
Shit,I thought n<=10^9.
you thought correctly
n is less than 10^9, and the n I showed is not necessarily bigger than 10^9 (what if a={prime around 10^8} and b=1?).
I get it.The loop will run many times.
Its called time complexity. Amazing concept.
CountingForces
problems were more like trashes ! it took away all the fun during contest ! what's the point to arrange a online contest based on these trashes ?
Care to elaborate?
First 15 mins submissions account to 55% of total submissions. Difficulty transition from B to C was high enough.
Out of curiosity: why do most people dislike mathforces?
Because it's hit or miss for many people.
For example,
1. In B, I failed to observe that a^n(a^m(1+k*b)+l*b) is actually in the form a^p + q*b.
2. In C, I failed to observe that multiples of lcm(1..x) can give result for x+1.
Any tips regarding how to not miss these observations?
Btw I think that most greedy observations are more "hit and miss" than mathforces.
Regarding 2, I thought along that line but couldn't come to the conclusion that lcm could be used. I was actually thinking with inclusion-exclusion principle for some reason. :(
Yeah, greedy observations (especially game theory based) are the most difficult for me at least.
for C I don't think such observation is needed. I just observed that product of $$$1^{st}\,\,14$$$ primes is greater than $$$10^{16}$$$. So I wrote a brute force solution with time complexity $$$O(14*log(10^{16}))$$$. One more trivial observation will be if $$$f(i)=x$$$ then $$$x=p^k,\,k \gt 0$$$ otherwise if $$$x=p^{k1}q^{k2}$$$ then we can always find some $$$j \lt k1$$$ or $$$k2$$$ such that $$$p^j$$$ or $$$q^j$$$ does not divide $$$i$$$. . Now you have to just implement it. You can see my submission if you want it should be understandable.
Thanks for this approach.
PROBLEM C i couldn't get the modulo correct, help guys, for 10000000000000000, i am getting 807500006, while the answer is 366580019. ll x = n/6; ll ans = 0; if(x > 0) ans = (ans + ((x%MOD * 12%MOD)%MOD))%MOD; if(x > 0) { if(x%2) { ans = (ans + (((x/2)+1) * 4)); ans = (ans + (x/2) * 5); } else { ans = (ans + ((x/2)*4)); ans = (ans + ((x/2)*5)); } } if(n%6 == 1) ans = (ans%MOD + 2)%MOD; else if(n%6 == 2) ans = (ans%MOD + 5)%MOD; else if(n%6 == 3) ans = (ans%MOD + 7)%MOD; else if(n%6 == 4) ans = (ans%MOD + 10)%MOD; else if(n%6 == 5) ans = (ans%MOD + 12)%MOD; cout << (ans%MOD)%MOD << "\n";The logic is wrong. For example, $$$f(12) = 5$$$, not $$$4$$$.
but it is 5, i've just added 4 and 5 there,
my approach was, 2 3 2 3 2 4 2 3 2 3 2 5 .......same continues.. is it correct??
will there be any other number than 4 and 5? im not sure
yes there can be many numbers.
solution seems buggy, try for following cases of n i.e. n = 12 n = 30 n = 27
33, 82 and 73 respectively, is it correct??
You can write brute force approach and validate the answers for first 1000 numbers.
The first half of the contest certainly required some mathematical maturity, but solving C was quite rewarding. I liked all the problems individually, but found it a strange choice to put B + C on the same contest and D + E on the same contest. Thank you for writing!
I thought that actual programming is done on CODEforces, seems like I am mistaken. My bad.
Why does my code TLE? I tried to cover all the corner cases...
You forgot about
cin.tie(NULL); ios_base::sync_with_stdio(false);/sit is in my main function. Here I have put only the solve part, testcase handling and fast (er) IO is in main function
oh, then try pragmas. But without sarcasm, it TLEs because of
Imagine if n is large and b is small, it will decrees it so many times.
If n = 10^9, a = some_prime>1/2*10^9, b = 1 and t = 10^5 you'll have around 0.5*10^14 operations. Which is equivalent to TLE in 3 secs.
Please Correct me if I am Wrong -:
Approach -:
f(odd number) = 2; f(even number except multiple of 6) = 3; f(odd multiple of 6) = 4; f(even multiple of 6) = 5;
Now just check how many EVENs, ODDs, ODD Multiples of 6 & EVEN Multiple of 6 are there in n & simply add f() of all of them.
I was getting right answers for first five test cases, couldn't get through the modulo one T-T
f(60)?
In fact, I was stuck with the same problem, but sequence actually looks like this https://oeis.org/A007978 As you can see it's also containing seven somewhere. There is different solution, I guess.
2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19. From these numbers, 1 number will be there. Cheers :)
In other words, f(x) is always between [2, 19]
I found that observation quickly. But how does it help to find the solution?
its a nice observation, but it doesn't help. there is much more to it.
121235927
Nope. $$$2*2*2*2*3*3*5*5*7*11*13*17*19=1163962800$$$ which is divisible by all the numbers in $$$[2,19]$$$
ProblemSolvingForces. Please, we need problems where you need to write segment tree and get ac, because calculating lcm and calculating answer modulo 998244353 is too hard and you can't solve problems like that if you didn't spend 20 years learning math.
Pretty sure there are people who upvoted you because they sincerely believed what you said not realizing the sarcasm
Thank Writers and RIP for my rating.
In problem E (both E1 and E2), why were there almost no cases in which $$$mod$$$ is small? There should have been some cases that have $$$mod=10$$$, for example.
Honestly, I have never seen a solution that fails neither big modulos, nor mod=1 but fails anything in-between.
Imagine getting 3.935sec/4.000sec on the pre-test, and having to look at "Running Test 63", "Running Test 64", ... one by one after that. MY HEART, oh my god.
Can you explain your approach for this?
could anyone please help me in figuring out the mistakes that I have done in building the logic of problem C, it would be a great help if anyone helps me through this. Thanks in advance! Here is my code (https://pastebin.ubuntu.com/p/vXc24T32Sh/)
there is nothing special in 6, why you checking only it?
I'm sorry, but this is not the kind of contest many people like..
your downvotes deny that.
Stop saying that the problems weren't good.Problems were really good.You are reluctant solve div-2 A B C level math problems.Come on bro!!!.Without skills in maths, you won't go a long way.in cp
Tbh, this has nothing to do with how good your math level is. It's all based on: do you see it. I figured out how to do ab and c, but only because I was lucky I saw it, not because I have math skills.
bro it's combination of cp and math skills.Practice in cp enables you to 'see' it.For example, in B n was in some form a^x+by...and your math skills enable you to check it.You shouldn't blame the problem setters for making this sort of problem
I agree that math is indeed needed, but you can't say this is a programming contest. It felt like a math olympiad. Tell me, where are the problems where you needed data structures, algorithms, ..
Codeforces certainly doesn't give math problems only in every contest.One or two contests like this is ok.And if it felt like math olympiad to you, then what would you call atcoder? Mathcoder??
The last 4 contests I did contained a lot of math problems. I would be better if there were 1 math problem in this contest in the next 5 contests, instead of just putting them together.
You also said something about atcoder, but I've never done a contest there.
And if there are people who like these kind of contests, which I have totally no problem with, but please do it somewhere else or announce it beforehand. When people want to do a contest at Codeforces, they most likely want a contest where there will be graphs, dp,.. and most importantly: multiple solutions. Don't tell me there are many approaches for problems like these..
AtCoder is a nice platform and their beginner contests are good for beginners. Exactly because they are easier than codeforces Div.2 and you will be almost guaranteed to solve multiple problems during a contest. Here's an announcement of their tomorrow's contest: https://codeforces.me/blog/entry/92484
The biggest downside of this contest was that places between 4685 and 14370 had been decided by just speed-solving a single problem A (even before cheaters removal). And this alone is very weird. The problem setters may have miscalculated something, unless the plan was to unleash their good problems on good-for-nothing audience.
You did well in this contest. Congrats! But there's no need mocking the others. Hopefully the others learned from their mistakes and will show better results next time.
Thanks,for an amazing round!!
Finally back to blue
It felt like I didn't deserve to post messages for the last week and now I can post again
To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Hi ! Why for example someone who had more rating than me and had the same rank got positive delta but i got negative delta for rating change? Thanks :)
Why downvotes ? you can see what am i saying in the standings and rating changes :|
For new users the rating shown is not the true rating, see https://codeforces.me/blog/entry/77890.
Were the cheaters removed? Looks like rating was not recalculated
Although the problems A, B, C were straight up math, in the end I reached purple for the first time, so tianbu orz, gyh20 orz
No one cares
Curious as to why only a single sample was given in E. This is probably just me whining, but it could've been helpful for debugging such a bug prone problem where I can't figure out if it's a mod issue or not. I know a brute for small n takes < 5 mins to write. But those spare minutes often make the difference.
Felt like i was giving a Maths Contest, rather than a Programming contest.
Problem C explanation
I hope they post the editorial soon. Early editorials are good because you still have interest in the problems immediately after the contest and that's usually not the case with late editorials
too mathy. Bad contest/coordination.
In problem B, I used two approaches. One with a for loop and one with a while loop. The while loop solution got a TLE whereas the for loop one got accepted. Why might this be happening?
Solution 1 (while loop) : 121246493 Solution 2 (for loop) : 121249628
I think the variable c overflows, causing an infinite loop. For the first submission, c is an integer and for the second one, it is a long long.
Somehow your solution 1 the variable c is integer whereas solution 2 the variable c is long long. So multiplication overflow could be occurred on solution 1.
Sorry if you find the round unbalanced, we will try to make it better next time(hopefully if there will be a next time).
But here's something I want to say
I personally am not a fan of math problems(in fact I like data structures and graph theory and greedy MUCH better), and I dislike math just like many of you do.
But I wouldn't say that the problems are bad simply because they are mathy, and problem E is counting which is not particularly math, you don't need to study MO for any of these problems.
Math is a type of competitive programming, which is important for any of us to learn. You can't just judge a problem by it's type, feecIe6418 really spent his efforts when preparing the problems, you can see that every problem involves something different and something new. You don't need high leveled math, just simple math learned in middle school.
I dislike math, no matter in the past or now. Before, I considered mathy rounds as bad rounds, but I gradually understood that I didn't find the problems interesting because I didn't put myself into it. You can find something new in different problems. It doesn't matter whether it's math or not, but its quality does matter. It would have been really easier if I just simply copy a data structure problem and add some queries or change a little, or I can just join two well-known idea and make a new problem,or simply copy some problems from MO and make a constructive problem, these things are much easier than creating a "math" problem .
Don't say a problem is all about math if you find $$$mod$$$ numbers in it. Problems on counting usually focus on finding a suitable DP state or find another way to cauculate, And the problems aren't necessarily needed to be solved with polynomial technology.
We discussed the problems over and over to avoid using some well-known solutions or problems too standard. Though I don't like math and I'm not good at math, but I wouldn't call a problem "trash" if it is simply because it is a problem about math.
btw, you might have to wait for the editorial. I currently can't get in contact with feecIe6418 now , maybe he has gone to bed(same as last time). I'll make sure it is published as fast as possible.
you can use this https://codeforces.me/blog/entry/76100 to publish the editorial.
loved the round, waiting for the next one lol
For me a math problem is similar to "have to solve the problem by working on formulars". Else it is not a math problem.
In this context B,C,D where such problems. (E I dont know, but E does not matter anyway, like no div2 solved it)
My usual strategy is to recognize a math contest before submitting A, and if do so, do not submit at all. In this sense my todays error was to not check problems enough before participating. But actually it feels like I've been betrayed.
D is dp...
Although I usually lose rating in a mathy round, I don't personally dislike mathy round. I dislike myself for being not mathy enough xD. Anyway,thank you for the challenging problems. I learnt a lot from this round.
Video Explanation for Problem A and B :
Problem A: https://www.youtube.com/watch?v=tWEbqar5tCA
Problem B: https://www.youtube.com/watch?v=zun-Wbr4rWk
Thank you very much!
Can any body tell what is wrong with this solution for problem b 121252891?
In case a = 1, the answer is "Yes" if (n — 1) % b = 0, not if n % (a + b) = 0. Example: n = 5, a = 1, b = 2.
For C, you don't need to use the inclusion-exclusion principle in a complicated way because the sequences of multiples of lcm(1, 2, ..., i) are subsequences of one another. You can just update by the difference of the 'lowest non-divisors'. For example there are floor(n/2) terms with f(i)>=3, floor(n/6) terms with f(i)>=4, floor(n/12) terms with f(i)>=5, floor(n/60) terms with f(i) >= 7... So to count them all: 3*floor(n/2) + (4-3)*floor(n/6) + (5-4)*floor(n/12) + (7-5)*floor(n/60) ... (here if (newQ-q)*floor(n/div), start with q=3, div=2 then div = lcm(div, q)(=q*div/gcd(q, div)); q += 1 (keep incrementing if q divides div). That's for the even terms, the odd ones are just 2.
Hopefully this makes sense.
you said f(i) =3,then f(i) =4 then f(i) = 5 then why not f(i) = 6 . How to know which f(i) will contribute to the answer . How you know that 6 will not come and many numbers like 6 which will not contribute to the answer . I know that that are some few numbers(including primes) . But cant really figure out which numbers are contributing to the answer ?? Can you please Teach me ?/ i am new to this all maths problems ...
If x has more than one prime factor, say 6=2*3, then it wont contribute. If you say that f[i] = 6, it means that i is divisible by 2 and 3(along with 4 and 5), but not by 6. Ofcourse, this isn't possible. Hence, only powers of primes will contribute.
that make sense .Thank You
can someone tell me why in codeforces round 729 question B giving wrong answer if i write if"(n%b==1)" it gives wrong submission but for "if((n-1)%b==0)" it gives correct submission. question link-https://codeforces.me/contest/1542/problem/B
(n % b == 1) doesn't work if b = 1
Unfortunately, I only finished implementing E2 after the contest :(. Oh well, here's my solution:
Consider two different permutations $$$p, q$$$ of length $$$n$$$, and say that they match on the first $$$n - i$$$ numbers for some $$$i\in [0, n - 1]$$$, and differ on the $$$n - i + 1$$$th number. WLOG $$$p$$$ is lexographically smaller than $$$q$$$. Let $$$S$$$ consist of the set of numbers in the last $$$i$$$ numbers of $$$p, q$$$, which clearly are identical. Then the difference in the number of inversions in $$$p, q$$$ only depends on the difference of the number of inversions in the last $$$i$$$ numbers of $$$p, q$$$. Say that the $$$n - i + 1$$$th number of $$$p, q$$$ are $$$j$$$th and $$$k$$$th largest elements of $$$S$$$ respectively, where we must have $$$j \lt k$$$. Let the last $$$i - 1$$$ elements of $$$p$$$ have $$$ij$$$ inversions and the last $$$i - 1$$$ elements of $$$q$$$ have $$$ik$$$ inversions. Then the difference in the number of inversions of $$$p$$$ and $$$q$$$ is simply $$$(j + ij) - (k + ik)$$$, and we simply need that $$$ij - ik \geq k - j + 1$$$.
Thus if we do casework on $$$i, j, k$$$, we simply need to find $$$f[i - 1][k - j + 1]$$$, the number of pairs of permutations such that they have length $$$i - 1$$$ and inversion counts differing by at least $$$k - j + 1$$$. We can iteratively build each array $$$f[i]$$$ from $$$f[i - 1]$$$ by doing casework on the newly added element in the permutations along with some simple math calculations and prefix sums. Then this overall works in $$$\mathcal O(N^3)$$$ since there are $$$\mathcal O(N^2)$$$ inversions. Note that I shift my indexing by a value $$$I$$$ so that negative indices are handled more easily.
My submission is linked here for more details. I used the
solvefunction to calculate the number of permutations of length $$$n$$$ with exactly $$$k$$$ inversions, but it is only used for $$$n = 3$$$ as a base case, so it's not needed.When will you put the editorial link ?
I have a solution for C without LCM, but I don't know why it gets WA on n = 1e16. I tested it with every n < 100 and it works. Can you find a mistake here?
Solution: find all the smallest numbers whos divides by the sequence of first numbers (will call them super numbers):
Then, we start choosing numbers step by step starting from the max to min. We divide n by our super number, subtract with the amount of this operation on the previous step, and then multiply this number with the first non-divide number.
All code here: https://codeforces.me/contest/1542/submission/121259996
I had been debugging this code for the last hour of the contest, but haven't found any error.
I have also used the almost same concept. But for me super number were (2 6 12 60 420 840 2520 ..). I am multiplying only those number which can't be formed by available combination of number
https://codeforces.me/contest/1542/submission/121260138
Edit — your sol give wrong o/p for 420
OMG, I thought 60 doesn't divide by 6, such a stupid mistake, thanks. Exactly the same solution as yours, but seed some bugs)
This code for problem D in Java gets a TLE verdict.
java
While this direct translation to C++ gets AC with time to spare.
cpp
Does anyone know a way to optimize the Java code? or should I just take this as yet another sign to switch to C++?
Make the switch! You'll thank yourself later.
Sure C++ is generally faster, but you can get Java to work in almost all scenarios. In your case, one major optimization you could do to get Java to AC is to modify your sum(int a, int b) operation. Instead of using the % operation, just check if a+b exceeds MOD, subtract MOD from it. Of course, this assumes a, b < MOD in the first place.
My submission runs in about half of the time limit by doing this: 121250179
Thanks, that did help. I also remember a few other problems where this trick would have helped too.
Before editorial comes out, you can find solutions here: https://www.youtube.com/watch?v=QbRMPoFpDmg&ab_channel=ColinGalen
Will there be Chinese editorials？
I think you can check luogu, some Chinese people will publish Chinese editorials on luogu.
I mean, offical Chinese editorials.
In general, there won't be Chinese editorials.
I think luogu is probably the largest Chinese editorial. There are thousands of Chinese people discussing algorithms in luogu.
Are you advertising luogu?
haha，meybe :)
Nice start time for Chinese! But prblem C is really harder than B.
I don't think so. I came up with the solution of C in 5 minutes, but more than 15 minutes for B.
Still, I haven't been able to come up with a solution to question C :(
I even think D is easier than C. Should have solved D if I didn't spend 1 hour on C :)
Could anyone tell me the solution of Problem D? I'll appreciate it if you can give me some hints.
For each number, count in how many sub-sequences it will be counted into the answer.
Oh, I know how to solve it. Thanks.
You can read my editorial in Chinese here.
Auto comment: topic has been updated by gyh20 (previous revision, new revision, compare).
Problem A Why this code showing me WA? https://codeforces.me/contest/1542/submission/121273828
Consider the testcase
14 7 10
Your code will print "YES" but the answer is "NO"
Bye bye Expert :(
mathforces :(
The difficulty gap between A and B and the one between C and D are quite large :(
Guys, what were the difficulty levels of the problems B and C in your opinions?
Based on difficulty I'd say 1300/1800
But given that quite a lot of people solved C, I assume it will be 1300/1600
in the C Tutorial : "Since f(n)= i means lcm(1,2,...,i−1) ≤n " why? I don't understand this, can you explain it to me?
If $$$f(n)=i$$$, then $$$n$$$ is divisible by $$$1,2,\dots i-1$$$, so $$$n$$$ must be a multiple of $$$lcm(1,2,\dots i-1)$$$, so $$$lcm(1,2,\dots i-1)\leq n$$$.
Anyone can help explain why ans for Div2 E2 with n=5 is 904 rather than 819?
It seems that I somehow misunderstood the description, but idk how...
A simple py program that outputs 819 for n=5:
Update: nvm, i thought the 'lexicographically smaller' do not include cases when p1=q1, because I didn't see these cases in the example with n=4.