### Блог пользователя MemorySIices

Автор MemorySIices, история, 8 месяцев назад, ,

Greetings to the CodeForces Community!

The February Long Challenge is just around the corner and I would like you to be a part of it. With 10 programming questions spread across 10 days, you can participate and solve all of Chef's puzzles. Joining me on the problem setting panel, we have:

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below after the contest.

Contest Details:

Time: 2nd February 2018 (1500 hrs) to 12th February 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/FEB18

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

•
• +62
•

 » 8 месяцев назад, # |   0 Auto comment: topic has been updated by MemorySIices (previous revision, new revision, compare).
 » 8 месяцев назад, # |   0 Auto comment: topic has been updated by MemorySIices (previous revision, new revision, compare).
 » 8 месяцев назад, # | ← Rev. 2 →   0 MemorySlices your editorial in the sept17 contest were great. Hope for the same. :)
•  » » 8 месяцев назад, # ^ |   +5 This isn't MemorySlices. He is yellow :O
 » 8 месяцев назад, # |   +10 Wow, really excited to see author from my country! Great job kamranm.
•  » » 8 месяцев назад, # ^ |   +4 Thank you. ) I hope you will enjoy the problems.
 » 8 месяцев назад, # |   +13 How fast is the CodeChef's judging server? Is it as fast as Codeforces' judging server?
•  » » 8 месяцев назад, # ^ |   +13 I think it's a bit faster than codeforces, about 1.2 times.
•  » » » 8 месяцев назад, # ^ |   +11 I believe that that statement is a bit controversial. While Codechef's judge has significantly improved, it still judges 2x slower than Codeforces's judges when there are long queues and only just equals Codeforces's when the queue is small.
•  » » » » 8 месяцев назад, # ^ | ← Rev. 2 →   +8 Does that mean a solution could get TLE when the queue is large and get AC when the queue is small?
•  » » » » » 8 месяцев назад, # ^ |   0 I dont have very accurate knowledge on how codechef's judge (or any other OJ for that matter) works but to my experience, that has never happened.
•  » » » » 8 месяцев назад, # ^ | ← Rev. 2 →   +21 Can you please tell where did you notice that and we will investigate it if it turned out to be true.
•  » » » » » 8 месяцев назад, # ^ |   -9 I had this problem whilst solving problems of JAN18, some of my submissions took as long as 4-5 minutes to get judged. I have also often had this problem while practicing on days a Long Challenge is going on. I guess the problem then is the priority given to submissions of the contest but since it is a long contest, the same problem prevails for 10 days and I often avoid practicing on codechef during those days :/
•  » » » 8 месяцев назад, # ^ |   -19 shut up :)
•  » » » 8 месяцев назад, # ^ |   +8 Reduce time of other language such pypy and pyhton for problems.
 » 8 месяцев назад, # | ← Rev. 2 →   0 Is it possible somehow to contact CodeChef admins regarding wrong institution name on Codechef? I did not get any personal response from feedback@codechef.com and admin@codechef.com.
 » 7 месяцев назад, # | ← Rev. 3 →   +19 Hello,We are looking for people to write editorials of Codechef problems, if you are interested please apply in this email: problems@codechef.com, please identify yourself and include anything that can encourage us to assign you as editorialist.requirments:1- Editorialist should have good writing skills and know how to orginize ideas2- Editorialist should be high rated competitve programmer because he has to understand solutions to difficult problems 3- Editorialist should be responsible and provide editorials on time4- Editorialist should be able to provide very high quality of editorials, example of typical editorials: link1, link2, link3Compensation: Long challenge: 300$for editorials of all problemsCook-off: 150$ for editorials of all problemsLunchtime: 150\$ for editorials of all problems
•  » » 7 месяцев назад, # ^ |   0 What about challenge problem? Should editorialist write solution which gives a good score (like 70-80)?
•  » » » 7 месяцев назад, # ^ |   0 Editorialist is not required to come up with solutions himself (generally speaking, not only challenge problem), he can seek help from problem setter/tester but he should be good enough to be able to understand the solution.
•  » » 7 месяцев назад, # ^ |   -32
 » 7 месяцев назад, # | ← Rev. 3 →   0 For problem CHANOQ, is there a chance for solution? I thought this was a pretty easy problem for a level 7 until I get TLE...I sorted the segments in the increasing order of left endpoint, then divided them into block, and for each of the block, I sorted the segments in the decreasing order of right endpoint. Then, for each of the point, I can update the parity of all the segment in Unable to parse markup [type=CF_TEX]. My code
