Livace's blog

By Livace, 3 months ago, ,

Hello, Codeforces!

Codeforces Round #483 will take place on May/15/2018 17:45 (Moscow time). The round will be rated for both divisions.

Problems were prepared by neckbosov, KAN and me.

Many thanks to testers qoo2p5, manoprenko, AlexFetisov, winger, cyand1317 and ashmelev.

Also thanks to MikeMirzayanov for Codeforces and Polygon and ifsmirnov for jngen.

Upd. The scoring distribution is 500-1000-1500-2000-2500 for div2 and 500-1000-1500- 2250 -2500 for div1.

Congratulations to the winners!

div1:

div2:

Editorial

•
• +203
•

 » 3 months ago, # |   +6 how many problems ?
•  » » 3 months ago, # ^ |   +42 5 for each division
 » 3 months ago, # | ← Rev. 2 →   +159 Judging from the name, it seems like a round in honor of people who donated some satisfying amount. Why are such special rounds not held on weekends so that as many people as possible could participate? Also maybe include some more information about the sponsors in the announcements.
 » 3 months ago, # |   +4 My rating is waving on the border of specialist and pupil these days. And bless everybody and me to get more rating in this contest.
 » 3 months ago, # |   +8 It is raining contests...!!!
 » 3 months ago, # |   -14 It will be very helpful if you please provide the scoring distribution for each problem.
 » 3 months ago, # |   +34 Don't worry that your division can change after ratings update after Codeforces Round #482 (Div. 2). I'll fix all the registrations to match your actual division.
 » 3 months ago, # |   0 Both divisions ? Now we have three in Codeforces ! Thanks Codeforces
•  » » 3 months ago, # ^ |   +7 But rounds are still div1 + div2
•  » » » 3 months ago, # ^ |   -54 Next rounds may be one day div1+div2+div3 as div3 is considered a division
 » 3 months ago, # |   +124 I believe if it is a thanks round, then the blog post should include some information and thanking for the supporters in this round. Otherwise it'll be no different from a normal round.
 » 3 months ago, # |   -19 Accidentally downvoted :(
•  » » 3 months ago, # ^ |   -96 Accidentally downvoted your comment :(
•  » » » 3 months ago, # ^ |   +79 Intentionally downvoted :)
•  » » » » 3 months ago, # ^ |   -6 downvoted to get attention ≧◡≦.
 » 3 months ago, # |   0 Contests everyday, thank you
 » 3 months ago, # |   +1 what does jngen mean???
•  » » 3 months ago, # ^ |   +28
 » 3 months ago, # |   +2 Contest of Div1 and ((div2 — div3) union div3) ) :P
 » 3 months ago, # |   -114 These guys will beat tourist :
•  » » 3 months ago, # ^ |   +24 who is the tourist?
•  » » » 3 months ago, # ^ |   -68 Dead SeriousWho are YOU?
•  » » » 3 months ago, # ^ |   0 i am fish
•  » » 3 months ago, # ^ |   +12
•  » » 3 months ago, # ^ |   0 hahahha...ofcourse
 » 3 months ago, # |   0 Hopefully, (Div. 2) Problems will be interesting like today's one.
•  » » 3 months ago, # ^ |   +3 I sure hope your wish won't turn out to be true. :/
 » 3 months ago, # |   +114 Wow, there are real jngen users :) I haven't promoted it for several months, so I'm very happy to see that sort of self-promotion exists.I would be glad if you could share the problems with me after the round. If I see how the community uses the library I can maybe improve the docs, give you some advice or see new development directions. My polygon login is the same as here.
 » 3 months ago, # |   +4 Wow, nice short description. Hope the description of the problems will be as short as the blog. :)
 » 3 months ago, # |   -8 My semester final exam start from today and I am waiting for Codeforces Round #483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!] :).
 » 3 months ago, # | ← Rev. 2 →   -36 My rating is below 2100 but I cannot register at the home page.Please fix the bug. MikeMirzayanov
•  » » 3 months ago, # ^ |   +31 If there is a div1 round, you only can participate in it. You are still a div1 contestant.
•  » » 3 months ago, # ^ |   +3 Candidate Masters are in Div 1 when both Div 1 and Div 2 round are scheduled at same time.
 » 3 months ago, # |   -7 Hopefully.Candidate master still participate in div 1 round.
 » 3 months ago, # | ← Rev. 4 →   +9 She: "What would you do alone at home?"Mobile chimes, " Codeforces Div ..."He: "I am not alone, anymore."
 » 3 months ago, # |   -37 you said the round rated for both divisionsis it rated for div3?or div3 is n't a division
•  » » 3 months ago, # ^ |   +135
 » 3 months ago, # |   -28 is it rated for DIV-3?
