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, MoonKnight., 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:
2.mhq
3.jiangly
4.Benaive
5.Ormlis
Div2:
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 :>
This round promises to be amazing!
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 solve
Neither problems nor questions, tasks seems good.
I think 6 problems are better than 5 problems!
Because when he puts 6 problems in two hours, he will make it easier than 5 problems in two hours!
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
cf round 728 was almost a week ago. Excited for 729 :)
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
Isn't he supposed to do it by continuously collecting contribution?
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.
i hope question A) and B) will be from binary search :_:
yes, with this time frame I can participate without worrying about missing EURO.
excited
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...
I wanna cross 1300 rating on this round!!
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.
Ya I know. its a fresh start for me though. gave the last one way back. 4 months ago I think!
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
B — 1250...Getting nervous now!
I'll Still give it a try :-)
Reading some funny blog posts before the round.
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.
last time I gave your contest . it was a complete disaster for me. I guess not this time.
Thanx for sharing your experience 10 mins before the contest.Xd
should had taken ur experience as Warning
10 min were enough?
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
Problems and competition has gotten harder significantly in the last 1-2 years. More resources and tutorials available. Smarter people joining. You maintained expert. You are good to go. I wonder when i will reach even a specialist. Need to be more consistent but doing Leetcode lol these days.(which does not help much here)
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
Failed System Test
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 :')
yep :)
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.com/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.
Thank you. I got how main idea is working.
Thought I didn't get it still how it is used in the code. May be I need to think harder.
Thanks a lot, again!
MATHFORCES
I was expecting at least one such comment. You, sir, have not disappointed me.
When you did not had any idea then why copy pasting some random shit from maths notebook.
Destroyed the mood.
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]++;}
make a blog about this. many people don't see comments.
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,33
Link : 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
Thanks, I didn't know about it
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
MOD
variable 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 explanation is nothing but an absolute beauty... Genius. I was trying to understand this very thing and kept looking in the comments but your explanation is just perfect.
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$$$
I was able to get this but was unable to convert this logic to code successfully.
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*j
Proof:- Let at any pointn=a^x+b*y
now1) 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.
thanks, I have checked it initially but I forgot the case where (n-1)%b != 0. Thanks
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 < 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
+ x
count how many subsequences up to indexi
havex
in thek
th 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.
Thanks DpForce for amzing problem
Contest should be renamed as Mathforces Round #...
Great contest! Thank you feecIe6418 gyh20.
Did you like the questions too?
The problems were interesting i liked them :)
I regret giving this contest :)
help me guyss
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-1
and+ x
withx
in an array. We chose one positioncheck
withnum[check]!=-1
which 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 withS
if it is beforecheck
and withG
if it is aftercheck
.Now we start a 2D-dp
dp[pos][S]
. We will check the positions from left to right and thedp
counts for positionpos
how manyS
we still have,S
beingt the amount of numbers smaller thannum[check]
.num[check]
itself also gets added toS
at positioncheck
. If we passed positioncheck
then 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]
overS
and multiply it withnum[check]
. Repeat for all positionscheck
and 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 decreaseS
on-
or keep it equal, if we are atS=0
(see on thefirst-
), increase it onS
and don't change it onG
.If we take
+5
at some point and laterS
gets reduced to0
then we have lost the+5
. Thats why we delete the values in the red fields.In this example
dp[4][2]=2
means, 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+5
yet. 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.
Thanks a lot! It helped.
Yes, it is. Let
C[i][j][k]
be the number of subsequences ofS
up to indexi
such that thej
th value is/would be thek
-th highest element in the multiset. Then the answer is the sum ofS[j] * C[n][j][k]
for allj
andk
.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.
I can also write the other expression but can't think of a general form a^K + Lb = n. instead i go and check if n is divisible by a, if divisible then i reduce n by a times, if not then i reduce n by b until i get the number divisible by a, i'm really stupid , thanks for your explanation
I was also trying to do similar thing but it didn't work for the last sample case given. It was giving WA.Dont I'll have to try the problem again
I was also trying the same, first reducing n by a as long it is divisible, and then solving the above equation, but it gave WA
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 2 min 30 sec and none in 1 hour 57 min and 30 sec
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.
how u thought of lcm i was just blank after factorial not worked
How I got to LCM was by observing that something that is divisible by 4 is automatically divisible by 2, as 2 is a factor of 4. So, when finding out the number for which the answer would be 5, I need it to be divisible by 2, 3, 4 and not 2 * 3 * 4, as that would include an extra 2 which is not needed, this pushed me towards thinking about LCM of (2, 3, 4) which is 12.
thnx bro nice explaination
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 < j)$$$ and add $$$ans_i * (i+1)$$$ to the answer.
Can anyone tell me the problem with my approach for Ques D
dp[i][j] denotes the answer till ith index if we strictly remove 'j' smallest elements
Our answer will be dp[n][0]
The transition goes something like
if ith char is positive -: Considering both the possibilities (taking and ignoring ith element)
dp[i][j] = dp[i-1][j] + dp[i-1][j] + pow(2,i-1-j) * A[i];
if ith char is negative -:
for j >= 0
(leaving and taking ith element)
dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
Link to code https://ideone.com/CgwuKR
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 < n < t_{k+1}$$$. Then we can observe that:
Using these two formulas we can efficiently compute $g(n)$ for any $$$n$$$.
thanks
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 < i$$$. And if a number is multiple of some set of numbers, then it is a multiple of their $$$\text{lcm}$$$.
I still didn't get this approach though I read it many times, can you please explain it a little more.
Thanks a lot!
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
then Why I am getting TLE.
I checked for n=10^9
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>0$$$ otherwise if $$$x=p^{k1}q^{k2}$$$ then we can always find some $$$j<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.
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.
try to f(60) !=5 you will get your bug f(60) = 7 in your code this case handled as 5
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.