•  » » 7 месяцев назад, # ^ |   +5 My solutionBasically it solves the problems separately for queries with one point, two points and 3 or more points. The first two cases can be easily solved with segment tree, and the last one means that there are no more than 2e5 / 3 such queries, and it can be solved with bitset within the memory limit for O(n2).
•  » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 I solved it with square root decomposition (AC), with the following algo:If the number of points in input query are greater than , then do brute force in O(N). There can be no more than such queries, so complexity for this part is Unable to parse markup [type=CF_TEX].If the number of input points is less than Unable to parse markup [type=CF_TEX], then do Unable to parse markup [type=CF_TEX] with persistent segment tree. Note that Unable to parse markup [type=CF_TEX] is less than Unable to parse markup [type=CF_TEX]. Also, Unable to parse markup [type=CF_TEX] pre processing is required for PST. My Code.
•  » » » 7 месяцев назад, # ^ |   +3 can you please explain the persistent segment tree part a little more. It will be a great help for the beginners like me :) Thank you!
•  » » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 Actually in the ith segment tree, we update for all segments having left point Unable to parse markup [type=CF_TEX], leaf node Unable to parse markup [type=CF_TEX]. This is the pre-processing. Then , we can easily answer in O(logN), number of segments having left end point between l...r and having right end point between Unable to parse markup [type=CF_TEX].
•  » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 The overall complexity is still with a lower constant factor, right? PS: Oh right, if we set M a bit lower than , the running time will be reduced.
•  » » 7 месяцев назад, # ^ |   +8 You can also solve it in O(M*(N/32)) in a very short code using bitset and exploiting codechef's memory limit.Code
•  » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 It's funny how this solution run even faster than .AJ.'s solution.Bitset is really overpowered...
•  » » 7 месяцев назад, # ^ | ← Rev. 2 →   +15 A trick is to let the size of block be something like Unable to parse markup [type=CF_TEX] or Unable to parse markup [type=CF_TEX] so that time complexity becomes Unable to parse markup [type=CF_TEX] rather than . (Hey, a Unable to parse markup [type=CF_TEX] speedup!)Another trick is to choose the constants before block size carefully. Unable to parse markup [type=CF_TEX] and Unable to parse markup [type=CF_TEX] are usually very different. This is better done by experiments.
 » 7 месяцев назад, # |   0 can someone please explain how to solve "chef and Land labelling" problem.