•  » » 3 months ago, # ^ |   +13 DIV-3 is a subdiv of div2, not an independent div.As it is rated for div2, it is rated for div3
•  » » » 3 months ago, # ^ |   0 So why do we call it div3?
 » 3 months ago, # |   +13 Q. Why did Scarlet witch fell in love with Vision?A. He was Red. :P
 » 3 months ago, # |   0 Good luck & hack for Both divisions
 » 3 months ago, # |   +13 10 min delay. why?
•  » » 3 months ago, # ^ |   +9 They did not give any reason in the past. So I do not think we can know the reason.
•  » » » 3 months ago, # ^ |   +38 You are SuperJava, however you code in C++.
•  » » » » 3 months ago, # ^ |   +2 C++ is faster.
•  » » » » 3 months ago, # ^ |   +2 Java is an island. An extremely verbose island.
•  » » » » 3 months ago, # ^ |   0 Because I used to use Java one year ago
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I think they wanted to wait for more participants. It's reaching 6k now. Apparently they've got ~100 more participants in the last 10 mins.
 » 3 months ago, # |   -49 The comment removed because of Codeforces rules violation
•  » » 3 months ago, # ^ |   0 What a baseless accusation.
 » 3 months ago, # | ← Rev. 2 →   -9 Problems difficulty is Unbalanced at all A and B**** are extremely easy compared to C and D
•  » » 3 months ago, # ^ | ← Rev. 2 →   -24 The comment removed because of Codeforces rules violation
•  » » » 3 months ago, # ^ |   -10 just searching the problem C and going to the top result leads to the answerwhy you copy the question from somewhere else and then remove the comments??
 » 3 months ago, # |   +8 No Hacks !!
 » 3 months ago, # |   0
 » 3 months ago, # |   0 The comment removed because of Codeforces rules violation
 » 3 months ago, # |   +21 I solved problem C without the condition of 4 guys in the elevator, and was thinking why I had got WA 4 during all contest.
 » 3 months ago, # | ← Rev. 3 →   +32 What's the point in making such a tough TL in div1A? Nice problems btw.
•  » » 3 months ago, # ^ |   +11 After finding g = gcd(q,b), If you divide q by g only once, it may reduces TL.(In TC 13)
•  » » » 3 months ago, # ^ |   +30 Furthermore, the next value of g will always be a divisor of the previous one. So you can initialise g = b and then do g = gcd(q, g).
 » 3 months ago, # |   +5 Is Div1 E just finding greedily till lca from both nodes and summing it??Also is Div1 B using SOS dp or something easy??
•  » » 3 months ago, # ^ |   0 I did simple interval dp with precalculating function on all intervals.
•  » » » 3 months ago, # ^ |   0 Dint precalc use SOS dp. ??
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +5 F[i][len] = F[i][len — 1] ^ F[i + 1][len — 1]dp[i][len] = max(f[i][len], dp[i][len — 1], dp[i + 1][len — 1])
•  » » » » » 3 months ago, # ^ |   +8 Thanks!! I dont know how to react to this to miss such a simple observation but find a very nice pattern...
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 Easy.dp[l][r] = max(dp[l][r-1], dp1[l, r]) wheredp1[l][r] = max(dp1[l+1][r], dp2[l, r]) wheredp2[l, r] = (dp2[l][r-1] ^ dp2[l+1][r])calc dp2 for all [l, r], then dp1, then dp.
•  » » 3 months ago, # ^ |   +8 Is Div1 E just finding greedily till lca from both nodes and summing it?? Almost. The way I see it, you should go greedily (precomputing jumps by 2^k buses up) and stop before reaching lca, then check if the two vertices you stopped at can be connected by 1 bus. That check seems harder to me, I solved it using offline+sweepline+segtree in or , but I'm sure there's a simpler solution.
•  » » » 3 months ago, # ^ |   +18 That check is equal to query "Is there any number from interval [tinx, toutx] in the subtree of vertex y?" so it can be done with simple merging of sets.
•  » » » » 3 months ago, # ^ |   +8 Ah, you mean numbering buses by one end vertex (with subtrees=intervals) and looking for them in subtrees by the other end vertex?My solution represents each "do we need 1 bus?" query by a rectangle formed by the intervals corresponding to the subtrees of its end vertices and each bus by a 2d point formed by the coordinates of its end vertices (both sorted to avoid casework). I avoid using a 2d interval tree by sorting and sweeplining by one coordinate, using an interval tree with operations "add/remove labeled interval" and "check off all intervals containing some point". In the end, I made it have amortised complexity per query, it's just more work and a clever structure.
•  » » » » » 3 months ago, # ^ |   +8 Ah, you mean numbering buses by one end vertex (with subtrees=intervals) and looking for them in subtrees by the other end vertex? Yes
•  » » 3 months ago, # ^ |   +8 I think you need to know whether you can "save one bus" because the stops from both subtrees are connected by the same bus.Since I'm not too sure how to phrase that properly, maybe I'll just highlight the problem by asking a simpler problem: Given 2 nodes, how do you know if they are connected by a bus (i.e. answer = 1 for that query)?
•  » » » 3 months ago, # ^ |   +3 Thanks. I get it .Will work on it!!
 » 3 months ago, # |   0 How to solve C?
