Hello, Codeforces!
On 26.11.2021 14:15 (Московское время) Codeforces Round 757 (Div. 2) will start. This round will be rated for participants with a rating less than $$$2100$$$.
All the problems were authored and prepared by vaaven and me.
You will be given $$$5$$$ problems, one of which has two subtasks. You will have 2 hours to solve them.
We would like to thank everyone helped a lot with round preparation:
- First of all, errorgorn and phyzzmat for help with translating the terms into English.
- Aleks5d and KAN for excellent coordination.
- Ormlis, kostia244, errorgorn, Ziware, Makcum888, wxhtzdy, fishy15, Sprdalo, Riladavin, Ekler, FairyWinx, olya.masaeva, LetterC67, vasilykuzmin22, TheEvilBird, kartikeyasri23, Kolychestiy, QuangBuiCPP, kuertov and WinCrash91 for testing and useful feedback.
- MikeMirzayanov for great Codeforces and Polygon platforms.
Score distribution: $$$500$$$ — $$$750$$$ — $$$1500$$$ — $$$(1500 + 1000)$$$ — $$$2750$$$.
Good luck everyone!
UPD: Editorial
Автокомментарий: текст был обновлен пользователем 4qqqq (предыдущая версия, новая версия, сравнить).
I hope that you will enjoy the short and concise statements. Also I hope that the hack I found will make people FST less (yes, it is in pretests
)
I think you should change your mind about concise statements. Statements wrote very bad and statements are only stories that waste our time.
Well, you and phyzzmat's translations are very bad, and I'm angry at it.
So many people test this contest, but why don't any of them find these obvious mistakes? I think you should reflect on yourselves.
UPD
After the talk with errorgorn, I realize that it isn't his fault.
I am very sorry to make this trouble. The mistake of problem E is maybe the problem setter's fault.
Agree.
I wasted a long time on the wrong statement of E,I've even written the code.I'm angry now.
Welcome to the club
I think that problemsetter should tell competitors about statement-update quickly.
I edited the statements for problems A,D,E only (and a removed problem). Problem B was added very late into testing so I did not look at it. I wrote problem E with only using $$$T$$$, I am not sure why it is changed as well. (I believe it was added quite late into testing as well so please do not blame the rest of the testers.)
I tried to do my best as a tester but I did not want to interfere too much with the content of the problems. I personally felt that I was pushing it when I removed some backstories in the statements (you will notice the english statement for A is much shorter than the russian statement).
I don't really have anything to defend myself but I did not know the statements were changed from what I edited it to until today.
I can understand your frustration but there is only so much a tester can do...
If there are any comments that are actually about translation and making the statements easy to read, I would be happy to read them. The problems you listed have nothing to do with translation. Do you really think they are the translators fault? They also appear in the russian version of the statements you know.
That's not phyzzmat's or errorgorn's mistake, because they made translation before some edits in english texts.
So, sorry for such terrible statements :(
Someone please give hint for Problem D1
use dp
also , $$$\sum_{i=1}^n(\lfloor\frac{n}{i}\rfloor)$$$ is about $$$n \ln n$$$
error
I don't know, when will the editorial release so, I am commenting here.
In problem B I have just used
to sort the array and I got TLE.
Even if I remove
else a.second < b.second;, still I am getting TLE.I used this
sort(all(a), greater<pair<ll,ll>>());after the contest, the solution got accepted.Solution1
Solution2
If possible, kindly resolve this issue, as according to me this should be a problem.
Eh, I am only a translator... I guess i can help fix your code
The issue is with the code below,
you have missed out the return statement in the
elseI think changing it to the edited code below should workYou missed a return in the compare function in solution 1.
This is my first time testing the round and I hope my feedback helped to balance it! I encourage you to read all of the problems — as they are very interesting.
A great time for Chinese people. Hope everyone can gain rating.
Why downvote this? The comment is pretty wholesome.
Note the unusual timing
D1>D2? That's weird. I hope everyone can solve them.
I think that easy version points $$$>$$$ hard version points is usual, for example Codeforces Raif Round 1 (Div. 1 + Div. 2) and Codeforces Round 750 (Div. 2).
but why is easy version points are greater than hard version points?
I think that if you solved hard version, you almost can solve easy version.
Hope that problems will be interesting
I always see, when the contest is held in unusual time, there are relatively less people who participate in the contest. And that is why we get less rating changes as compared to a usual time contest (because rating change also depends on no. of participants).
Ok so you participate in contests just to get some ratings?
This mentality of just gaining ratings and not enjoying CP as a sport has led to so many cheating cases these days!
haha...go and check my profile...still stuck on specialist after giving around 70 contests. If I were a cheater I'd have been orange or red till date after giving around 70 contests. Moreover I have 192 days problem solving streak(and counting) till date. If I were a cheater, why would I have been practicing CP this much. These things are enough for anyone to understand that I don't cheat.
Reward is something people wants when they works for it. People first need expectation to gain something in life provided that they are working fair. Yes I give contest for rating, but that is not greed. Because your school teacher has not taught you the meaning of greed. Greed is something that we want without working, and expectation is something that we want when we work hard for it. That is called 'achieving', not 'cheating'. I hope god made you smart enough to understand this.
op(2)
Looks like you have cheater mentality of just giving contest for Greed(ratings). Stop it or you will be banned..
who are you, the thought police? no one's getting banned for their mentality
haha...go and check my profile...still stuck on specialist after giving around 70 contests. If I were a cheater I'd have been orange or red till date after giving around 70 contests. Moreover I have 192 days problem solving streak(and counting) till date. If I were a cheater, why would I have been practicing CP this much. These things are enough for anyone to understand that I don't cheat.
Reward is something people wants when they works for it. People first need expectation to gain something in life provided that they are working fair. Yes I give contest for rating, but that is not greed. Because your school teacher has not taught you the meaning of greed. Greed is something that we want without working, and expectation is something that we want when we work hard for it. That is called 'achieving', not 'cheating'. I hope god made you smart enough to understand this.
respect++
First time being a tester, so excited (^.^). Although the start time is unusual again, hope you guys could spend time participating the well-prepared round with interesting problems >~<
your graph is really motivating :)
Thanks! I have focused on CP since last year in order to have an opportunity to participate in the national OI in my country. If I could proceed to the national round, my next target is reaching yellow color on CF ;)
I hope you do!, all the best
solo ?
look at my graph and be demotivated again lol
Hope that my streak of underperformance ends here
I hope to solve four problems in this round. Looking forward to it :).
maybe 5?
But that's after I solve 4 :).
As a tester I'm a tester
zamn
никита лазарев добавил меня в черный список в мессенджере TELEGRAM.
Context
Hopeforces
fingers crossed for some non negative delta
Are Ratings going to update before the round starts ?? Any Idea ??
How Can we participate in a contest without rating update from the previous contest
Can we participate in a contest without rating update from the previous contest?
Thxx for the unusual timing. Its better for us (russians)
hey I have confusion as previous contest rating is not updated yet so this contest rating will be calculated with change in rating or rating before previous contest ? please someone clearify
The contest was delayed by 10 minutes!
Maybe in the meantime, the rating will be changed
done
The contest was delayed by 10 minutes。But why？
Why delay??
Sorry, I postponed the round. I would like to have time to update the rating based on the results of yesterday's Div3. I'm in a hurry!
Good decision to increase 10 minutes , i didn't drink coffee
Why it's start time is 19:15(in China)?
It's usually 22:45(in China).
Congratulations to 4qqqq to get 107 ratings. XD
Good luck to everyone
Is it div.3?
No its Div93849329 you're too noob
Is it some IGM alt ?
Maybe LGM.
list, coding style seems very close
ow that's rude
It is div.trash
It is div.114514
Another mathforces round :(
Retired_MiFaFaOvO participating .. after a long time
The amount of ad hoc contained in problem C frightened me.
pretest 2 of problem c has cost me my mouse and sanity
How do you solve it? Pretest 2 killed me
In my case I missed the input like:
11 11 1 1073741823it took my last 40 minutes during the contest...
How to solve D2? How to optimise from O(Max(ai)*log(max(ai)))?
The problems themselves are good, but the contest is unbalanced. There are so many math problems. Problems A and B are too easy, and problems D E are too hard. If you have some problems with problem C, like me, wasting too much time for mistaking "OR" by "XOR", you will be finished.
I saw it after seeing your comment I thought it's xor of subsegment.. I'm doomed
Same thing happened to me also :(.
Hint for C I wasted my 30 minutes in thinking this logic. Could have googled it early and got a decent rank!
Same
Two Friends Of Mine Tried Solving It Using Lazy Propagation xD, only one got ACC
I was able to figure this out — but what was the logic for finding the frequency/number of each bit present in the array? e.g. in array [1, 2] — 0th bit freq is 1, and 1st bit freq is 1. How do I get that info from the subsegments?
if an element is covered by more than 1 subsegments, then its largest possible value is the bitwise AND of all values corresponding to the subsegments that are covering it.
For example, if we have
n=3and subsegments1 2 7,2 3 14, then the largest possible value ofa_2is7 & 14 = 6. Moreover, a possible value must only have the bits occur in the binary representation of the largest possible value. But we can safely just use the largest possible value here.I used a segment tree (range update + point query) to process this information, and I wonder whether there exists a simpler approach.
What i did was, took OR of all the OR's given (irrespective of l,r) and just multiplied it with pow(2,n-1). This passed pretests as well as sys tests.
It's like we don't need to reconstruct a valid sequence, am I right?
Could you briefly explain the intuition (or proof) behind this? Thanks
Yeah, we don't need to construct a valid sequence.Try this link here for a formal proof
If X is the bitwise OR of a segment, then for each set bit of X, there exists an element with that bit set. Then consider all subsequences excluding that element (2^(n-1) of them): they either XOR to 1 or 0 times 2^(bit). If they XOR to 1, then subsequence with our set bit XORS to 0; if they XOR to 0, then subsequence with our set bit XORs to 1. Either way, we are guaranteed a contribution of exactly 2^(bit) times 2^(n-1) from that bit, i.e. its contribution to x. So we just need to know if a given bit is set anywhere in the whole sequence, and if so we add that contribution. Otherwise, the bit is skipped.
i am such a stupid that i started figuring out a valid sequence and I figured out how to find a valid sequence.But when i used combinatorics to find the number of subsequences i realized that we just need to know whether there is a particular bit on in any of the element in the array which can easily be figured out by just looking OR of all elements.
2^(num of on jth bit-1)*2^(n — (num of on jth bit)) you can see that num of on jth bit cancels out but you can see num of on jth bit — 1>=0 num of on jth bit >=1
Why does this work? I got that OR of all the ORs given will be the OR of the original array. But why does it become sum of XOR of all subsets after multiplication with pow(2,n-1) ?
In binary, look at digit r (aka the bit corresponding to the place 2^r) of all numbers in the original array. Say a of them are 1s and b of them are 0s. From the set of a numbers, choose i to be in some arbitrary subsequence, and from the set of b numbers, choose j. Note that making such a choice corresponds to forming exactly one subsequence (for now, dealing with digit r only). Clearly, the bitwise XOR will yield a 1 for digit r iff i is odd. If a>0, this corresponds to aC1 + aC3 + aC5 + ... = 2^(a-1) ways of choosing a set of i numbers from the original a, where i is odd, and simply 2^b ways of choosing any j numbers from the b with 0s at digit r. Hence, when a>0, the total contribution from all subsequences to coziness by digit r is 2^(a+b-1) * 2^r = 2^(n-1) * 2^r, as a+b=n. When a=0, however, the contribution to coziness is 0. The coziness can thus be written as 2^(n-1) * sum(2^r, where a>=1 at position r). Observe that this sum is the bitwise OR of the n numbers, and we're done.
Thanks a lot. This seems fine. Although I found this another explanation by going through the comments-
If at a given place, if at least one of the numbers has its bit = 1 :
1) lets remove any number from the array whose bit is 1 at that place.
2) now, rest of the numbers(n-1) will make pow(2,n-1) sets, now all the sets with xor of bits = 1 will contribute to the solution (addition of XORs)
3) but if xor of the bits in a set is 0, the it will become 1 when the excluded number with set bit is added to all the sets, and then it will contribute to the solution.
4) So if at least one of the numbers has its bit 1 at a place, it ensures that this place will contribute place_value*pow(2,n-1) to the solution (sum of XORs)
5) Now to ensure if at least one number has its bit 1 at place, we can find OR of all the numbers and check if the it is 1 at that place.
6) OR of all the given ORs will be the OR of the array.
I wasted a lot of time in solving this, however, I still didn't solve it. Thanks for your hint. My rating must be reduced a lot. :(
Rating is temporary. Skill is permanent.
Thanks.
So its googleforces :/
Agree.
i just cannot become friendly with XOR, doesnt matter how much i try.
Yea me too. In theory XOR has the same abstract complexity as AND and OR. But I feel like our (at least mine) minds don't understand XOR the same, natural way they understand AND and OR. Also XOR has so many weird characteristics that aren't easy to come up with on spot.
How to solve D1?
Sorry for my poor English.
Let we call $$$b_i=\gcd(a_1,\cdots a_i)$$$,then we have $$$b_i|b_{i-1}$$$.
And $$$b$$$ is like $$$[c,\cdots c,d,\dots d,e,\cdots]$$$.
$$$dp_i$$$ Means the max value when you choose all $$$j$$$ That $$$i|a_j$$$.
Add some $$$i$$$ after $$$[\cdots,ki,\cdots,ki]$$$,so $$$dp_i=\max(dp_{ki}+i(t_i-t_{ki}))$$$ where $$$t_i$$$ means $$$\sum\limits_{j=1}^n[i|a_j]$$$.
Then we can solve it in $$$O(a\log a+n\sqrt a)$$$.
D1 was really interesting!
Really curious to know, How to do it ?
This is certainly not the right place to talk about it but I saw you video reviewing profile of users, I am stuck in green here. Would be glad If you could suggest something. Many thanks
I don't have a lot to suggest. It seems like you left CP for a long time. Anyway, if you continue to solve problems in rating [1300:1500], you should be good to go. Also, up solving at least 1 problem after every contest is a must.
How to solve D2 ? Does it involve the fact that we only have to consider atmost 25 distinct elements?
I didn't use it . I just made some small constant optimization on the code of D1 .
If so , I think there is no need to set D2 ...
Problem B, i figured out total time, but how can i print the vector? Divan's office at 1 and then sort given vector in decreasing order, then v[0] at 2,v[1] at 0, v[2] at 3 v[3] at -1 ....
you can sort a
vector<pair<int, int>>where the first element of each pair is the value, and the second element is the original index. In such way you can preserve the information of the original index.Hi everyone, sorry to bother but :( in the contests I participated in during this time, the codeforces page loads very slowly :( this prevented me from submitting my post C at the last minute can anyone give me some advice.
Try submitting using Codeforces Tool, or through these mirror sites:
I tried but it's not loading MathType.
You can use the main site for viewing problem statement, while using the mirror sites for submission :P
Help needed!!!! In q.2 of today's contest I have made a submission :
https://codeforces.me/contest/1614/submission/137006738
Above is the code ,I surely believe that there is some system error that's why it is giving me wrong answer on test case 4 ,which passed when I made some meaningless changes,in short can someone tell me why this code is not passing because I have made this submission after 13th minute ,so if this code passes then I get a very good rank as compare to now...please help
Did you forget to use long long ?
No i have used it. https://codeforces.me/contest/1614/submission/137006738 you can check it here @vaaven please help!!
"#define ll int"
Can someone help me understand why https://codeforces.me/contest/1614/submission/136996986 got TLE?
its O(nlogn).
EDIT — Seems like many people who used Python TLE'ed this problem.
D is such a funny problem. The difference between D1 and D2 is that max(a_i) difference is about 4 times bigger. Time for ConstantForces
Author's solutions have different asymptotics for D1 and D2.
Editorial will be ready soon.
I hope it isn't max(A_i)^3/2 and max(A_i)log(max(A_i)).
It is
D1: max(A_i) * log(A_i) D2: max(A_i) * log(log(A_i))
My D2: TLE on test 1[main tests] https://codeforces.me/contest/1614/submission/137008202
Moral: No matter what happens, even if it's a life and death situation, never forget to take MOD :(
Help needed!!!! In q.2 of today's contest I have made a submission :
https://codeforces.me/contest/1614/submission/137006738
Above is the code ,I surely believe that there is some system error that's why it is giving me wrong answer on test case 4 ,which passed when I made some meaningless changes,in short can someone tell me why this code is not passing because I have made this submission after 13th minute ,so if this code passes then I get a very good rank as compare to now...please help
line 4
and your "meaningless changes" include changing it to
#define ll long long intWhy this submission in C++ 17 gives TLE for D1
And the similar solution to it C++ 20 passes within the given time limits even though the worst case runtime for both the solutions is same.
Why changing in different version of C++ has so much big difference in runtime and if so then should the problem not have much flexible time limits as you can see it cost me an extra penalty just because I choose C++17 version initially
C is segment tree range-AND for each segment with their beauty and then XOR-sum in O(n) right ? Got TLE on test case 2 sadge
Doesn't actually need to be this complicated. If X is the bitwise OR of a segment, then for each set bit of X, there exists an element with that bit set. Then consider all subsequences excluding that element (2^(n-1) of them): they either XOR to 1 or 0 times 2^(bit). If they XOR to 1, then subsequence with our set bit XORS to 0; if they XOR to 0, then subsequence with our set bit XORs to 1. Either way, we are guaranteed a contribution of exactly 2^(bit) times 2^(n-1) from that bit, i.e. its contribution to x. So we just need to know if a given bit is set anywhere in the whole sequence, and if so we add that contribution. Otherwise, the bit is skipped.
In pseudocode terms
(Take mods where appropriate)
I wonder how I miss that while still understanding we can do XOR-sum in O(n) for kinda the same argument. Thank you that was helpful.
I actually missed it in contest too. I did a brute force over each bit, setting only those I had to set to 0 (i.e. where we had information on a whole segment that the bit was 0). From there I applied some combinatorics.
This was all a bit of a waste of time, and my solution just scraped through in the 1s limit.
I later realised that, by symmetry, all my combinatorics effectively came out at "half of all subsequences" for any set bit.
I guess for Question C, the question should have also asked for the possible values of elements of array, so that Lazy_propagation would have become necessary.
Here's my submission by which we can also print possible values of array.
lazy propagation wouldn't be "necessary" strictly speaking, because you can apply all the range updates before printing the array
Actually I used LAzy propagation in Segment tree for range updates. So I guess it's necessary.
You can do offline range update (i.e. process all the range update operations, then print the array) without lazy propagation segment tree
I did exactly that still got WA on pretest 3. Any idea why?
Need long long, not int, I think. When you’re multiplying two ints together you’re potentially getting an overflow before you MOD them.
but, I have defined #define int long long in the beginning (around 5th line)
Sorry you're right. You shouldn't MOD your value o.
worst problemset i've ever saw...
Very great contest,but I think the time limit for C can be 2s.
Finally Specialist Today !!!!
In problem B, I failed for the error message for the pretest: "wrong answer answer is wrong: pans = 14 is not equal real_pans = 18 (test case 1)" But the example output is 14 for the test case 1. I checked many acceptable submissions, the answer is still 14 not 18. Do I miss something?
optimal answer is 14 but your output array will give 18 that's why it is showing 18..
Passed pretests of D2 only to see failing on sample in system testing. -,-
I know right. I literally did some stupid optimization and passed D2 right now. To be honest, look at the time variance of any code from any test although solution is independent of N. The time variance is just too large sometimes reaching 500ms in that problem for no reason.
Just noticed system test was run for 3rd time. (Pretest passed, TLE2 on 1st ST, TLE18 on 2nd ST, AC on 3rd ST). What is going on? :|
I guess they decided to give people a fair go (i.e. when the servers weren't overloaded)
My submission TLEs on different test each time I resend it... Time limits should either be tighter or looser.
137041121 137027753 This is not ok. One parnthesis off
Can anyone please explain why this solution of mine for problem B is getting TLE 137017820
large input/output causes TLE, use this instruction before write anything in the main function:
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) ;
Why do you set the minimum temperature of question e to 0? Why is it not 1 or -1e9? The important boundary information is written so unobviously, fuck.
I can't understand the verdict of [problem:1614B]problem B in my code? https://codeforces.me/contest/1614/submission/137041237
Can you check my code?
check your answer manually it's coming wrong..
2 5 4 3 1 0Your array outputs:
(3*2)*3+(2*2)*8+(1*2)*10+(1*2)*6+(2*2)*1 = 86which is not the correct answer.What a painful lesson to learn that $$$2^{30} > 10^9+7$$$. (Problem C)
Was this the intended solution for D1?
I used 1D DP over all the possible factors of all the numbers.
https://codeforces.me/contest/1614/submission/137040944
I wrote a dp solution for probleme [problem:https://codeforces.me/contest/1614/problem/C] , while the complexity of my code should work just fine, the time constraints didn't fit [submission:https://codeforces.me/contest/1614/submission/137034593],
changing from long long to int, made the solution pass just fine [submission:https://codeforces.me/contest/1614/submission/137043656] , it's been a while since the last time I encountered such a problem.
I know It's not the intended solution, but mine should be accepted too, or what do you think?
NVM, both get AC now.
I would like to ask if system test slower than pretest?
When I solve problem C, it says pretests passed (12 test cases) and the time cost is about 820 ms. After carefully consideration, I decided to move on.
But I finally failed the system test, and the maximum time cost for first 12 test cases is 951ms. (And it finally failed test case 15). If I get 951ms in the pretest, I will try to optimize my code.
I see in comment section that @iaNTU failed the first test case in the system test with problem D2, he must passed test case 1 in the pretest, that is why I ask this question.
UPD: Thanks god, my contest code get AC after rejudgement.
Problem COrigial problem at Leetcode 1863Was there no pretest in C for the max N? my code TLE'd on test 17. it was O(NlogN*logN) and maybe it can be optimised but I didnt try as the pretests passed. Please try to include max N in pretests. Nice problems tho
Edit: submission rejudged it is AC now
You should always check the max N by yourself, e.g. via the Custom Invocation. There has to be some area for hacking lol
my bad, the submissions are rejudged, i should not have commented before the contest was officially over
Can there be more than 1 answer in problem C?
I don't think so. Howsoever the distribution of bits across all N elements is, in the end, it only matters if a particular bit is set in any of the N elements.
How to solve D?
Tutorial video by jqdai0815 (in Chinese)
Originally I wrote a solution for problem E which passed pretests, but resubmitted later because I was scared about TLE. Glad I did, because even my faster submission took 1996 ms! (https://codeforces.me/contest/1614/submission/137021260)
I am no Psychologist, but brah this Divan has some serious problems..
Lol, the number of upvotes of this post is getting fewer and fewer
.
I have a pupil title on the site how do I cheat from newbies?
kingkd and ayushkedia0511 are both my id because kingkd is my old it which is lost but i got it and mastakenly i gave the contest with both id, for for the voilation of rules and i will not use my old (kingkd ) id for more contests
looking at your code, i realised that you submitted your code with kingkd untill you got accepted, and then you submitted with ayushkedia0511.
it's 100% obvious that you used two accounts in purpose but now you are still lying that it was an mistake.
Please Update the Ratings . I want to see myself as a Specialist Today :_: before i go to Sleep it Late night in here in India.. Also jee main paper Doesnt decide your Future
Can someone help me figure out why these 2 similar solutions for D2 are giving different results? Is there some optimisation I'm missing?
Passing: 137049637 Not passing: 137046389
64 bit compiler is sometimes faster
Thanks! interestingly it's not just the compiler but also changing long long -> int. Seems like there were some razor thin time limits.
64 bit compiler with long long instead of int: 137063729
There is too much unnecessary use of long long, use int instead and then you should be fine.
Here are two of my exact same submissions, which differ by almost 600ms in runtime. Before this, one submission got TLEd on the first submit, and then the same code got accepted on submitting it again. 137066206 and 137066133
Are such large differences common? It seems to me that something is up with the judge.
hope this gets upvoted, the D2 time limit was really too low. See also this comment
Автокомментарий: текст был обновлен пользователем 4qqqq (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
nice problems, bad contest
How to solve D2? I cant think of any other way than computing dp for all divisors. I used the same D1 code, compute the factors only if required. But still got TLE. submission.
I also tried to create an array of divisors for all 2e7 integers with complexity 2e7 * number of divisors. Optimized to compute only where all of the prime factors of this number is <= to the max number of prime factors. There I got MLE submission. So how to solve it ?
You can create prime tables in $$$\mathcal{O}(2e7)$$$ and the we can enumerate prime's multiples. Submission
Example is when you are at $$$dp(5)$$$, you can look at $$$dp(10)$$$, $$$dp(15)$$$, $$$dp(20)$$$. But $$$dp(10)$$$ has already looked up to $$$dp(20)$$$ earlier, plus it's easy to see that $$$dp(i)$$$ >= $$$dp(i * k)$$$ where $$$k$$$ is some constant. So going for a composite check is unnecessary.
mysubmission
what's wrong with my code,can anyone help me?? thanks in advance
I think res[i+1]*a[i] is an int multiplication which overflows in your example
In question B, it is given how the businessman will travel for first 10 years(5256000 minutes) only. And it is asked to choose the cordinates such that it minimises the time for walking within first 10 years only, no info. about what to consider if he can't visit every building in that time, what to print in that case the minimum time < 10 years by visiting only some good buildings or just try to minimise the time only if buildings can be travelled within 10 years or something else can't decide
Same Doubt
Submission for problem D1
Can anyone explain the time complexity analysis of this solution and also in general for any dp solution. I become little confused sometimes while calculating time complexity of a dp solution.
Thanks in advance:)
Here's my apology for the mistake I had in the contest.
Please pardon me this time.
https://codeforces.me/blog/entry/97309
Could someone tell me how to get the table cnt[x] where cnt[x] denotes how many numbers are there which are divisible by x in o(nloglogn ) or in o(n)