### mtnshh's blog

By mtnshh, history, 5 weeks ago,

The Programming Club, IIT Indore is proud to present our flagship event, Divide By Zero! The contest will take place on Apr/11/2021 17:35 (Moscow time). This round will be rated for all participants with a rating lower than 2100.

Thanks to the following people for making the round possible:

There are 6 problems, and 2 hours to solve them. The points distribution will be updated later.

Update: The scoring distribution is 500 -- 1250 -- 1500 -- 2000 -- 2750 -- 3000.

Update: Editorial is up.

PRIZES: Twenty Codeforces T-shirt will be given to:

• Top 10 Indian Participants
• Random 10 from top 100 (rank 11-100) Indian participants

Hope you guys enjoy the contest! See you on the leaderboard!

Update: Here is the list of winners who won T-shirts. We will contact you guys soon. Congrats!

Top 10 Indian Participants

Random 10 from top 100 (rank 11-100) Indian participants

We have uploaded the link to the code for generating random numbers and ranklist here.

• +502

 » 5 weeks ago, # |   +14 Indian round ,Cool,,, Hopefully I will be gray this round :)
•  » » 5 weeks ago, # ^ |   +42 It's not about hope, You'll be gray if you participate.
•  » » » 5 weeks ago, # ^ |   +20 It was joke comment.
•  » » » » 5 weeks ago, # ^ |   +11 wow you are genius
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +30 Yess bro....Thanx for motivating me,,,,I will participate this tym,,,,I tried many time but I am not able to solve even one problem :)EDIT: Spoiler Ofc it is joke comment ,,,based on many "hope I will be this or that comment"
•  » » » » 5 weeks ago, # ^ |   0 To be honest, I wasn't motivating, wether you solve all of the problems or none you will be newbie after your first contest.
•  » » » » » 5 weeks ago, # ^ |   +5 This just got me to think, what's the maximum delta one could achieve? Like, say a new account finishes 1st in a combined round (like the global round). She will gain 500+(actual delta). Where actual delta might even be 500-600s considering it's a combined Div1+2+3 round. That's quite close to pupil, right?
•  » » » » » » 5 weeks ago, # ^ |   0 Well, first of all it depends on the contest, as you mentioned global round is rated for the 3 divisions and it's nearly impossible that an unrated account ranks the first place. So second and third divisions are left(since an unrated account can't participate in a first division contest), and I've seen unrated accounts reaching the first place in a second division contest and gained at most 900 delta.
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +9 The person said max delta so it doesn't matter if its almost impossible for an unrated account to win a contest, plus you are also forgetting alt accounts.
•  » » » » » » 4 weeks ago, # ^ |   +3 An unrated account starts from 1400, the maximum is gotten from winning a contest. Also notice that the more the people in a contest, the higher the rating for the people at the top also same if the opponents are of higher rating, so the best case is winning div 1 but its unrated for a 1400, so we have to stick to global rounds and div 2s . You can use CF visualizer to check for the contests with the highest number of people in global and div 2 and 3.
•  » » » » » » » 4 weeks ago, # ^ |   0 Unrated accounts now start from 0 rating.
•  » » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 The real rating is 1400, 0 is just the display rating.https://codeforces.com/blog/entry/77890
•  » » » » » » » 4 weeks ago, # ^ |   +2 Yes, that is why I mentioned common rounds for all divisions. With div 2 or 3 the maximum change would be less. If it is possible to get +700 then along with 500 (being first contest) one can still skip newbie and become pupil
•  » » » » » » 4 weeks ago, # ^ |   0 ur id seems to be scam 2020
•  » » » » » » » 4 weeks ago, # ^ |   0 O_o
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   -7 JrNTREDIT: Just wanna say he got 1000 in first round (I guess maximum possible)
•  » » 5 weeks ago, # ^ |   +4 Indian round ,Cool,,, Hopefully I won't be green this round :)
 » 5 weeks ago, # | ← Rev. 5 →   -48 why indian guy ?
•  » » 4 weeks ago, # ^ |   +1 because IIT indore means The Indian Institutes of Technology Indore
•  » » » 4 weeks ago, # ^ |   +3 I really think the "The" you mentioned was knowingly... Seriously..
•  » » » » 4 weeks ago, # ^ |   -10 It should be The Great Indian Institute of Technology, Indore
 » 5 weeks ago, # |   +82 i think its time to change the country part in the setting to india for this round :dicaprio:
•  » » 5 weeks ago, # ^ |   +62 Maybe time for getting a Shipping address in India too, and also ID proof.PS.: Currently, shipping t-shirts would be tough in India too, shipping worldwide is almost impossible.
•  » » » 5 weeks ago, # ^ |   +41 you can sell it to someone in india \$
•  » » » » 5 weeks ago, # ^ |   +25 Not worth the effort xD
•  » » » » » 5 weeks ago, # ^ |   +47 i know XD it was a joke but some people take it seriously lol
 » 5 weeks ago, # |   -41 How is blue coder setting problems? I think rules were changed this year, you need to be at least 2100.
•  » » 5 weeks ago, # ^ |   0 A blue can't set alone but he can do with orange or red. Orange/Red can only set contest.
•  » » » 5 weeks ago, # ^ |   +2 I think yellow can set a contest.
•  » » 5 weeks ago, # ^ |   0 Also if you have problemsetted in other juries or contests you can do it.
 » 5 weeks ago, # | ← Rev. 2 →   +82 As a contributor, I hope my contributions will become positive after this contest XD.