•  » » 3 months ago, # ^ |   +1 is finite iff q contains only prime factors of b. So just divide q with the prime factors of b, and check if at the end whether q is 1 or not.
•  » » » 3 months ago, # ^ |   0 How did you find prime factors with such time constraints?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 You don't need to find prime factors, just divide by the gcd until they are relative prime.
•  » » » » » 3 months ago, # ^ |   0 Ok thanks got it
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 i exactly did that but i got TLE on test 13:(
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 set b = gcd(q,b) before iterating, it decreases the complexity of finding the gcd, cuz you don't care about the other factors.
•  » » » » » » 3 months ago, # ^ |   0 You have to divide q by g(g = gcd(b,q)) till q % g == 0. This statement cost me 6-7 WA. RIP rating
•  » » » » » 3 months ago, # ^ |   0 I solved C as your described, but i do not know why I got TLE in test11.
•  » » » » » » 3 months ago, # ^ |   0 I was getting it too, until i switched to fast IO.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 mraron, can u please, explain in detail? I knew that prime factors of q must be subset of b during contest. But seeing, constraint I couldn't figure out how to code i.e, prime factor for number till 10^18, would be TLE? Update : Leave it, understood :)
•  » » » 3 months ago, # ^ |   -8 What I was thinking was to convert q to base b and then check if the new q contains only powers of 2 or 5. Is this a correct approach?
•  » » » 3 months ago, # ^ |   0 I know the theory but I did not checked q is 1 or not
•  » » » 3 months ago, # ^ |   0 mraron p/q is finite iff each prime factor of q and b are equal OR each prime factor of q divides b???
•  » » » » 3 months ago, # ^ |   0 Check this out, for base 10, https://www.youtube.com/watch?v=rVhU8Vyhz7c
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 A rational number p / q has finite decimal representation in a base b iff there exists a positive integer n such that q|bn. From this we conclude that the set of divisors of q must be a subset of the divisors of b. I tried implementing this idea in PyPy but got TLE on pretest 9 (though asymptotically it should pass, guess the constant factor for PyPy is too large or my implementation was bad. :( )Edit: Reading mraron's reply above, I think that my implementation was bad, kind of overkill.
 » 3 months ago, # |   +11 Hack-Free contest !
•  » » 3 months ago, # ^ |   +3 I have seen someone had a successful hack. It was really unbelievable!
 » 3 months ago, # |   -8 why second pretest in B doesn't equal second example in task? wtf
 » 3 months ago, # | ← Rev. 2 →   0 I realized that the TITLE of the Problem Div2D,Div1B was such a huge hint, but it was too late. no time to debug.
 » 3 months ago, # |   -47 Problem Div.2 C What is the answer for : 1 1000000000000000000 999999999999999999 10the calculator shows : 1000000000000000000/999999999999999999 = 1.000000000000000001 which is finite
•  » » 3 months ago, # ^ |   0 Infinite
•  » » » 3 months ago, # ^ |   0 why is that ?
•  » » » » 3 months ago, # ^ |   +3 For it to be finite you should be able to multiply denominator into a power of 10
•  » » 3 months ago, # ^ |   +24 I'm sure your calculator would also show finite fraction for 1/3
•  » » 3 months ago, # ^ |   +3 The answer is infinite if q / gcd(p, q) has prime divisors which b doesn't have and finite otherwise. The problem is I couldn't realise it.
•  » » 3 months ago, # ^ |   +23 i don't think calculator can show infinite number of digits
•  » » » 3 months ago, # ^ |   0 Yeah I got it now.
•  » » 3 months ago, # ^ |   0 The answer for you case is "Infinite", you can learn some about precision of calculator.
•  » » 3 months ago, # ^ |   -19 You are right! Checker is wrong so contest needs to be unrated!!!
 » 3 months ago, # |   +32 Thanks Botan Investments for my decreased rating...
 » 3 months ago, # |   0 For div2d, I thought of some kinda O(N^N) preprocessing but I had no clue how to calculate f() efficiently.. What is the idea behind this problem ?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 Look at the title of that problem. There's a huge hint.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 If len = ar - al thenf(al, ..., ar - 1) = f(al, ..., al + len - 2k - 1) xor f(ar, ..., ar + len - 2k - 1), where 2k is the maximum power of two that less than len
•  » » » 3 months ago, # ^ |   0 Sorry, I can't understand why that works. How to prove that?
•  » » » » 3 months ago, # ^ |   0 Write a program that simulates the function f.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 First, Calculate the 2d dp:A[j][i+j] = A[j][i+j-1]^A[j+1][i+j]then calc max as:M[l][r] = max(A[l][r], max(M[j][i+j-1], M[j+1][i+j]))then the query will be O(1)
 » 3 months ago, # | ← Rev. 2 →   -8 how can we solve problem D , i know we need to find max xor pair in given range , but how to optimise it from o(n^2) ?
•  » » 3 months ago, # ^ |   0 Using 2d segment-tree would be enough, I think.
•  » » » 3 months ago, # ^ |   0 ((r-l)log (r-l) for each query ?
•  » » » » 3 months ago, # ^ |   0 NVM. my approach was wrong. it was a simple pyramid-dp problem like answered below.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 build a table : d[n][n] where d[0] = a, d[i][j] = d[i-1][j] xor d[i-1][j+1]precompute mx[n][n], where mx[0] = d[0], mx[i][j] = max(d[i][j], mx[i-1][j], mx[i-1][j+1])answer queries mx[l-r][r]
•  » » » 3 months ago, # ^ |   0 thanks
•  » » » 3 months ago, # ^ |   +3 I think it should be: precompute, mx[n][n], where mx[0] = d[0], mx[i][j] = max(d[i][j], mx[i-1][j], mx[i-1][j+1])Correct me if I am wrong.
•  » » » » 3 months ago, # ^ |   0 my mistake, sorry
 » 3 months ago, # |   +6 To be honest, I must appreciate how setters choose cases for pretests in this one — really careful and cover nearly everything one can slip into. Cheers. ;)
 » 3 months ago, # |   +35 too tight time limit on Div.2 C....
 » 3 months ago, # |   +158 Anybody else wants to complain against time limit of div1 A?
•  » » 3 months ago, # ^ |   +38 me, i even made a comment in russian
•  » » 3 months ago, # ^ |   +26 It depends on what is an intended complexity. Firstly I did something like log times gcd per testcase (which is O(log^2)) and it turned out to exceed TL. Then I did some optimization which looks silly, but I think it may actually improve complexity and passed in TL/3. However this task is actually doable in O(log(log(b + q)) per testcase, because it suffices to check if q|b64 which can be done with 6 multiplications if we have big integers or __int128_t that Codeforces doesn't have (taking mod q after each step of course).
•  » » » 3 months ago, # ^ |   +12 I tried bigint solution with python, and got TLE..
•  » » » 3 months ago, # ^ |   +8 I have log times gcd and it got AC. On the other hand, the numbers I'm computing gcd from decrease very quickly — it's "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible".
•  » » » » 3 months ago, # ^ |   +21 That's what I did in the end as well. I mean you and I both finally have "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", but in the beginning I had "while Q > 1 compute gcd(B, Q), divide Q by it" without "as many times as possible". I am not sure what is the worst case complexity of this solution, but after some thought I got an impression it is really useful and it is not as silly as it looks.
•  » » » » » 3 months ago, # ^ |   0 For having "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", it may takes even longer time in worst case. An example is q = 260, b = 231 then gcd(q, b) = 231 but we can divide it only once. However to check whether dividing it one more time is possible, we have to compute a division to check its remainder. (That cause extra time)
•  » » » » » » 3 months ago, # ^ |   0 Yes, in some cases it may be worse but thats not a worst case. In your example in next iteration we will have gcd=2^29 and divide everything, so there is only 2 computations of gcd(which also has divisions btw). If you divide by gcd once you have up to 60 iterations of gcd (which gives per test comlexity. If you divide while you can, it's no more then sqrt(60) iterations of gcd, which gives you (and comment shows that complexity may be shown to be
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I'm pretty sure this is asymptotically faster. It's no more that O(sqrt(log()) iterations of gcd because you divide by numbers with different number of primes each time(and may be it's even faster)
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +18 If you do that + making B = gcd(B, Q) after not being able to divide makes the complexity O(log) amortized. This works because for each 2 iterations of Euclid's algorithm, one number is at least half of before and you use that number for the next iterations so the maximum number of iterations is O(log). Other than that, the number will obviously be divided at most O(log) times. Did I miss something?Edit: also, for your optimization my friend's reasoning applies. There will be 1 prime that will get below the exponent of B in one while iteration and it will disappear in the next one. So you get rid of at least one prime for each 2 iterations.
•  » » » 3 months ago, # ^ |   0 Thanks AlexDmitriev for this comment, he is right, this solution works O(nlog1.5M). Optimization is same as "divide as we can", but works faster because numbers are smaller. But I think that it doesn't make less complexity. Editoral will be updated.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 It actually does make the complexity O(logM) per case. Maybe I wasn't clear on the comment above. If you call gcd(q, b) for each 2 iterations b will be at least half so the sum of iterations until b is 1 is O(logb) (amortized).By iteration I mean iterations inside gcd
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 Sorry, it's not clear to me why the complexity is O(log M) per case. If you have log(N) + log(N/2) + log(N/4) + log(N/8)..., that's still log(N)^2 time, no? Since it's log(N) + (log(N)-1) + (log(N)-2)... complexity.Seems to me like the real complexity is still . Since the worst case involves all the primes having different exponents, we can divide by more than half each time, we can divide by 2i for each iteration. So, our computation is log(N) + log(N/2) + log(N/2^3) + log(N/2^7)..., or log(N) + (log(N) -1) + (log(N) - 3) + (log(N) - 6) ....So, the number of log(N) operations we have to do is based off of how fast 1,3,6... reaches log(N). As that's just simply the triangle numbers, there's terms.
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +10 If you had one gcd take x iterations then B will be <= B / 2^(x/2). So the complexity isn't log(N) + log(N/2) + log(N/4) + log(N/8)... and the sum of steps will be <= 2 * log(B).So if a gcd computation takes indeed log(B) or a big number of steps, the number will be much lower than B and the maximum number of iterations for the rest will be lowered. This is amortized analysis, not every gcd will be worst case. Also as you get closer to worst case for gcd, worst case implies that gcd is 1 and you don't need to continue so more iterations == B is much lower.
•  » » » » » 3 months ago, # ^ |   +8 If I'm not mistaken the following simpler code works in : b = gcd(q, b); while (b > 1) { q /= b; b = gcd(q, b); } return q; Suppose that the loop has several iterations, and the value of variable b in the i-th iteration is bi. Time complexity of the i-th invocation of Euclid's algorithm is . So the total complexity of the loop is , since for some Q.
 » 3 months ago, # | ← Rev. 2 →   +16 solution for Div2. C (Div1. A):https://math.stackexchange.com/questions/310402/proving-finite-vs-infinite-representation-of-p-q-in-base-b(i think now there is no violation with codeforces stupid rules)
•  » » 3 months ago, # ^ |   -8 they didnt even change the p,q,b!!!
•  » » » 3 months ago, # ^ |   -11 well if you know the solution. why you couldn't get accepted verdict? they have tighten the time limit so you must try different approach.
•  » » » » 3 months ago, # ^ |   -11 i tried 19 different approaches!and now when i see others approaches some of them are same whit me and the only difference is that they print the answers immediately but i print all answers after calculating all of them
•  » » » 3 months ago, # ^ |   +40 A very high chance that it's just a coincedence. Integer fraction is very often (almost always) presents as p/q and base is ussualy presents as 'b'.
•  » » » » 3 months ago, # ^ |   -11
 » 3 months ago, # |   +3 An interesting game
 » 3 months ago, # |   +21 problem C looks trivial. Does this dp works? dp[i][pos][x1][x2][x3][x4]=minimum cost if the first i people already entered in the elevator, currently we are at floor pos, and the elevator contains people that wants to go to floors x1,x2,x3,x4.
•  » » 3 months ago, # ^ |   0 Yes, i think. but you should consider memory limit in that problem.
•  » » » 3 months ago, # ^ |   +5 well, we only need the last two rows so i={0,1}
•  » » 3 months ago, # ^ | ← Rev. 2 →   +24 You can reduce the complexity and memory space only considering the ordered multisets of (x1, x2, x3, x4). There is only 715 such multisets. Also looked trivial for me, just a careful implementation was needed.
 » 3 months ago, # |   +35 This is the first round when I solved div1 E. I solved div2 E for the first time when Livace was the problem setter too (Codeforces Round #442).
•  » » 3 months ago, # ^ |   +16 Perhaps you should plan to meet him in person?I don't think it's just notorious coincidence ;)
 » 3 months ago, # |   0 in problem (B. Minesweeper) 1 1 * how test like this can be valid ????
•  » » 3 months ago, # ^ |   0 It satisfied all constraints.There is only one cell with a mine. No cells left un-mined, so no numbers could be found.
•  » » 3 months ago, # ^ |   0 The one cell satisfies both criteria given in the problem statement: there is not a digit in the cell, so you don't check for the count of bombs in neighboring cells; the cell is not empty, so you don't check for neighboring cells having bombs. :)
•  » » » 3 months ago, # ^ |   0 there is a bomb with no number point to it !! this is a violation for the game rule ??
•  » » » » 3 months ago, # ^ |   0 Indeed, in the real game it would not make much sense. But if you just abide by the problem statement it does. In my case, I didn't think about this apparent inconsistency because I never played that game :)
 » 3 months ago, # | ← Rev. 3 →   0 During the contest I wanted to hack leon_ldy's solution(38273146).I had 2 unsuccessful submissions in this problem and after my second submission I noticed in pretests 8 , n=1.but why his submission passed pretest? this is his code: #include #include using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 1010; int a[MAXN]; int main() { #ifdef LOCAL //freopen("C:/input.txt", "r", stdin); #endif int n; cin >> n; for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); int j = n - 1, k = 0; while (true) { j--; if (j == k) break; k++; if (j == k) break; } cout << a[j] << endl; return 0; } but when n=1 so j=0. and in the "while (true)" we had TLE. because at first "j--" and after that j=-1. so always j!=k.
 » 3 months ago, # |   +78
 » 3 months ago, # |   +22 C+E = (Code*Code*Code+Code^2)^Code
•  » » 3 months ago, # ^ |   +19 What's wrong with C? Seems fine to me.
•  » » » 3 months ago, # ^ |   +28 That it is obvious to come up with a solution and nontrivial how to properly code it. It is a programming task, not an algorithmic one. Some people would say that it is ok, but I think that it is also ok to say it is not an interesting problem.
•  » » » » 3 months ago, # ^ |   +8 OK, I see what you mean (but I still think that it's pretty easy to code)
•  » » » » » 3 months ago, # ^ |   +29 It seems that whenever contest goes well for me I think tasks were fine and when it doesn't I always declare tasks as programming and noninteresting ones :P.
 » 3 months ago, # |   0 For C I check whether the divisors of q are a subset of the divisors of b with gcd but still get TLE on 13.
•  » » 3 months ago, # ^ |   0 It is because of slow input
•  » » » 3 months ago, # ^ |   0 I used fast input for java but it may be bcause I used slow output xD
 » 3 months ago, # |   +8 Any ideas for D?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +11 Probably, it's wrong
•  » » » 3 months ago, # ^ |   +13 Do you know any good tutorials for kd-tree?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +5 Unfortunately, I haven't seen.For D I followed this easy-to-implement solution(actually, it's not classical KD-tree, it's more likely as joined KD-tree and Segment tree, just intersecting rectangles instead of segments) Probably, the author forgot about inclusion/exclusion case with boundary points in some quadrant.
•  » » 3 months ago, # ^ |   +8 Author's solution is scanline + segment tree with sets in vertices.
 » 3 months ago, # | ← Rev. 3 →   +9 def gcd(x, y): while(y): x, y = y, x % y return x a=input() while(a>0): a-=1 p,q,b=map(int,raw_input().split()) r=gcd(p,q) q=q/r r=gcd(q,b) while(q!=1 and r!=1): while(q%r==0): q=q/r r=gcd(q,b) if(q==1): print"Finite" else: print"Infinite" even after writing exactly the same code as it is being discussed in the comment section, my solution failed. Time limit for python is too strict. i got tle in 11. Please verify if there is a mistake on my side or this happened because of the language selected. Thanks :)
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 my English is poor,emmmm, while(q!=1 and r!=1): q=q/r while(q%r==0): q=q/r r=gcd(q,b) ~~~~~ while(q!=1 and r!=1): q=q/r while(q%r==0): q=q/r r=gcd(q,r)
•  » » » 3 months ago, # ^ |   0 it means while q not equal to 1 || r not equal to 1
•  » » » » 3 months ago, # ^ |   0 i know , it is the first time for me to reply you can look the code i changed.
•  » » » » » 3 months ago, # ^ |   0 I even tried this in my submission but even that failed pretest 11
•  » » » » » » 3 months ago, # ^ |   0 oh i know ,and you should know if p == 0 output Finite change like that ~~~~~ while(q!=1 and r!=1): q=q/r r=gcd(q,r) ~~~~~
•  » » » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 ohh shoot I think I got my mistake i thought all were having constraints >=1 Thanks a lot mate
•  » » » » » » » » 3 months ago, # ^ |   0 it dosent matter whether p==0 or not as when p==0 gcd(p,q)=q and q/q=1 and so ans would be finite it is definitely fault of strict time limit
•  » » 3 months ago, # ^ |   0 The language selected is the mistake on your side.
•  » » » 3 months ago, # ^ |   0 I know. I think its time to switch to c++
•  » » » » 3 months ago, # ^ |   +15 It can be solved with python although. Not recommended. http://codeforces.com/contest/983/submission/38299853
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 but isn't this method just a fluke way which has no guarantee always. can't the original solution with any optimization pass in python
•  » » » » » » 3 months ago, # ^ |   0 yes, it's better to use C++/Java for the contests. Some problems just can't be solved in python under given time limits.
 » 3 months ago, # |   +2 Is the time limit for python and c++ same every time for every question???
•  » » 3 months ago, # ^ |   0 Pretty sure it is. Python needs more love!
•  » » 3 months ago, # ^ | ← Rev. 4 →   +3 no I guess its 5x for python but at times even that is slow it makes the competition more fair if the setter/tester try it in python as even python is being used a lot as compared to c++ and java
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 no I guess its 5x for python Where did you hear of this? All I see is there is only a single time limit for each problem, e.g. it's 1 sec for Div2 C
•  » » » » 3 months ago, # ^ |   0 python has a time of 5x likewise java has 2x. this time is allocated according to the processing time of the language. as python is a slower language than c++ it gets 5x time. But this dosent mean python has more advantage.
•  » » » » » 3 months ago, # ^ |   0 You aren't answering my question though, are you sure you are not just making this up?
•  » » » » » » 3 months ago, # ^ |   0 no I am sure as on various platforms like codechef and hackerearth this rule follows
 » 3 months ago, # | ← Rev. 2 →   0 For Div2D , if (r-l+1) is power of 2 then we can take all elements from l to r.If I am right then please someone say the answer of this input and how ?241 2 128 256 512 1024 2048 4 8 16 32 64 1 2 128 256 512 1024 2048 4 8 16 32 64 15 20
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 The answer is 4035. For simplicity, that input is the same as16512 1024 2048 4 8 16 32 64 1 2 128 256 512 1024 2048 411 16While you can take all elements from 1 to 16 (f(array), if array's size is a power of 2, is indeed the xor of all elements), the statement asks for the biggest value of f considering all continuous subsegments of the subarray v[l...r]. The xor of all elements in this input is 507, however you can take f(v[7...14], 0-indexed) which gives 4035.
•  » » » 3 months ago, # ^ |   0 OMG, I did bitwise OR rather than XOR ( typo ).
 » 3 months ago, # |   +5 During the contest I had the following problem. In my template I have a few pragmas that should optimize operations and make Codeforces submissions faster (they’re pretty common to include nowadays). However, for today’s problem E, something weird happened. The solution with these pragmas got RE verdict on pretest 1, while the solution without them got accepted. I assure you the only difference between the two sources is in the pragma macros. Have you ever experienced something like this? What pragma do you think is broken, in this sense?
•  » » 3 months ago, # ^ |   -8 Leaving my comment, cuz I am curious as well and I wanna be notified :D
•  » » 3 months ago, # ^ |   0 I tested on custom invocation and put the bits/stdc++ line before the pragmas and oddly it worked. I have no idea why
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 Third pragma. The problem may appear in situation, when CF uses different machines with a different architecture to compile and run code. It's common problem on Yandex Contest system. I use following pragma for it: #pragma GCC target("sse,sse2,sse3,ssse3,sse4") 
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +1 So, is it only the tune=native setting I shpuld remove or all the rest of them?Also, I can’t test myself right now, have you tried running it without tune=native and seen it work?Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.
•  » » » » 3 months ago, # ^ |   0 Ok, I tested. In your case it's "abm" setting. Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times. Actually, It depends not on platform, but on problem and on your code. That is, if the bottleneck of your solution can be vectorized, then the pragma will help. Otherwise, the optimizer can apply vectorization where it is not needed, and your solution will slow down.
•  » » » » » 3 months ago, # ^ |   +1 I agree with that. However, I’ve seen consistently better results overall on Codeforces, while I’ve never seen improvements on Yandex (Opencup for example). I think it depends on the architecture and the compiler as well. I’m not pretending to know anything here, but my guess is that the running on Windows the pragmas will have a bigger positive impact than on Linux. Have you ever had noticeable changes using these pragmas on Yandex? (compared to not using them, obviously)
•  » » » » » » 3 months ago, # ^ |   0 There were some problems from SNWS contests, PTZ and MIPT camps, that I solved with not optimal complexity, and I'm pretty sure that pragmas helped in that solutions.
•  » » » » 3 months ago, # ^ |   +24 abm changed the implementation of std::__lg, which is later called by std::sort. Here's a simple example of it being unstable, even on other platforms: #pragma GCC optimize("Ofast") #pragma GCC target("abm") #include using namespace std; int main() { cout << __lg(1) << endl; volatile int i = 1; do { cout << __lg(i) << endl; ++i; } while (i <= 1); } Output: 0 31 with abmwithout abm
•  » » » » 3 months ago, # ^ |   +11 Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times. Lol, I added the Ofast pragma to my code for E and it slowed down by ~50%.On the other hand, one secondary school student in our IOI selection used # pragma GCC optimize ("O3") # pragma GCC optimize ("Ofast") # pragma GCC optimize ("unroll-loops") to almost solve a problem with bruteforce.
 » 3 months ago, # |   0 The time limitation on Div2C is too tight.... just reassigning gcd value made it passed.. -_-
 » 3 months ago, # |   0 Systests for div1B are weak, i see some O(q*n) solutions accepted
 » 3 months ago, # |   0 Can anyone explain why first gives TLE and the other one AC 38300452 and 38300601
•  » » 3 months ago, # ^ |   0 Got it.
•  » » 3 months ago, # ^ |   0 Because cin/cout is much slower than scanf/printf. So, don't use cin/cout to solve big I/O problems.
•  » » 3 months ago, # ^ |   0 you can just write first line from int main(): ios::sync_with_stdio(false); and this will give you a boost
•  » » » 3 months ago, # ^ |   0 Really bad from my side . Had I written it it would have been AC :(
 » 3 months ago, # |   0 When are we going to get the tutorial?
 » 3 months ago, # |   +182 So, did noone notice this: 1 2?
•  » » 3 months ago, # ^ |   -29 WHAT THE FUCK! this two codes are perfectly matched and CF didn't notice?
•  » » 3 months ago, # ^ |   +8
•  » » 3 months ago, # ^ |   +28 As far as we know, the problem coincided with a problem from some Chinese online judge :(. So we think these submissions are fair.
•  » » » 3 months ago, # ^ |   0 https://blog.csdn.net/wmdcstdio/article/details/44596291Actually is this problem from a Chinese National Training Team contest back in 2011.
 » 3 months ago, # |   0 can someone explain why the first query of the second test case of Div.2-D is 60 instead of 63? shouldn't it be 1 ^ 2 ^ 4 ^ 8 ^ 16 ^ 32?
•  » » 3 months ago, # ^ |   +1 You misunderstood how f function works. Acturally, the answer for f(1,2,4,8,16,32) = 51. You may implement it yourself. :)
•  » » » 3 months ago, # ^ |   0 Yes, I realize now. Thanks!
 » 3 months ago, # |   +6 Pretests for B were pretty weak. In my solution I put a "n" instead of "m" in the second loop when I wanted to traverse my matrix. Apparently that was enough to pass the pretests. I noticed that error only after the system tests.Then I changed "n" for "m" and got AC. Sad day for me :( .
•  » » 3 months ago, # ^ |   0 weak pretests are needed for hacking:)
•  » » » 3 months ago, # ^ |   +8 Hacking is needed for weak pretest (not the opposite)
 » 3 months ago, # |   +14 Q. When does one grow up? A. When one reads more comments on CF than FB.
 » 3 months ago, # |   0 In div2 problem C For values of p,q,b=(10,5,3) in TC#3 how the answer is finite
•  » » 3 months ago, # ^ |   0 10 / 5 = 2 in base 10 which is 2 in base 3. This does not have a non terminating decimal part(rather does not have any digit after decimal point)I guess you are confusing with the case (p,q,b) = (5, 10, 3). In which case it would be non terminating and hence infinite in problem's context.So you only need to take into consideration the prime factors of denominator and base since for improper fraction a/b you can always write it as [a/b] (greatest integer function) + {a / b} (fractional part) where the former will always be translatable to different bases without recurring decimals . Refer editorial for more insights.
•  » » » 3 months ago, # ^ |   0 Well if we convert both numerator and denominator firsthand to base 3 i.e. 10 in base 3 would be 101 and 5 in base 3 would be 12, so 101/12 will be infinite. I am confused here.
•  » » » » 3 months ago, # ^ |   0 Yes it is correct to say that but notice that since you convert numbers to base 3, conventional division(in base 10) does not work.You can still observe that base3(12) * base3(2) = base3(101). Hence we don't have a recurring decimal. An easier way to do the this is the same as mentioned in samples in the question .
•  » » » » » 3 months ago, # ^ |   0 I got it. I misunderstood the notes of the problem given in the contest. Thanks alot. :D
 » 3 months ago, # |   0 I was trying to solve Div1E with O(n * sqrt(n)) complexity, sqrt(n) jumps instead of binary lifting. When I debugging I changed my sqrt variable to 1. And it got accepted. 38320734It simply tries to jump lca and stop when there's a route from this node to lca. And same thing for second node, also check for ans - 1, no different solution. You can check my code and see that for every query I'm calculating the answer with increasing res one by one. while(!inside(c, go[x])) { if(go[x] == x) { res = -1; break; } res++; x = go[x]; } And sad part is I have no clue how good my O(n * sqrt(n)) solution is. It actually got slower time :(
 » 3 months ago, # | ← Rev. 2 →   0 My solution was missjudged in contest. Please kindly look into it.Detailed post: http://codeforces.com/blog/entry/59503Submission on contest: 38291441Same solution accepted: 38328663Thank you.