•  » » 7 месяцев назад, # ^ | ← Rev. 3 →   0 Greedy works. Find all candidates for each row and update row with minimum number of candidates. Don't forget to delete non-proper candidates of other rows after giving label to some row. To admins, testcases of this problem are weak. My solution is O(n3) which can be decreased into O(n2logn) very easily, but it still gets accepted.
•  » » » 7 месяцев назад, # ^ |   0 if you don't mind then can you please elaborate your solution.
•  » » » » 7 месяцев назад, # ^ |   0 For finding candidates for each row, we need to don't consider 0's in the matrix, so we keep each row in v[i]. Let can[i] be set of candidates for row i. For each x, we consider x as candidate of row i if permutation created by x is some rearrangement of row i. This code finds candidates for (int x = 1; x <= n; x++) { vector cur; /// cur is the permutation created by x for (int y = 1; y <= n; y++) { if (x != y) { cur.pb (d[gcc[x][y]]); /// number of common divisors is count of divisors of gcd } } sort (all (cur)); for (int i = 1; i <= n; i++) { if (cur == v[i]) { /// v[i] is also sorted, so it gives true if cur is some rearrangement of cur can[i].insert (x); } } } Now we need to sort can[i] by size of its set (its hypothesis of our greedy). For that, we make another set s and keep id and size of each can[i]. How to make s set > s; for (int i = 1; i <= n; i++) { s.insert ({can[i].size(), i}); } We know that answer is always possible, so we do following operations exactly n times: Select first element of s (which has minimal count of numbers in can[id]) and update its label with any of numbers in can[id]. Update of label auto t = *s.begin(); int num = *can[t.S].begin(); lbl[t.S] = num; We also know that d[gcd(label[i], label[j])] = arr[i][j] if d[x] is count of divisors. So, for each i, d[gcd(label[id], label[i])] = arr[id][i] and we know id (which is t.S in above code). Therefore, we need to delete "bad" numbers from can[i] set for each i. For finding this "bad" numbers needs iterating can[i] set and deleting something while iterating set doesn't seems good, so make new array and push there bad numbers, then delete them. Deleting bad numbers vector del; del.pb (num); for (auto it = can[i].begin(); it != can[i].end(); it++) { if (d[gcc[*it][num]] != arr[t.S][i]) { /// it is bad number del.pb (*it); } } for (int j = 0; j < del.size(); j++) { can[i].erase (del[j]); } s.erase (itt); if (can[i].size() > 0) { s.insert ({can[i].size(), i});/// don't forget to update set s } else { used[i] = 1; } 
 » 7 месяцев назад, # |   +6 LUCASTH: Use dp/bruteforce for finding values of f(n, k) for every 0 ≤ k ≤ n and oeis it, first result will be A130534. Then google Stirling numbers of first kind and get some information from wikipedia about it. Next thing is googling "Stirling numbers of first kind modulo". You will find PDF in second result, look it and there is solution in page 4:Theorem. For n fixed, the number h(n, p) of Stirling numbers of first kind that are not multiples of p is given byh(n, p) = (ns + 1)(ns - 1 + 1)... (n1 + 1)h(n0, p)where (ns, ns - 1, ... n0)p is the p-ary representation of n.Calculating p-ary representation of number needs O(logp(n)) time, so it is easy to get one part of answer — the multiplication of (ns + 1)(ns - 1 + 1)... (n1 + 1). But, what about h(n0, p)? Notice that n0 < p ≤ 105. And there is one formula in wikipedia:Can be solved by FFT. Learn FFT, write code and get AC.By the way, if you are aware of HackerRank Week of Code hard tasks, Stirling numbers of first kind will remind you Sasha and Swaps II problem and you can find FFT code to calculate this numbers in the editorial :)
•  » » 7 месяцев назад, # ^ |   0 Ok, so I have a question about FFT. Specifically, numpy's implementation of FFT.If you (or anyone else) have tried using numpy's FFT (numpy.fft.fft and numpy.fft.ifft), I'd like to know how good it is. At the very least, can it be used in a contest without worrying too much about TLEs and approximation errors?I came to the answer of the question using FFT, but didn't have time to learn it and implement it myself. Instead, I tried using numpy's version, but that gave me a TLE on even the first subtask. With Python's time limit multiplier, that's 20 seconds — direct multiplication didn't even take a second for the same thing.So, is the problem the implementation, or is it possibly my use?For reference, assuming I'm multiplying P and Q, I was pretty much doing: fft(P) fft(Q) Multiply P and Q coordinate-wise to get R ifft(R) I hope that's correct?(I'll try to learn and implement FFT myself soon and figure this out, but I'm just curious in general)
•  » » » 7 месяцев назад, # ^ |   +8 numpy's FFT? Python? It gets AC hardly in C++, I don't think it will pass. But if you know python, why not to check it?While checking some solutions in python, I noticed that tests of this problem are also very weak, for instance, see this submission: https://www.codechef.com/viewsolution/17348967 . It returned answer is n0 + 1 if n > 40000 and brute-forced otherwise. You can observe that answer is n or n + 1 (mostly n + 1) if n < p, even I have submissions with returning n + 1 for n0 (click). One can find test for n > 40000 and answer for n0 is not n0 + 1. kingofnumbers, please give more attention for tests, some hard problems has really weak test data and it is not good to see one passed tests with wrong solution while you crack your brain on that problem all day.
•  » » » » 7 месяцев назад, # ^ |   0 I don't actually know much Python lol, I just wing it and search what I need to implement whatever I'm thinking of. Python basically comes in when I want to do something with bignums, pretty much everything else is C++.But yeah, I should probably figure this out myself, you're right.Is the FFT multiplication right, though? A quick read got me that, so I might be missing something there.And, that's kinda a shame about the tests...
•  » » » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 Very nice FFT tutorial here: http://codeforces.com/blog/entry/43499It is multiplication of two polynomials in O(nlogn) time instead of simple O(n2).
•  » » » 7 месяцев назад, # ^ |   0 If you want to use numpy you can also use numpy.polymul, it uses numpy.fft under the hood for bigger multiplications and bruteforce for smaller ones. I also used it and got AC so it's not that slow: https://www.codechef.com/viewsolution/17347833
 » 7 месяцев назад, # |   0 Can anyone explain, How to solve "BROKEN CLOCK" in simple way. Not able to understand the solutions in submission. Link for Problem — BROKEN CLOCK