•  » » 5 weeks ago, # ^ |   +27 As an advisor; Try rewriting; as a contributor, in the beginning, that will surely stonk your contribution.
 » 5 weeks ago, # |   -78 One of my little dreams is to see my contributions positive !! Certainly anyone no likes negative contributions, so don't be harsh with me and help me achieve this little dream ..
•  » » 5 weeks ago, # ^ |   -43 LoL
•  » » 5 weeks ago, # ^ |   +27 I have noticed you comment in almost each blog Maybe you should try to control your urge as it seems too irritating for others.
•  » » » 5 weeks ago, # ^ |   +18 Thanks for your kind words, which caused more negative votes.. After this comment, I am no longer interested in my Contribution. I assure that you will not upset about see my comments anymore :)
•  » » 5 weeks ago, # ^ |   0 You got my upvote ;) good luck becoming positive
 » 5 weeks ago, # |   +5 Indian round cool. Expecting to do good and atleast come closer to green :)
 » 5 weeks ago, # |   +3 All the best everyone .... Jai Hind
 » 5 weeks ago, # |   +35 Many indian contest recently. You guys are motivated.
•  » » 5 weeks ago, # ^ |   -42 Naah, just population I believe xD
•  » » » 5 weeks ago, # ^ |   +6 The same reason why there are so many smart Chinese :)
 » 5 weeks ago, # |   -108 Hi Sir, I am not able to attend these contests which startsat 8:05 PM. So, Please Change the timing to Sunday Morning 10:00AM. So, Please consider my request. Thank you Sir
•  » » 5 weeks ago, # ^ |   -18 yeah sure
•  » » 4 weeks ago, # ^ |   +30 Anything else?
•  » » » 4 weeks ago, # ^ |   +9 make earth flat i guess
 » 5 weeks ago, # | ← Rev. 2 →   +33 On April 6th, a contest was held in Codechef which was prepared by IIT Varanasi. After competing in it I felt it's some what like a classical math question paper than a programming contest. So, is it Déjà vu ?
 » 4 weeks ago, # |   +11 Indian round, coolinsert nationalistic comments
 » 4 weeks ago, # |   -33 China>India
•  » » 4 weeks ago, # ^ |   0 k
•  » » 4 weeks ago, # ^ |   0 Go back to twitter!
•  » » 4 weeks ago, # ^ |   +20 Yes in inventing viruses
•  » » » 4 weeks ago, # ^ |   +4 An eye for an eye only ends up making the whole world blind.
•  » » 4 weeks ago, # ^ |   -8 Hello Do Lund Trump
 » 4 weeks ago, # |   0 good to see India here.
 » 4 weeks ago, # |   0 I wish this contest have interesting problems and strong pretests.Wish you all luck and rating increasing)))
 » 4 weeks ago, # |   0 mtnshh , When points distribution will be updated ??
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by mtnshh (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 1250 for a B problem,The B is going to be some mind-fuck problem IMO.
•  » » 4 weeks ago, # ^ |   +35 I think it is just free points.
•  » » » 4 weeks ago, # ^ |   +12 What a positive attitude you have, but then again you are a MASTER and I am a grasshopper(literally because i am green).
•  » » » 4 weeks ago, # ^ |   0 It were somewhat hard-earned free points for some of us
•  » » 4 weeks ago, # ^ |   +8 Funny thing is IMO can be read as International Math Olympiad:)
•  » » » 4 weeks ago, # ^ |   -14 It is also a common abbreviation for in my opinion.
 » 4 weeks ago, # |   -47 SRH match appud pedtunav kada ra neechuda
 » 4 weeks ago, # |   -19 I have a feeling that this contest is going to be terrible.
•  » » 4 weeks ago, # ^ |   +22 Why?
•  » » » 4 weeks ago, # ^ |   -21 looking at the score distribution
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 But you should not judge a contest by just looking at the score distribution.
•  » » » » 4 weeks ago, # ^ |   +2 Ok now I know what you were saying
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 LOL at least it was bad for me, problem C destroyed me.Such tight time limits :((Edit: Turns out it was long long maing the TLE:(((
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Sorry to bug but can you please point out what went wrong here.Edit: Missed fast I/O ;-;
 » 4 weeks ago, # |   +1 I think it's cool than chinese round,because chinese round is too hard,although it's my country...
 » 4 weeks ago, # |   0 hope I remain expert after this contest :)
 » 4 weeks ago, # |   -12 Is it rated?
•  » » 4 weeks ago, # ^ |   0 yes
 » 4 weeks ago, # |   +143
 » 4 weeks ago, # |   0 wake the firck up samurai
 » 4 weeks ago, # |   0 Every intellectual having more than one year experience of coding when solves first and only problem of div2 thinks that becoming tourist is not hard, An intellectual,2021
 » 4 weeks ago, # |   -44 MikeMirzayanov it's kind reuqest. please no codeforcoes round during CSK matches. As you know this season dhoni last season. I want to enjoy both codeforces and msd. Please atleast change timings of CSK matches
•  » » 4 weeks ago, # ^ |   +1 what is it in cricket that you like?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0
•  » » 4 weeks ago, # ^ |   0 LMAO
•  » » 4 weeks ago, # ^ |   0 you can watch match recordings as well as participate virtually
 » 4 weeks ago, # |   0 i need a t-shirt :) like them
 » 4 weeks ago, # |   +8 The score distribution is wrong, lol
 » 4 weeks ago, # |   0 Why is my nlogn solution giving TLE for B? 112705441
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You are initializing an array of size 2,00,001 in each testcase. Maybe that's the reason?
•  » » » 4 weeks ago, # ^ |   0 Even after using a map I get TLE:(
 » 4 weeks ago, # |   +4 can anyone plz tell me why D wrong on pretest 3??
•  » » 4 weeks ago, # ^ |   +68
•  » » » 4 weeks ago, # ^ |   +5 isnt_it obvious? because he got WA on pretest3
•  » » 4 weeks ago, # ^ |   0 Yes, someone please tell me what is the Pretest 3 in D. I got WA on Pretest 3. Then, I figured out I used to wrong iterator. After correcting it also, WA on pretest 3. Then I thought, maybe it is because of overflow. So, I used long long. Then also WA on Pretest 3.
•  » » » 4 weeks ago, # ^ |   0 Try this -112 122 4 10 16 2 6 3 21 30 17 20 16Answer — 55I figured it out in the end but was not able to implement it in time.
•  » » » » 4 weeks ago, # ^ |   0 It is passing. You can check my submission here.
 » 4 weeks ago, # |   +1 Can someone explain me the approach of C?
•  » » 4 weeks ago, # ^ |   +3 I precomputed number of digits for 0 to 9 until 2e + 50 and then solved eatch testcase in log10(n) by simply adding values from the array.
•  » » » 4 weeks ago, # ^ |   0 can u show me ur submission?
•  » » » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   0 I did the same thing. https://codeforces.com/contest/1513/submission/112704320
•  » » » » 4 weeks ago, # ^ |   0 mine passes in 857 ms. hella dude, your passes in 140ms, i think yours is too much optimized, can you explain what you did ?
•  » » » » » 4 weeks ago, # ^ |   0 I think you used mod(%) much more than I did. Also you used #define int long long.
•  » » » » » » 4 weeks ago, # ^ |   +5 F, I read somewhere that #define int long long will comeback to bite me someday. xD
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Can you please explain a bit like what went wrong here? One is with pre-computation and the other one without. https://codeforces.com/contest/1513/submission/112713639 https://codeforces.com/contest/1513/submission/112714167Edit: Missed fast I/O ;-;
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I think, we don't need to precalculate all the answers from 0 to 8. It is a big optimization not to do this. For more information, see my comment below.
•  » » 4 weeks ago, # ^ |   +1 its a series. https://oeis.org/A103377
•  » » » 4 weeks ago, # ^ |   0 What is the formula to that series?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 a[i] = 1 for i = 1 to 10 anda[i] = a[i — 9] + a[i — 10] for i > 10
•  » » » 4 weeks ago, # ^ |   0 Is it cool to access oeis, during the contest ?
•  » » » » 4 weeks ago, # ^ |   +7 As long as the resource being looked up exists before the start of a contest, it is okay to take help from that resource during contest
•  » » 4 weeks ago, # ^ |   0 Yes, let me try. I passed pretests of this problem after getting a TLE on the 2nd test. Let $c[n][i]$ be the number of "i" $0\leq i\leq 9$ after $n$ operations. You build the relation between $c[n][i]$ and $c[n-1][i]$; which is a 10x10 matrix A; and $c[n][i]$ can be calculated via $c[0][i]$ and $A^n$.So the goal is to calculate 2*10^5 matrices $A^k$ given the first matrix $A$(which is a sparse matrix).Since A is sparse, after calculating $A^{n-1}$, you can calculate $A^{n}$ in O(100) instead of O(1000). So the complexity to calculate all matrices is O(2*10^7); and I passed pretests in 888 ms.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 I have just debugged my code :( But I think it will be AC. EDIT: It got AC: 112711140We can calculate answer independently for every digit, so we can use precalculation.Precalculate all the answers (200000) for 9. It will take about of 2*10^6 operationsThen, in every test case count how many times every digit is present in n. I have used cnt array for that. Substract every number from 1..9 from 9 and check if it's less than m. If it is, just add calc[m — (10 — i)] * cnt[i] to the answer. Else, simply add cnt[i] to the answer.Time Complexity: amortized O(1) per every test case.Code: Code#include #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define all(x) (x).begin(), (x).end() #define len(s) (int)((s).size()) #define str(ch) string(1, ch) using namespace std; using ll = long long; using ull = unsigned long long; using graph = vector>; long long calc[200001]; void solve() { int n, m; cin >> n >> m; long long ans = 0; int cnt[10]; memset(cnt, 0, sizeof(cnt)); while(n) cnt[n % 10]++, n /= 10; for(int i = 0; i < 10; i++) { if((9 - i) < m) ans += calc[m - (10 - i)] * cnt[i], ans %= (int)1e9 + 7; else ans += cnt[i]; } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); long long cnt[10]; for(int i = 0; i < 10; i++) cnt[i] = 0; for(int i = 0; i <= 200000; i++) calc[i] = 0; cnt[9] = 1; for(int i = 0; i <= 200000; i++) { long long ncnt[10]; memset(ncnt, 0, sizeof(ncnt)); for(int j = 0; j < 10; j++) { if(j == 9) { ncnt[0] += cnt[9]; ncnt[0] %= (int)1e9 + 7; ncnt[1] += cnt[9]; ncnt[1] %= (int)1e9 + 7; continue; } ncnt[j + 1] += cnt[j]; ncnt[j + 1] %= (int)1e9 + 7; } for(int j = 0; j < 10; j++) { cnt[j] = ncnt[j]; calc[i] += cnt[j]; calc[i] %= (int)1e9 + 7; } } int tt; cin >> tt; while(tt--) solve(); return 0; } 
•  » » 4 weeks ago, # ^ |   0 I am getting TLE On Pretest 3? What is wrong with my submission?
•  » » » 4 weeks ago, # ^ |   0 try to add ios::sync_with_stdio(false); also add #pragma GCC optimize("Ofast") and #pragma GCC target("avx,avx2,fma")
•  » » » » 4 weeks ago, # ^ |   0 Yup did that! It worked thanks
 » 4 weeks ago, # |   +29 ModuloForces
 » 4 weeks ago, # |   +4 How to solve D?
 » 4 weeks ago, # |   0 Can anyone explain why I am getting Runtime error on pretest 1 for problem C? Its working fine on my local machine! https://codeforces.com/contest/1513/submission/112707395
•  » » 4 weeks ago, # ^ |   0 your code has "index out of bound" on line 51
•  » » » 4 weeks ago, # ^ |   0 How did you check that? My local runtime env doesn't complain..
•  » » » » 4 weeks ago, # ^ |   0 Add -fsanitize=undefined to your compiler's flag. But even without any flag I still got segmentation fault.
•  » » » » » 4 weeks ago, # ^ |   +5 Btw, thanks it was indeed the mistake. I reckon, you deleted your comment of -Wall, but that was some good info for me again, so thanks for that. In my case -fsanitize=undefined does give me runtime error now. Thanks a bunch! :)
•  » » » » » » 4 weeks ago, # ^ |   0 For posterity: ❯ g++ --version g++ (Ubuntu 8.4.0-1ubuntu1~18.04) 8.4.0 Copyright (C) 2018 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. ~/Desktop/competitive/codeforces/1513 ❯ g++ 1.cpp ~/Desktop/competitive/codeforces/1513 ❯ ./a.out 5 1912 1 5 6 999 1 88 2 12 100 5 2 6 4 2115 ❯ g++ -fsanitize=undefined 1.cpp ~/Desktop/competitive/codeforces/1513 ❯ ./a.out 1.cpp:52:36: runtime error: index 16 out of bounds for type 'long long int [10]' 1.cpp:52:38: runtime error: store to address 0x55f17e832c60 with insufficient space for an object of type 'll' 0x55f17e832c60: note: pointer points here 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
 » 4 weeks ago, # |   +5 so hard :(
•  » » 4 weeks ago, # ^ |   +1 I agree.
 » 4 weeks ago, # |   0 For problem A, I noticed someone's solution only printed "-1" if n>=kSo I tried to hack it with a test case of n=3, k=1But the solution was in python and I forgot integer division works differently in python :(
 » 4 weeks ago, # |   +3 This contest is hard and required to know a lot of Math knowledge, just in my opinion. It is hard for everyone who has no experience. Bye bye Blue. I am back to Cyan soon.
•  » » 4 weeks ago, # ^ |   +9 It's harder than usual but not because of the math knowledge imo.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +19 I agree that it needed more math knowledge than usual, but mostly math that occurs pretty commonly in competitive coding, not anything completely out of the blue. A — Adhoc, maybe a bit mathy B — Required some basic combinatrics, so fair enough its pretty heavy math for a B. C — Pretty standard dp, no math involved D — First observation is somewhat math intensive for a D (gcd = min means all elements are multiple of the min), but the rest of the problem requires no other math, just intuition of why Kruskal's algo constructs an optimal MST. E — Pure math, all non-combinatorial observations can be made using just the samples. Then its just standard combinatorial ideas that most 18-1900+ rated participants should have likely come across. F — didn't solve, no comments.
•  » » » 4 weeks ago, # ^ |   +1 Oh, ok. Thank you for your problem comments.
 » 4 weeks ago, # |   0 Anyone can explain Bhttps://codeforces.com/contest/1513/submission/112705171
•  » » 4 weeks ago, # ^ |   0 For B. The observation is that a[1] = a[n] = minimum value of the array. Also, for every i, a[i] & a[1] = a[1].
 » 4 weeks ago, # | ← Rev. 2 →   0 For some reason, everyone's problem A sols were hacked but its been reverted
 » 4 weeks ago, # |   +58 Problems were hella good imo, especially D
 » 4 weeks ago, # |   +3 how to solve b
•  » » 4 weeks ago, # ^ |   0 The condition in the problem is equivalent to finding the number of permutations of Indices of the array's elements so that ap1 and apn are bitwise and operation of all of the elements in array a. So let cnt be the number of occurrences of (a1 & a2 .. & an) in array a, if cnt is less than 2 then there is no such permutation and the answer is 0, otherwise the answer is cnt * (cnt — 1) * (n — 2)!.
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   +3 For intuition, consider n = 2. This has a valid permutation when both elements are identical.Now consider n > 2. What if the first and last elements in the permutation are different? Then, this is not a valid permutation since you can always make a 1-element group which has just the larger endpoint, and a (n-1) element group with all the other elements. The AND of the group with the smaller endpoint is strictly smaller so there's no solution.Now we know the end points have to be the same. What about the middle elements? Assume there's an element in the middle that has a 0 in a bit where the endpoint has a 1. Then, we can always make a (n-1) element group that will have an AND smaller than the other endpoint. So, every element a_i in the middle must equal the endpoint when ANDed with the endpoint, i.e. satisfy (a_i AND a_0) = a_0. This also implies the endpoints must be the smallest values in the array.So the answer is (count_of_smallest_element nCr 2) * ((n — 2)!), assuming there's at least 2 of the smallest element and all values in the array equal the smallest value when ANDed with it.
•  » » » 4 weeks ago, # ^ |   0 nice observation, need to study byte manipulation. weak area of mine.
•  » » » » 4 weeks ago, # ^ |   +6 Actually it is called bit manipulation ;)
•  » » » » » 4 weeks ago, # ^ |   0 Lol yes that's what I meant
 » 4 weeks ago, # | ← Rev. 4 →   0 i hate contest from these iit during contest but love them a lot while upsolving https://codeforces.com/contest/1513/submission/112707749 i did dp but fuck it
 » 4 weeks ago, # |   0 If only I never knew matrix expo, would have I not made three TLE attempts at C, coded the intended dp solution and saved the contest. Unlucky day, though I had fun nevertheless. Good contest.
•  » » 4 weeks ago, # ^ |   0 matrix expo is not needed
•  » » » 4 weeks ago, # ^ |   0 I realized, the constraints made sure it doesn't pass.
•  » » » » 4 weeks ago, # ^ |   0 Nope, I passed.
 » 4 weeks ago, # |   0 my Code for C runs five minutes after contest ends, end every time - C is based on recursion where you can start from state when number becomes two digit i.e. 10 and calculate what happens after k steps using dp.
 » 4 weeks ago, # |   0 Missed D just by a minute :(
•  » » 4 weeks ago, # ^ |   0 i understand the pain
 » 4 weeks ago, # |   +3 I really need to know why my D failed, sumission, else my brain might explode. Please.
•  » » 4 weeks ago, # ^ |   0 I have the same code... also very curious :) submissions
•  » » » 4 weeks ago, # ^ |   +3 I also have a similar solution. Maybe our logic isn't correct.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It is quite similar to the one that passed, but rn I can't find the mistake. https://codeforces.com/contest/1513/submission/112692615
•  » » 4 weeks ago, # ^ |   0 Try this -112122 4 10 16 2 6 3 21 30 17 20 16Answer — 55
•  » » » 4 weeks ago, # ^ |   +6 nope,this is not a good test,my code is right on this but wrong on 3rd TC
•  » » » » 4 weeks ago, # ^ |   +3 Maybe, but the above person's code failed on this test and mine too.
•  » » » 4 weeks ago, # ^ |   0 There are 5 components: cost 2: 2 4 10 16 2 6 cost 3: 3 21 30 3 of cost 12: 17, 20, 16 So cost of all is 5*2 + 2*3 + 4*12 == 64How to get 55?
•  » » » » 4 weeks ago, # ^ |   +3 You can connect 3 and 6 to get a cost of 3 instead of 12.
•  » » » » » 4 weeks ago, # ^ |   0 Ok, thanks :/
•  » » 4 weeks ago, # ^ |   +3 Let's say you have a testcase like this: 1 3 1000 2 6 3 Your algorithm connects 2 to 6, then doesn't connect 6 to 3. This can be fixed simply by using DSU instead of your vis[] array.
•  » » 4 weeks ago, # ^ |   0 I made the same mistake and realized it after contest. Think of the following p=10 2 4 6 3here 2 will connect 4 and 6 and 3 will be connected to(2,4,6) by p=10 in your case but the better way will be to connect 3 to (2,4,6) by the edge of weight 3.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, there's a catch out there! Notice that every time you're trying to connect your current index to some node on the left or right, you're checking if the left or right has already been considered or not! Now, consider the case like array [2,6,3]. Your algorithm will start from the first node and mark both 2 and 6 as connected So when you try to connect 3 to 6 (as 3 is the gcd of [3,6]), your algorithm denies saying that 6 is already visited! Now you can observe that the accepted codes have incorporated a slight change that allowed every node to be considered by potential values both on the left and right. An easy way out is always the DSU method, and when you wanna avoid that, you need to be careful about the components! So yeah one possible input is: 1 3 100 2 6 3
 » 4 weeks ago, # |   0 I just don't get it, why my solution of C fails with TL. Looks like some very dumb mistake, which I don't see.  int t; cin >> t; while (t--) { int n, m; cin >> n >> m; long long ans2 = 0; while (n > 0) { ans2 += cache2[m][n % 10]; n /= 10; } cout << ans2 % mod << endl; } This is the main part. The rest of the code is precomputation that doesn't depend on inputs and takes just 124ms.
•  » » 4 weeks ago, # ^ |   +4 try adding fast io tie(nullptr)sync_with_stdio(false);
•  » » » 4 weeks ago, # ^ |   0 Yep, that was the issue. Got AC with 327ms
•  » » 4 weeks ago, # ^ |   +3 I got same tle, then i change cin and cout to scanf and printf and it passed
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +13 also you use endl, which flushes the output on each iteration, use "\n" instead
•  » » » 4 weeks ago, # ^ |   0 Nice point! Using endl instead of "\n" takes 826ms vs 327ms
•  » » 4 weeks ago, # ^ |   +4 Btw, had to rewrite it from python to c++ because the most natural implementation didn't fit into time limitUnnecessary tight time limit for D2C
•  » » 4 weeks ago, # ^ |   0 Slow I/O operations, i.e., cin/cout.Just added this to your code: ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); Btw, it got WA due to integer overflow: 112713355
•  » » » 4 weeks ago, # ^ |   +3 Yes, I've already fixed it: https://codeforces.com/contest/1513/submission/112712250
 » 4 weeks ago, # |   0 https://codeforces.com/contest/1513/submission/112698905This is my solution for Problem C. According to me, its Time Complexity is O (10 * m) which is 2 * 10 ^ 6, which is very well for 1 second, I believe. It is giving TLE verdict on pretest 3.What can be the possible reason behind this ?Thank you !
•  » » 4 weeks ago, # ^ |   +1 every time you count dp again
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Its O(10*m*t)
•  » » » 4 weeks ago, # ^ |   0 I believe time limit per test case is 1 second, so why is t being included in Time Complexity ?Correct me if I am wrong.
•  » » » » 4 weeks ago, # ^ |   +5 Each test includes t test cases. Time limit for ALL t test cases is 1s
•  » » » » » 4 weeks ago, # ^ |   0 Ohh okay, wasn't sure about it ! Thanks a lot !
•  » » 4 weeks ago, # ^ |   0 You are given t <= 200000
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +2 The time complexity of your solution is O(t*10*m) which can be around 10^11 in worst case. So, it is giving TLE.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 deleted (answered the wrong comment)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 deleted
•  » » 4 weeks ago, # ^ |   0 Just precalculate the dp once instead of calculating it every time.
 » 4 weeks ago, # |   +38 Could somebody tell me how to do E and F :
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +33 For E, we want to reach $\frac{sum}{n}$ as the value of all elements. Lets call this the $\textbf{good}$ value of the array, all elements smaller than it as $\textbf{low}$ elements and all elements larger than it $\textbf{high}$ elements.Clearly a high element can never be made less than good, as it can never be used later as a sink (due to step 4), meaning we can never make it good. Same for low elements and greater than x. For the same reason, good elements can never be used in an operation.Now lets notice that if there exists any subsequence of the form $\textbf{low high low high}$ or $\textbf{low high high low}$ or $\textbf{high low low high}$, we can get different end costs by mapping the lows to different highs. So if there is more than 1 low and more than 1 high, we need them to all be separate, that is all lows before highs or vice versa.So we just want to arbitrarily choose where to place the $\textbf{good}$ elements in the array, multiply that by the number of ways of individually permuting $\textbf{low}$ and $\textbf{high}$ respectively. (and that by 2 if the array actually has $\textbf{low}$ and $\textbf{high}$ elements for the other direction)Ways of choosing places of good elements is clearly just $n \choose cnt_{good}$. Ways of placing low and high can be found is just multinomial theorem.
•  » » 4 weeks ago, # ^ |   0 In E array is balanced if sum is divisible by n and there is no subarray [x, y, x, y] where x is less than sum / n and y is greater than sum / n. You can calculate number of combinations with multinomial coefficient.
•  » » 4 weeks ago, # ^ |   +26 Wow now that I realized I misread the problem statements. I thought i can't be source anymore :<. Wonder how many people like me and can't solve E :
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   +23 I did as well for 20 mins and asked a clarification for the sake of my sanity after seeing it was the other way around. That part is really unnatural, like you'd expect it to say $i$ and $j$ can't be used again as source and sink respectively but it says the opposite. Once you realize the reason for the condition its obvious which it is, but till then its something that's really easy to miss and should have been bolded.
•  » » » » 4 weeks ago, # ^ |   0 Totally agree!
 » 4 weeks ago, # |   +3 My Submission for C got TLE on pretest 3. Afterwards, including fast I/O and changing for(auto x:s) to for(auto &x:s) ,it got passed. How?
•  » » 4 weeks ago, # ^ |   +5 because t <= 2 * 10 ^ 5 and you code for passing system test needed for ios_base or scanf & printf
•  » » 4 weeks ago, # ^ |   +1 The constraints were too tight:)
 » 4 weeks ago, # |   0 I had resubmitted my same correct solutions of first two questions later but my earlier correct solutions were skipped in system testing and my rank got changed .What can I do now?
•  » » 4 weeks ago, # ^ |   +30 You can do nothing. That's the rule.
•  » » » 4 weeks ago, # ^ |   0 But I had submitted same solution both times.
•  » » » » 4 weeks ago, # ^ |   +8 Yes, but CF doesn't know that. And even if it does, that's literally the rule. You can't really complain about this.
•  » » » » 4 weeks ago, # ^ |   0 yeah, the one submitted later is considered even if the previous one was accepted, also I don't think codeforces lets you submit exact same solution twice.
•  » » » » » 4 weeks ago, # ^ |   +14 He just removed some comments of the old submission so that's kind of unfortunate.
•  » » 4 weeks ago, # ^ |   0 Codeforces considers the most recent submission even if the earlier one is correct:)
•  » » 4 weeks ago, # ^ |   0 I think codeforces doesn't allow the exact solution to submit twice. At least when upsolving.
 » 4 weeks ago, # |   -38 problem A: here take some cheesy math! problem B: here take some more math! problem C: hold on! I got some more math!honestly speaking, Problem set sucked! you know math you solve it easily, you suck at math you get rammed!
•  » » 4 weeks ago, # ^ |   +23 >see numbers >"MATHFORCES!!!"
•  » » 4 weeks ago, # ^ |   +28 None of the problems were related to math excluding B, besides that they include numbers and digits... C was DP, B had an observation, counting permutations was an easier part and A was just a constructive.
•  » » 4 weeks ago, # ^ |   +18 I thought it was quite a well balanced round in terms of topic variety.
 » 4 weeks ago, # | ← Rev. 2 →   0 Could someone please provide me counter case for my submission of problem D .Test case 3 is very long.
•  » » 4 weeks ago, # ^ |   +3 Here is a counter: 1 5 1000 2 12 6 3 5 
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 See this comment, I think it is same problem as my code.The problem is, we do connect adjacent elements only if they have same gcd on both directions. But that is wrong, something like 2 6 3 gets connected for the price of 5 instead of 2+p
•  » » 4 weeks ago, # ^ |   0 thanks VTifand for counter case.thanks spookywooky.Yes it was that mistake. I corrected it.
 » 4 weeks ago, # |   0 The problem C and D are wonderful! Really nice round.I love it.
 » 4 weeks ago, # |   0 got the idea of solving C when there was only a few minutes left. tried my best to implement it but just couldn't finish in time :'(
 » 4 weeks ago, # |   +3 https://codeforces.com/contest/1513/submission/112708303 Here is my solution for question c.. which is giving TLE.. but I suppose it's time complexity is O(m*10+t*10) in the worst case.. please explain
•  » » 4 weeks ago, # ^ |   +5 you have long long everywhere, try to replace it with int
•  » » 4 weeks ago, # ^ |   +6 Try to use "\n" instead of endl because endl takes a lot of time as it clears the buffer after each output
•  » » » 4 weeks ago, # ^ |   0 He has #define endl "\n"
•  » » 4 weeks ago, # ^ |   +1 Replace endl by "\n", as it takes about 500ms more
•  » » » 4 weeks ago, # ^ |   0 I have defined #define endl "\n
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone please review or suggest why my problem C solution is giving TLE? I precomputed the values and added in the sum but still test case 3 fails. Here's my solution : 112712714
 » 4 weeks ago, # | ← Rev. 2 →   +6 .
•  » » 4 weeks ago, # ^ |   0 What about the submission links and their usernames? Copy pasting the code doesen't help much.
 » 4 weeks ago, # |   0 https://codeforces.com/contest/1513/submission/112681391Can someone please explain why I am getting TLE on this solution of C? I think the time complexity is O(m+t*log(n)) which should run well within 1 second?
•  » » 4 weeks ago, # ^ |   +1 Same issues as in my solution, see comment https://codeforces.com/blog/entry/89520?#comment-779333
•  » » » 4 weeks ago, # ^ |   0 Let me know why my solution is getting TLE . I have used fast I/O https://codeforces.com/contest/1513/submission/112700123
•  » » » » 4 weeks ago, # ^ |   +3 You are actually do the dp 10 (or 20) times you need to. Consider that a digit x produces the same result after m steps as the digit x+1 after m-1 steps.
•  » » » » » 4 weeks ago, # ^ |   0 Ya i have implemented the same
•  » » » » » » 4 weeks ago, # ^ |   0 No, you did not. You can get rid of this outer loop for (int k = 0; k <= 9; k++) {, would make it 10 times faster. for example see this submission
•  » » » » » » » 4 weeks ago, # ^ |   0 Ok thanks
•  » » » » » » 4 weeks ago, # ^ |   0 U have used endl ,which itself takes too much time,in case of big test cases, just replace endl by "\n" ,u will see the time will be reduced to half of the previous execution time.
•  » » » » » » » 4 weeks ago, # ^ |   0 Got it thanks!
•  » » » 4 weeks ago, # ^ |   0 Thanks. Got AC with FAST I/O. 732ms to 186 ms with printf instead of cout.
•  » » 4 weeks ago, # ^ |   +4 try using FAST I/O statement you can go and see into my submissions your code is accepted after using FAST I/O
•  » » » 4 weeks ago, # ^ |   0 Thanks. I didn't know about FAST I/O
•  » » » » 4 weeks ago, # ^ |   0 use scanf, printf
•  » » » » » 4 weeks ago, # ^ |   +4 For heavens' sake, stop using scanf and printf in c++ and don't recommend them to others. They don't belong to this language
 » 4 weeks ago, # |   0 When can we get the editorial.
 » 4 weeks ago, # |   +6 Incredible contest:)a contest with decent level gradient in the questions.
 » 4 weeks ago, # | ← Rev. 2 →   +36 Here I see a lot of comments related to problem C. Most have implemented using a 2d array of size [2e5]*[10]. I would like to share that it is possible to solve the question by 1d array of size [2e5] only. No need to preprocess for all digits from 0-9. You can preprocess all answers for zero, and then the answer for digit 'd' would be simply dp[m + d]. But, here you need to note that instead of precomputing till 2e5, you will have to precompute till at least 2e5+9.You can check my submission here.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 https://codeforces.com/contest/1513/submission/112719310 Here is my solution for question c.. which is giving TLE.. but I suppose it's time complexity is O(m+t) in the worst case.. please explain
 » 4 weeks ago, # |   0 This round really awesome with some good problems but that's my bad I couldn't solve problem C.
 » 4 weeks ago, # | ← Rev. 2 →   +2 C is nice!!Those who are unable to do it let me explain lets think in this way if the number is this 023109so if we know that after m operation what is the length if we start from "9" so if we know that after m operation what is the length if we start from "2"so we just have to add cnt(0,m) + cnt(2,m) ..... cnt(9,m)where cnt(x,y) denotes what is the length after y operation if we start from xwe can precompute ans for 0 to 9 for each m this wont take O(m*10*10) time complexity which satisfies our time limit
•  » » 4 weeks ago, # ^ |   0 https://codeforces.com/contest/1513/submission/112708303 Here is my solution for question c.. which is giving TLE.. but I suppose it's time complexity is O(m*10+t*10) in the worst case.. please explain
 » 4 weeks ago, # | ← Rev. 3 →   0 Can anyone help me in understanding why my code failed for problem B?I used the logic of getting the lowest element. Then there are two positions for it, so cnt[lowest_element] * (cnt[lowest_element] — 1), and then I multiplied it by fact[n-2] ( for handling various permutations of the middle elements )https://codeforces.com/contest/1513/submission/112699438Thank you( edit -> linked wrong submission )
•  » » 4 weeks ago, # ^ |   0 You also need to check weather the AND operation of all numbers is equal to the smallest number or not. In case they are not equal than the answer is 0. (also for finding the AND of all numbers initlize the variable used for this purpose by the first element of array and not 1).
•  » » » 4 weeks ago, # ^ |   0 I used INT_MAX and i & with all the elements, still got Wrong anwer on pretest 3. https://codeforces.com/contest/1513/submission/112687504
•  » » » 4 weeks ago, # ^ |   0 Thank you for replying. Will try this out.
 » 4 weeks ago, # |   -40 I am extremely disappointed with test cases of problem C of this round. I wrote a perfectly correct algo for the problem and was constantly getting TLE in testcase 3 of the problem. After the contest ended i just changed cin/cout by scanf/printf and boooom, it passed all test cases. You should avoid such test cases which show TLE just due to the way of taking I/O.
•  » » 4 weeks ago, # ^ |   0 I wonder how did you solve problems with large input before.
•  » » » 4 weeks ago, # ^ |   0 I always used cin/cout before and it always worked for me, i realized today that they actually have some significant time difference
•  » » 4 weeks ago, # ^ |   +3 You should always use fast IO (the ios_base......stuff)
•  » » » 4 weeks ago, # ^ |   0 will be doing that from now onwards
 » 4 weeks ago, # |   0 Can anybody help me to find why my solution is wrong for problem B? Thanks in advance. https://codeforces.com/contest/1513/submission/112687504
•  » » 4 weeks ago, # ^ |   0 ans=(c*(c-1)*fact_table[n-2])%modu; Replace the above line in your code with-ans=(((c*(c-1))%modu)*fact_table[n-2])%modu; and see if it works.
•  » » » 4 weeks ago, # ^ |   0 Thanks bro, now i will go and cry in the bathroom.
•  » » » » 4 weeks ago, # ^ |   0 should write it as c*(c-1LL) to avoid overflow.
•  » » » » » 4 weeks ago, # ^ |   0 ans=(((c*(c-1LL))%modu)*fact_table[n-2])%modu;
•  » » » » » » 4 weeks ago, # ^ |   0 Thanks bro!!
 » 4 weeks ago, # |   +3 why is my solution to B giving wrong answer? please tell. 112718984
•  » » 4 weeks ago, # ^ |   +7 The problem is with the precedence of operators (sad). In your code, if you change this line if(a[i]&mi != mi) to this if((a[i]&mi) != mi). It will work. This kind of mistake sucks xD
•  » » » 4 weeks ago, # ^ |   0 Thank you!
 » 4 weeks ago, # |   +1 waiting for editorial .....
 » 4 weeks ago, # | ← Rev. 2 →   0 Does anyone have an idea why is this (https://codeforces.com/contest/1513/submission/112721127) nlognlogn solution too slow?EDIT: nvm I know where I made a mistake
 » 4 weeks ago, # |   0 Thanks for your effort!Problems B, D and E are beautiful and so good in my opinion.Problem C is just rude because of its TL, in my opinion. It's just about pre-calculation. Testcases are queries, in fact. Matrix exponentiation solution with O(1e3 * log(m) * testcases) should pass, because it is not a simulation solution anymore. Even matrix solution with O(1e3 * 2e5) pre-calculations didn't pass. Why so tight TL?
 » 4 weeks ago, # |   -26 I just received a message about leaking of code or same solution. But I really don't know how are solutions matched . Yes by mistake I used Ideone in public mode . I accept my mistake but don't block my account this mistake will never happen again in the future
 » 4 weeks ago, # | ← Rev. 2 →   0 Editorials are on time.
 » 4 weeks ago, # | ← Rev. 3 →   +4 I saw lots of solutions for problem C with precalculating length after m operations separately for different digits. But notice that after applying 1 operation to 1 we get 2, then 3, ..., 9. This means that for example applying m operations to 7 is the same as applying m + 7 operations to 0. So, we can precalc this values for 0 only.
•  » » 4 weeks ago, # ^ |   0 I tried the same but failed. Can u share your solution?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It‘s dirty, but here it is 112685719
 » 4 weeks ago, # |   +13 My submition is still waiting for recounting(((
•  » » 4 weeks ago, # ^ |   +9 We'll check tomorrow.
 » 4 weeks ago, # |   0 Does somebody know why identical submission show different results?
•  » » 4 weeks ago, # ^ |   +42 lol, because one problem is C and the other is D
•  » » » 4 weeks ago, # ^ |   +8 wow, im actually stupid, thank you
 » 4 weeks ago, # |   0 If I get Wrong answer on pretest 1 then will that be counted as penalty(-50)?
•  » » 4 weeks ago, # ^ |   0 No, It will not count as a penalty
 » 4 weeks ago, # |   +7 Memorable contest for me. I became an expert:)
 » 4 weeks ago, # | ← Rev. 2 →   +3 I got this message after the contest: Attention! Your solution 112682833 for the problem 1513C significantly coincides with solutions IloveUless3/112679357, jamil314/112682833. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. This is my submission : https://codeforces.com/contest/1513/submission/112682833 This is the other submission : https://codeforces.com/contest/1513/submission/112679357 I don't see how that is not a coincidence! And I already got another warning in another contest for compiling in ideone (which, at that time, i did not know was a violation of rules)
 » 4 weeks ago, # |   +5 Who experienced rollback rating for this contest? I am unrated this contest and come back to Blue? Some thing went wrong???
 » 4 weeks ago, # |   0 I think it is funny!
 » 4 weeks ago, # |   +25 Can you guys please announce the selected random 10 contestants for a t-shirt from 100?
•  » » 4 weeks ago, # ^ |   0 Updated!
•  » » » 4 weeks ago, # ^ |   0 Hey I just checked the list of top 100 participants. My name was not there, although I think that it should be there. Any specific reason?
•  » » » » 4 weeks ago, # ^ |   0 We have updated the ranklist; there is no change in ranks.It was an honest error from our end; sorry for the inconvenience.
•  » » » » » 4 weeks ago, # ^ |   0 No issues. I thought there was some other reason.