•  » » 7 месяцев назад, # ^ |   +1 first we calculate all the cos terms of power of two by formula (cos (2*theta) = 2* cos^2(theta) — 1) we have all the cos terms of exponents of 2. Now, while calculating cos terms we parallely compute sin terms also.Now, the problem is that sin(theta) may be irrational! But this will not affect our answer. Why? : because we are interested in only cos(x) value and we know cos(x+y) = cosx*cosy — sinx*siny. So, as we can see there are two sin terms and both multipled together. and we know while calculating sin(x*theta) we use 2*sin((x/2)*theta)*cos((x/2)*theta). As we further break the sin((x/2)theta) we see that it ultimately stops at sin(theta) (NB : WE ARE ONLY CALCULATING SIN FOR POWER OF 2 SO, IT IS ALWAYS TRUE). so, we can claim that in the above formula the term 'sinx*siny' contains irrational terms in pair(i.e. either both have irrational part(which have same value) or none) so, if we ignore this irrationa part and just compute sin(2*theta) = 2*sin(theta)*cos(theta) then at the time of computing cos(x+y) we simply multiply the whole sin term (i.e. sinx*siny) with (sqrt(l^2 — b^2)*sqrt(l^2 — b^2))!Now, so far we have all the sin and cos precomputed (all the powers of 2 upto 62). so, how to answer the query(i.e cos(theta)) for a particular 'theta'!suppose theta = 15 --> 8 + 4 + 2 + 1we have cos(8*t) and cos(4*t) (and corresponding sin values also) so, we can apply formula cos(x+y) to get cos(12t).Now, moving forward we have cos(12t) and cos(2t) (and corresponding sin values also) so, again we can get cos(14t).finally we have cos(14t) and cos(t) (and corresponding sin values also) so, we get cos(15t).!!
•  » » 7 месяцев назад, # ^ |   +3 Idea is almost same as above comment, calculating cos(n * t) gives us answer. We use cos(n * 2x) = 2 * cos2(n * x) - 1 is t = 2x. But for odd t instead of calculating sine I used that:We know cos(x) + cos(y) = 2 * cos((x + y) / 2) * cos((x - y) / 2). Replace x = n * t, y = t. So,cos(n * t) + cos(t) = 2 * cos((n + 1) * t / 2) * cos((n - 1) * t / 2), therefore, cos(n * t) = 2 * cos((n + 1) * t / 2) * cos((n - 1) * t / 2) - cos(t). Use memoization to avoid TLE.Nice problem.
•  » » » 7 месяцев назад, # ^ |   0 but how to store values upto 10^18 i came up with the formula cos(n θ)+cos((n-2) θ) = 2cos(θ) * cos((n-1)θ) but where to store values upto 10^18 ?
•  » » » » 7 месяцев назад, # ^ |   0 Your formula will work in O(n) because, if n is odd, you will calculate n-2 which is also odd, then n-4 which is also odd and so on. About storing values, use map.See my code: https://www.codechef.com/viewsolution/17285268
•  » » » » » 7 месяцев назад, # ^ |   0 yes , and since n=t(here) can be large upto 10^18 this was not an effective one as at most everytime i m subtracting 2 from it ... ur formula is divides each θ by 2 therfore it will be much faster.And pls correct me .. u dont have to deal with irrational values as finally t will be either 1 or 0. am i right ??
•  » » » » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 Yes. t will be 1 in the end and we know value of cos(x) from input which is not irrational value.
•  » » » » » » » 7 месяцев назад, # ^ |   0 Thanks @toonewbie for the explanation !
•  » » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 I also got the same formula, but I used matrix exponentiation to solve this equation.Link to my solution
•  » » » » » 7 месяцев назад, # ^ |   0 thats where i got stuck .. didn't have prior knowledge of Mexp. i could store values upto 10^6 but what to do further i was not getting !!
•  » » » » » » 7 месяцев назад, # ^ |   0 See this for learning matrix exponentiation, just in case you want :)
•  » » » » » » » 7 месяцев назад, # ^ |   0 thanks !! for the link ..
•  » » » 7 месяцев назад, # ^ | ← Rev. 4 →   +3 Here's another idea, perhaps a bit easier to implement. Use the formulas:Unable to parse markup [type=CF_TEX] and Unable to parse markup [type=CF_TEX]With Unable to parse markup [type=CF_TEX] and Unable to parse markup [type=CF_TEX], we have:Unable to parse markup [type=CF_TEX] and Unable to parse markup [type=CF_TEX]Add them up and we have:Unable to parse markup [type=CF_TEX], or, equivalently, Unable to parse markup [type=CF_TEX]This is now a simple linear recurrence, which can be calculated using matrix exponentiation: Unable to parse markup [type=CF_TEX], where Unable to parse markup [type=CF_TEX] and Unable to parse markup [type=CF_TEX] in the input.See my submission for an implementation.
•  » » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 thats what my above formula is but since n can be 10^18 what u did to avoid tle ?
•  » » » » » 7 месяцев назад, # ^ |   0 If you notice, the formula forms a linear recurrence — the one I mentioned at the end: Unable to parse markup [type=CF_TEX], where Unable to parse markup [type=CF_TEX] and Unable to parse markup [type=CF_TEX].Essentially, what we need to do is find the n'th term of this recurrence. Again, as you've noticed, doing this directly, even with memoization, is O(n). However, there is a way to find the n'th term of a linear recurrence in O(logn) by representing the recurrence in the form of a matrix, and then finding the n'th power of that matrix by square exponentiation (the same method you use to find Unable to parse markup [type=CF_TEX] in O(logn)).Here's a pretty simple tutorial, which explains the motivation fairly well: http://fusharblog.com/solving-linear-recurrence-for-programming-contest/.That optimization will let you solve the problem even for very large n — including 1018.
•  » » » » » » 7 месяцев назад, # ^ |   0 yes .. now i know that it will be solved using matrix exponentiation !! .. good question ~
•  » » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 Thank you. Well explained. see lokpati
•  » » 7 месяцев назад, # ^ |   +18 For explaining convenient, let's rotate the clock 90 degree clockwise. What we need to find now is the x coordinate of the minute hand.Represent the point P = (x, y) by a complex number Unable to parse markup [type=CF_TEX]. Notice that, when we multiply C by Unable to parse markup [type=CF_TEX], we rotated the point P by an angle Unable to parse markup [type=CF_TEX] around the origin, with Unable to parse markup [type=CF_TEX] (θ is the angle that the minute hand rotated each second). Why? Because in polar form, Unable to parse markup [type=CF_TEX]. So, if Unable to parse markup [type=CF_TEX] in polar form, then Unable to parse markup [type=CF_TEX].So, the answer we need to find is the real part of the complex Unable to parse markup [type=CF_TEX].To calculate this, represent complex number in form Unable to parse markup [type=CF_TEX]. Then, Unable to parse markup [type=CF_TEX]. So, what we need to calculate now is the real part of Unable to parse markup [type=CF_TEX], which can be done by fast exponentiation.
•  » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 very good idea ..
•  » » 7 месяцев назад, # ^ | ← Rev. 2 →   +5 The value for cos(theta) is given. Now we have to find cos(t*theta).We can do this using chebyshev polynomial of the first kind , since Tn(x) gives cos (n*theta), where x is cos(theta).The chebyshev equation is: Tn+1(x)=2x*Tn(x)+Tn-1(x).This can be solved by using matrix exponentiation in O(log(t))Link to my solution
•  » » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 @sdssudhu in ur solution how you dealt with fractional parts like when cos θ = 4/7 how u handled numerator and denominator seperately & have u caculated modinverse of L in the beginning? if yes , but in the question it was mentioned that after finding the final y coordinate and simplifying it to p/q , then you have to calculate mod inverse of q.
•  » » » » 7 месяцев назад, # ^ |   0 Yeah, for that you can use the matrix property and take the denominator constant out, for example if you have[2a/b,1,-1,0] , then you can have it as 1/b*[2a,b,-b,0]. Now you can multiply the matrix ^ t and then Divide by d^t using inverse modulo. Then you must multiply the answer by l, where l is the length of the clock. See my solution if you want to have a look at the implementation.
•  » » » » » 7 месяцев назад, # ^ | ← Rev. 3 →   0 okk.. went through ur solution .. very good approach .. now its clear to me . thanks !!