By MikeMirzayanov, 3 years ago, translation, ,

Hello, Codeforces!

I'd like to invite you to join in Playrix Codescapes Cup for the both divisions that will be held on May 11 at 18:35 MSK. The round is rated and open for everyone.

Problems are prepared by KAN, Al.Cash, MikeMirzayanov and fcspartakm. Huge thanks to Playrix company for making this round possible. Hope you enjoy the round!

Playrix is one of the leading mobile games development companies in the world. Its distributed team consists of 450 professionals from around the world. The company has released three successful mobile free-to-play games – Township, Fishdom and Gardenscapes. All of the projects have consistently been among the Top 50 Grossing Apps for iOS and Google Play since their release.In 2016, Facebook named Gardenscapes game of the year.

Company is looking for Russian-speaking C++ developers.

Prizes from the Playrix company:

• Top 1: iPadPro 9,7 + PowerBank + T-shirt with logo
• Top 2-5: PowerBank + T-shirt with logo
• Top 6-50: T-shirt with logo
• (New!) Random 5 participants (not from top-50, submitted at least once): T-shirt with logo

Congratulations to the winners!

The problem analysis is published.

• +464

 » 3 years ago, # |   +49 why all of the jobs in codeforces are for Russian-speaking contestants?
•  » » 3 years ago, # ^ |   +91 I think it's a matter of the companies which hold contests on CF , not CF itself.
 » 3 years ago, # |   +16 Register again. Previous registration has been cancelled.
 » 3 years ago, # |   +50 How many problems?
 » 3 years ago, # | ← Rev. 2 →   -74 Tourist winning another round ? Hope he participates.
•  » » 3 years ago, # ^ |   -8 return true;
•  » » » 3 years ago, # ^ |   -26 On the face of haters :P
•  » » 3 years ago, # ^ |   0 why so much hate on this comment lol..everyone knows he will win, and I guess everyone loves tourist — the beast
•  » » » 3 years ago, # ^ |   -15 Maybe some are jealous... :P
 » 3 years ago, # |   0 Wow very awesome!!
 » 3 years ago, # |   +106 tourist will complete his set of apple products.
•  » » 3 years ago, # ^ |   -39 We have much confidence on him !
•  » » 3 years ago, # ^ |   +140 Maybe "multiset" XD
 » 3 years ago, # | ← Rev. 2 →   +49 Posted time: 15:35 UTCActual time: probably 15:45 UTC
•  » » 3 years ago, # ^ |   +13 Yes, because they reset the registration.
 » 3 years ago, # | ← Rev. 2 →   +26 Hi, everybody.The offer to organizers from the company PlayrixConsidering that the Playrix is engaged in development of games, I would advise to bring some spirit of surprise in a contest :) For example, to add 3-5 small prizes (or T-shirts) which by a randomly method will get to participants outside the first hundred, and maybe the first thousand. It would stimulate attraction to a contest of players.
•  » » 3 years ago, # ^ |   +14 would be fantastic, no newbies got a tshirt before.
•  » » 3 years ago, # ^ |   0 Although I totally love the idea and also love to get a T-shirt, but I think keeping it for the first 50 is better. To encourage low-rate participants to do better and EARN the T-shirt.
•  » » » 3 years ago, # ^ |   +2 I don't urge to take away t-shirts at TOP-50 participants. ))) I suggest to give IN ADDITION 3-5 t-shirts for participants from the first thousand
•  » » 3 years ago, # ^ |   +84 Great idea, thanks! Playrix will give 5 additional prizes to random participants not included in the top 50. I hope CF will help us with fair random algorithms )Best Regards, Trushkov Aleksey Playrix
•  » » » 3 years ago, # ^ |   -11 Thank you for understanding. P.S. Понадобятся идеи, обращайтесь, на кетайщине их хватает ))
 » 3 years ago, # | ← Rev. 2 →   0 It would be great if you will announce such events more than a day before. Thanks.
 » 3 years ago, # | ← Rev. 2 →   -14 Problem prepared by MikeMirzayanov! I'm not gonna miss it.
 » 3 years ago, # |   +32 I predict there will be an obscure Geometry problem.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +31 Given that Playrix is a games development company?
•  » » » 3 years ago, # ^ |   -7 Playrix is one of the leading mobile games development companies in the world.
 » 3 years ago, # |   +135 T-shirt on girl is really great :D
•  » » 3 years ago, # ^ |   -18 What's her name :D ?
•  » » 3 years ago, # ^ |   +149 and a very long right hand
 » 3 years ago, # |   +12 I hope there won't be delay before the contest.
•  » » 3 years ago, # ^ |   0 Me too XD
 » 3 years ago, # |   0 T-Shirt <3
 » 3 years ago, # |   +32 Dafuq happened to the right hand of the t-shirt girl?..look at those veins :O
 » 3 years ago, # |   -13 http://codeforces.com/blog/entry/51926 Help please
 » 3 years ago, # |   +2 Hope it's easy to understand all the problems, And all participants will enjoy the contest. :)
 » 3 years ago, # |   +4 The T-Shirt Looks Nice
 » 3 years ago, # |   +8 How does back of white T-shirt look?
 » 3 years ago, # |   +62 Extensions: Have fun & high rating:)PS One guy wrote to me that he couldn't install extension. Does anybody else has the same problem?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I have same problem :("An error has occurred There was a problem adding the item to Chrome. Please refresh the page and try again."
•  » » » 3 years ago, # ^ |   +5 I think I got this message when I had slow internet speed
 » 3 years ago, # |   +4 how many problems???
 » 3 years ago, # |   0 T-shirts very well
 » 3 years ago, # |   +7 Is my luck so poor? I never get a random prize.
•  » » 3 years ago, # ^ |   +8 Well considering that 4500 ppl will participate in this round 50 for them will get prizes for sure that leaves 4450 the probability that one will get a prize is 0.0011235955.Your luck is not poor it's just math.:)PS: if you work hard enough you won't need luck cause your probability will be 1.
•  » » » 3 years ago, # ^ |   +6 Actually, assuming 4500 people submit at least once, the probability that you win one of the 5 random T-Shirts is 0.003366496682134068.
•  » » » 3 years ago, # ^ |   +32 Still got a higher chance than finding our soulmate
•  » » 3 years ago, # ^ |   +2 I wonder if the T-shirts in this contest will be distributed based on an adaption of the formula from the problem in the previous contest 807B - T-Shirt Hunt ...
 » 3 years ago, # |   +5 i think that it will be a little bit tricky one and challenging too.....
 » 3 years ago, # |   +13 What about scoring distribution?
 » 3 years ago, # |   +6 The '#' took the perfect place in the picture.
 » 3 years ago, # |   +8 Expecting a 10 minute delay. xD
 » 3 years ago, # |   0 How many problems? What's the scoring distribution?
•  » » 3 years ago, # ^ |   0 5 minutes before the contest: we're still waiting for more info
 » 3 years ago, # |   0 tourist registered. maybe he is going to be champion
 » 3 years ago, # | ← Rev. 4 →   +8 Look at girl's right hand. What is that monster dude...?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 photoshopFAIL
 » 3 years ago, # |   -11 wow.. no delays .. so unusual ..
 » 3 years ago, # |   +7 hope to be in random 5 !!!
 » 3 years ago, # |   +8 mikemirzayanov please give tourist a new color :O
•  » » 3 years ago, # ^ |   0 can't agree more :) Or just a choice of any color he wishes
 » 3 years ago, # |   +288
•  » » 3 years ago, # ^ |   +84 Did you spend the last ten minutes of the contest making this meme?
•  » » » 3 years ago, # ^ |   +191 yes
•  » » » » 3 years ago, # ^ |   +20 you make my day))
•  » » 3 years ago, # ^ |   -8 You know what, the same thing came to my mind :P
•  » » 3 years ago, # ^ |   +32
 » 3 years ago, # |   +5 how to solve D?
•  » » 3 years ago, # ^ |   0 Dp[h][w] in map
•  » » » 3 years ago, # ^ |   0 But how do you know which extinction you used and which one you didn't ?
•  » » » » 3 years ago, # ^ |   0 dp[h][w*a[i]]=dp[h][w] dp[h*a[i]][w]=dp[h][w] for all i:=0 to n-1
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +4 I'm so dumb.Sorry.Hope you pass systest.:)
•  » » » » » » 3 years ago, # ^ |   0 thanks, you too)
•  » » » » » » 3 years ago, # ^ |   -6 It's fail! TL!
•  » » » » » » » 3 years ago, # ^ |   +9 I'm so sorry...Don't worry you'll get them next time.:)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +7 Notice that for ai >= 3, you will need maximum of 11 items to increase alength from 1 to over 10**5. So you can brute over min(22, n) largest items to divide them into either Length/width. Incase the length is still less, then find how many no of 2's will satisfy Maintain a count of actual length increments done and find the minimum answer.Complexity: O(2**22 * 20)I thought this should pass. But this was very close to tle. 940ms first time for me. But after doing some bad optimizations, it passes pretest ins 499ms. (I lost around 400 points on this :|)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 If reverse sorted a[] is like five 6, five 5, five 4, five 3, five 2, you can brute over x '6' to width and 5-x '6' to height. And so on for the rest of the unique values in a[]. I think a binary search is required at the lowest level as you may not need all of 5-x 'smallest-digit'. And we must also consider inverted the rectangle by 90degree. The max time this will take is 2*( 2^(2*10 + 2*log11) ).
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 if you sort in non-increasing order, you should not to skip some extension, answer is some prefix, so you can use dp[idx][pair(curW, curH)] with map 27034588
•  » » » 3 years ago, # ^ |   0 It is also possible to memoize only one of the parameters (h or w). The other one may be derived from the current index of the dp if you precompute the prefix product of the sequence.
•  » » » 3 years ago, # ^ |   +5 what is the time complexity of this approach? how many elements in the worst case will be added to the map?
•  » » » » 3 years ago, # ^ |   0 In my solution , it's O(max(a,b)) — since there are sqrt(x) different x/y numbers for y belongs to integers. so sqrt(x)*sqrt(x) for the pair = O(x) = O(max(a,b)).
 » 3 years ago, # | ← Rev. 2 →   +13 Congrats tourist , i was spectating whole round lol
 » 3 years ago, # |   +1 How to solve C?
•  » » 3 years ago, # ^ |   +4 Taking fountain with diamond + coin is easy. Then use two pointers\bin search for coin + coin, diamond + diamond pair.
•  » » » 3 years ago, # ^ |   +12 Then use two pointers\bin search for coin + coin, diamond + diamond pair. Could you, please, explain how to do that? It looks like a knapsack for me.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 When we buy fountain for x coins, we still have c — x coins. So you can sort and find max prefix that you can buy with c — x coins, and find max beauty in that prefix with prefix maximums.
•  » » » » » 3 years ago, # ^ |   0 I think that with this approach we can choose one fountain twice.
•  » » » » » » 3 years ago, # ^ |   +1 Nope, we just limit our prefix by i — 1.
•  » » » » » » » 3 years ago, # ^ |   0 Yeah, really, I didn't think about that, thank you!
•  » » » » » » 3 years ago, # ^ |   0 not if you binary search corectly. you should make hi=i-1 and it is imposible to take fountain i twice
•  » » » » » 3 years ago, # ^ |   0 I described that in my comment below.
•  » » » » » 3 years ago, # ^ |   0 Could you share your code?
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Here (might fail because of bugs)(don't look at the segtree, I haven't used it).
•  » » » » » » » 3 years ago, # ^ |   0 My solution is failing on test 4 . How to handle it ?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 well,you have 2 cases:you take two of the same type(2 coins or 2 diamonds) or you take one fountain with diamonds and one with coins.1 diamond+1coin: you take the most beautifull fountain you can afford for each type2 diamonds/coins: you take fountain i,and search for another fountain j,such that their beauty is maximal for i,and their cost is small enough
•  » » » » » 3 years ago, # ^ |   +1 such that their beauty is maximal for i,and their cost is small enough I don't understand how to do that.
•  » » » » » » 3 years ago, # ^ |   0 you select a fountain i,and say "ok,i would like to buy this fountain and another one of the same type,but i would like to take the most beautifull one i can afford". so beauty[i]+beauty[j] is maximal,and cost[i]+cost[j]<=C(or D,depends on case)and res will be max of all this cases and case 1(1 diamond+1 coin)
•  » » » » » » » 3 years ago, # ^ |   +1 We do O(n) steps to choose fountain i. For each of i we do O(n) operations to find j'th fountain. Right?
•  » » » » » » » » 3 years ago, # ^ |   0 we find j in logN steps by sorting the array and binary searching after,but thats the tedious part,and its hard to explain.
•  » » » » » » » » » 3 years ago, # ^ |   +1 ... logN steps by sorting the array and binary searching ... So, we sort by beauty or by cost?
•  » » » » » » » » » 3 years ago, # ^ |   +1 by cost
•  » » » » » » » » » 3 years ago, # ^ |   0 In this case, after sorting the array by cost and getting the position of the fountain with less or equal to (total coins — coins for selected fountain) coins, wouldn't one need to check for all fountains less than this found price as well? Then, will it still be logN?
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 yes,because it would be something like max(beauty[1],....beauty[j]),which can be precalculated with another array,where V[i]=max(beauty[1],beauty[2],....,beauty[i])
•  » » » » » » » » » 3 years ago, # ^ |   0 I have used the same approach but my solution is giving WA on test 4 .
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Well,You did something wrong in the code than. Belive me,this approach is good,and i got accepted with it
•  » » » » » » » 3 years ago, # ^ |   0 "ok,i would like to buy this fountain and another one of the same type,but i would like to take the most beautifull one i can afford"But can it be a situation like we can choose 2 fountains in one currency without that fountain we chose in the first time?
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Yes,thats why you take each fountain i from 1 to number_of_same_type,and after you do a max
•  » » » 3 years ago, # ^ |   0 @Reol , I have done same thing as you are mentioning. But was getting WA for 4th testcase... can't figure out what is mistake,,,
•  » » » » 3 years ago, # ^ |   0 Exact same case with me. I did binary search and keep getting WA on 4th test case.
•  » » » » » 3 years ago, # ^ |   0 @hrushikesht, binary search ??? I thought it was simple knapsack problem... where picking up 2 fountains was compulsory :| ... Can't say for sure...
•  » » » » » » 3 years ago, # ^ |   0 well its pretty hard to do knapsack on this,considering you would end up with O(N*C*D) plus,you can choose a maximum of 2 elements,so that would be a costant of 2
•  » » » » » » » 3 years ago, # ^ |   0 @georgerapeanuWhat I mean by knapsack is that. firts of all split fountains which can be bought by only diamonds , and only coins,,, then given list of fountains which can be bougth by only coins,,, use knapsack for them ,,, and DP table size will be ,,, (number_of_coin_fountains * 2) same goes for number_of_diamond_mountains*2 size for other process... Since costs of fountains are within the 10^5 ,,, that was most preferable approach(in my opinion),,,
•  » » » » » » » » 3 years ago, # ^ |   0 wouldnt it be O(C*number_of_coin*2)?because you should take care of the cost,and you are at index i,and you have selected k fountains so far
•  » » » » » » » » » 3 years ago, # ^ |   +3 @georgerapeanu,,,yeah , my bad,,, it will be maximum 100000*2 ,,, and we can fill up the DP table in linear time...but now, you must be getting an idea,,, which KNAPSACK I was talking about
•  » » 3 years ago, # ^ |   +11 I used segment tree range maximum query to find the best pair
•  » » » 3 years ago, # ^ |   0 Can you please elaborate more on the approach?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +2 There are 3 cases: 1. Get 1 fountain with diamonds and 1 with coins, 2. Get both with coins, 3. Get both with diamonds.Case 1 is easy: buy the most beautiful ones that you can afford. For cases 2 and 3 you can use 2 separate segment trees: st[0 or 1][i] = most beautiful fountain that costs i coins (0) or diamonds (1). Iterate through all fountains. If you take fountain i, you have c — cost[i] coins left. Let this amount be x. Use range max query on first segment tree to find the most beautiful fountain whose cost is in the range 1...x and take the sum of current one's beauty and this one's. Then, store current fountain in the segtree. The same applies for diamonds, just use another segtree.From each case you get a value, answer is the maximum of these. Be aware of the situations when you can't buy two fountains.
•  » » » » » 3 years ago, # ^ |   0 I tried something similar but I'm getting WA on test 4. I dunno why. Here is my solution http://codeforces.com/contest/799/submission/27039911
•  » » 3 years ago, # ^ |   0 Observe that you can either pay with coins only, diamonds only or both.Sort by Coins or Diamonds whatever the case and have a dp array such that dp[i] is the fountain with biggest beauty in the range [0..i].We can use binary search for any of the cases.In the last case, iterate through the coin array and use binary search on the corresponding Diamond array.I think all three cases should produce a best value.
•  » » » 3 years ago, # ^ |   0 I was thinking about dp[i], but it can be that for some i1 and i2 that i1 + i2 <= d/c dp[i1] and dp[i2] will be the beauty of the same fountain, or did i misunderstood something?
•  » » » » 3 years ago, # ^ |   0 noeInadal states what I'm trying to say.So once you understand that there are three cases, you basically use binary search and sorting to achieve your aim.It is possible to code without duplicate creation.
•  » » 3 years ago, # ^ |   0 There are three ways of purchasing two fountains: one of each type; two of the first type; two of the second type. In the first case, just consider, for every type, the maximum beauty among the fountains whose price is lower or equal to the number of coins of this type. Then, the maximum beauty is the sum of these two.Then, sort fountains separately according to their price, and precompute for every fountain the maximum beauty with a fountain whose price is lower of equal than this fountain. Then move from most expensive fountain to cheapest one and update the answer if you can.Complexity in O(nlog(n)).
•  » » 3 years ago, # ^ |   0 Unfortunately for me because I attempted and solved(pretest) C, I could not come back and solve my B on time. I hope my speed increases soon. :(
•  » » 3 years ago, # ^ |   0 I did not solve it but those who find segtree easier than bin search can try this for the cases coin+coin and diamond+diamond. For every cost x, maintain two values, the two maximum beauty available and call them b1 and b2. If there is only one, set b1 to -inf and if there is none, set b1 and b2 both to -inf. Now build a segtree over the costs and every leaf node stores the maximum beauty possible with the given cost. If you select a fountain with cost x, replace in segtree with the second maximum beauty and query the segtree. Repeat this for every possible cost.
•  » » 3 years ago, # ^ |   +3 No binary search needed. Since the maximum possible price is not that big, it can be solved as follows. Let's compute fc[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i coins, and id2 is the index of the second most beautiful fountains with the cost at most i coins. Similarly, fd[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i diamonds, and id2 is the index of the second most beautiful fountains with the cost at most i diamonds. These two tables can be easily computed in O(n) starting from i = 1 (or O(n*log(n)) if someone is lazy) if you have fountains grouped initially by an exact price. After that, the only thing to do is to combine the results considering all the cases: you pay only with coins for both, you pay only with diamonds for both, you pay with coins for one and with diamonds for the other.
 » 3 years ago, # | ← Rev. 2 →   0 I think it's awesome how computational geometry problems can be so conceptually simple and yet so hard to solve in contest time (ok probably because it was the last question too).What's the solution for E? (I get the strange feeling that some sort of clever gradual refinement might somehow pass, since it is almost a linear programming question.)Edit: seems like modified mincost maxflow might work...
 » 3 years ago, # |   0 Great contest I liked the problems very much...C was a little bit tedious tho.How to solve D ?:)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Since 2^18 > 1e5, you only need something like 60 items with best cost.
•  » » » 3 years ago, # ^ |   +5 2^17 > 1e5 and 34 items total I believe.
•  » » » » 3 years ago, # ^ |   0 I think so, but I hate tight bounds so I decided to take 55 elements :D
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 What is 4th testcase bro ? (for C question)
•  » » 3 years ago, # ^ |   0 Sort the array a, and then try all possibilities by having last k elements in use? I used multiset array to store variantions of h and w, for some k and then go thru all of them in (k-1) array and try to multiply. As the multiplicator is at least 2 the multisets size might not explode :D
•  » » » 3 years ago, # ^ |   0 it doesnt get TLE ? :O
•  » » 3 years ago, # ^ |   +2 C was easy to code using BIT. Not at all tedious. code
•  » » » 3 years ago, # ^ |   +1 ankububble can you please explain your concept behind your code .... thanks
•  » » » » 3 years ago, # ^ |   +2 Sure.Let dp(i) denote the max beauty when you have to pick 2 fountains from first i fountains and you are selecting the ith fountain. When I am calculating dp(i) , I need to iterate over all j
•  » » » » » 3 years ago, # ^ |   0 Got it ... Thanks a lot and same to you :)
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 solved
 » 3 years ago, # |   -15 I told you we have much confidence on tourist winning the round. Now see he has won it by huge huge margin. On your face who gave me downvotes on my previous comments.
 » 3 years ago, # | ← Rev. 2 →   +36 There are random t-shirts again, so we will use a similar algorithm to the one used several months ago. We have a pseudo-random generator based on testlib.h. The seed will be the winner score in the Tinkoff Cnallenge Final Round on Saturday. The printed integers are the winning places, the ties are broken by the time of last AC. Generator#include "testlib.h" #include using namespace std; int main() { rnd.setSeed(9889); set winners; while (winners.size() < 5) winners.insert(rnd.next(51, number_of_participants_made_at_least_one_submission)); for (auto winner: winners) cout << winner << " "; cout << endl; return 0; } 
•  » » 3 years ago, # ^ |   +14 you use number_of_participants_with_positive_score while in announcement tshirt is for those who have at least one submission
•  » » » 3 years ago, # ^ |   +5 Fixed!
•  » » » » 3 years ago, # ^ |   0 Can you write handles of winners?
•  » » 3 years ago, # ^ |   0 Why do you use seed from the next contest?
•  » » » 3 years ago, # ^ |   +24 So that no one can claim the system is rigged.
•  » » 3 years ago, # ^ |   +13 So winner score is 8876 and number_of_participants_made_at_least_one_submission is 3465,I get these five numbers: 903 935 1552 1591 2272
•  » » » 3 years ago, # ^ |   +13 If I am correct then the T-shirts go to Acarus Xris MashiroSky orz010orz Abuccts
• »
»
3 years ago, # ^ |
Rev. 2   +40

The seed is 8876, the number_of_participants_made_at_least_one_submission is 3465. So the winners are

Place Handle
903 Acarus
935 Xris
1552 MashiroSky
1591 orz010orz
2272 Abuccts

Congratulations!

 » 3 years ago, # |   +3 I need help in Problem D.I need to solve this Subproblem.Given an array A = [a1, a2, a3, ..., an] and an Integer X.Get a Sub Sequence B = [b1, b2, b3, ..., bm] from array A such that b1 * b2 * b3 * ... * bm is >= X and as minimum as possible.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +1 Hint: Note that bi >= 2. So you need at most 17 elements to make their product > 10^5.Hint2: Suppose you are kinking K numbers. You will sort them in descending order and pick the first K numbers.
•  » » » 3 years ago, # ^ |   0 Nice Trick :D Thank you.
 » 3 years ago, # |   +42 Submitting problem A and passed pretest: YES! I did it! I'm the f**king genius! Let's check the dashboard. WTF?! tourist solved problem E already?
•  » » 3 years ago, # ^ |   +18 We know he is a legend :) But he solved E after 41 minutes while you solved A after 22 minutes.
•  » » » 3 years ago, # ^ |   0 22 minutes: Submitted. 22 minutes ~ about 26 minutes： In queue. I checked dashboard: he got '-1' on problem E So, you're right. It should be 'He has submitted problem E already' exactly.
 » 3 years ago, # |   +33 Due to technical reasons the system testing and the rating update will probably be delayed a bit.
•  » » 3 years ago, # ^ |   +16 Why people vote this comment ://////
•  » » » 3 years ago, # ^ |   0 my question too ... !
•  » » » » 3 years ago, # ^ |   0 because he is the codeforces co-ordinator.
•  » » » » » 3 years ago, # ^ |   +1 I think you should better look the message than the writer of it:/
•  » » » 3 years ago, # ^ |   +15 Because he is informing the community so most people don't start expecting immediate system testing. This in my opinion is a respectful thing to do.
•  » » 3 years ago, # ^ |   0 systesting started fairly fast...guess rating change is going to be a bitch.
•  » » 3 years ago, # ^ |   +28 I removed cheaters and recalculated the ratings.
•  » » » 3 years ago, # ^ |   +15 When will the (random) tshirt winners be announced? MikeMirzayanov
 » 3 years ago, # |   0 Hi:I understand that the contest is finished, but is there a way to still submit my code, just to test for myself..?Cheers
•  » » 3 years ago, # ^ |   0 Usually the problems will be added to the problemset, you can upsolve them there
•  » » 3 years ago, # ^ |   0 Yes, after the contest is completely finished, you can submit your code for a problem or run a virtual contest for you. Cheers
•  » » 3 years ago, # ^ |   0 After system test finishes
•  » » 3 years ago, # ^ |   0 You can upsolve after system testing.
 » 3 years ago, # |   0 The contest is over but I am not able to see the submissions of other users. Why is it so?
 » 3 years ago, # |   0 For C, I separated coins and diamonds. Applied knapsack on both of them individually. Then I just checked the maximum 2 values that can be generated taking care of if 2 fountains cannot be generated. Is this method wrong?
•  » » 3 years ago, # ^ |   +5 TLE and MLE Unless you did one hell of an optimization.
•  » » » 3 years ago, # ^ |   0 Thank You. I missed to consider memory limit completely.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +4 there are 3 choices :1) 1 cois + 1 diamond2) 2 coins3) 2 diamondsthe first is easy , the second and the third are the same you have a vector of pair for each type { price , beauty } sorted in ascending ordertry the first fountain to be v[i] with price p1 and you have coins-p1 left the second one will be from range [ 0 , min(i-1, upper_bound(coins-p1)-1 ) ]now take the one with max beauty ( precalculation )something like that ...
•  » » » 3 years ago, # ^ |   0 Thank you for your help :)
 » 3 years ago, # |   -12 In some last minutes, I used brute force way with O(n^2) for problem C and passed the pretest. So the pretest is weak and it is the chance for some cheater who passing it by this way, then open other solution in the same room to find the "real" solution.
•  » » 3 years ago, # ^ |   0 Well, it doesn't make a difference, does it? He/She cannot resubmit his/her solution. And it was more or less obvious from the constraints that an O(n^2) solution would time out, so he didn't necessarily have to look at an optimal solution to figure that out.
•  » » » 3 years ago, # ^ |   +10 Someone can have fake account and see others' solution with locking in fake account, then write in his real account.
•  » » » » 3 years ago, # ^ |   0 That can also be done if doesn't pass pretests...
•  » » » » » 3 years ago, # ^ |   +8 Yes but then it requires solution that passes pretests with intended complexity. This is harder, thus making cheating harder, which is a good thing.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 How do you think XD
 » 3 years ago, # | ← Rev. 2 →   +1 Why was the memory limit so tight in C? I got memory limit exceeded with only 2 segment trees and total memory of around 12 * 105. My contest got ruined because of this :(By the way, how much memory can I declare when 256 MB is the limit?Edit: Nevermind, memory limit wasn't tight. I'm just stupid.
•  » » 3 years ago, # ^ |   0 I have the same problem )=
•  » » 3 years ago, # ^ |   +13 No there will be a different issue. 12*10^5 easily fits 256 MB.
•  » » 3 years ago, # ^ |   +5 I got same error, the problem was in my build function, say if count of 'C' is zero, u shld take care of this in ur build(1,1,count(C)) in the segment tree for C(Coins)
•  » » » 3 years ago, # ^ |   +5 Oh god! I think you're right! I'm so stupid -_-
•  » » » » 3 years ago, # ^ |   0 Yes. That's it. I wasted the entire contest on that. Lesson learned I guess.
•  » » 3 years ago, # ^ |   +24 Your contest got ruined because you are used to use segment trees everywhere, even if there is much simpler solution.
•  » » » 3 years ago, # ^ |   -7 Nothing wrong in that :P. segment trees is not "complex"
 » 3 years ago, # | ← Rev. 2 →   +4 Hats off for strong pretests. Update: I meant in D mainly, and I didn't see many hacks in general.
•  » » 3 years ago, # ^ |   +23
 » 3 years ago, # |   +3 Someone know why MLE here http://codeforces.com/contest/799/submission/27036789 I only use 10^6 integers or where am I wrong?
•  » » 3 years ago, # ^ |   +3 You can't see others' submissions before systest. Can you pastebin it?
•  » » » 3 years ago, # ^ |   +4 Sure, it's a little ugly code... #include using namespace std; typedef int lli; typedef pair ii; typedef pair dd; typedef pair ll; typedef vector vi; typedef vector vlli; typedef vector vll; typedef vector vii; #define fst first #define snd second #define _ cin.sync_with_stdio(false);cin.tie(NULL); #define u_map unordered_map #define sz size #define pb push_back #define u_set unordered_set #define endl "\n" const lli inf = 1e9; const lli mod = 1000000007 ; const int infInt= 1e9; const double PI=acos(-1.00); const double eps = 1e-6; lli n,m,k; lli u,c,d; int len; lli st[2][400010]; vll C,D; void constructST(int ind,int l,int r,int i=0){ if(l==r){ st[ind][i]=((ind==0)?C[l].snd:D[l].snd); return; } int mid=(l+r)>>1; constructST(ind,l,mid,i*2+1); constructST(ind,mid+1,r,i*2+2); st[ind][i]=max(st[ind][i*2+1],st[ind][i*2+2]); } lli query(int ind,int s,int e,int l,int r,int i=0){ if(s>r or l>e)return -inf; if(s<=l and r<=e)return st[ind][i]; int mid=(l+r)>>1; lli L=query(ind,s,e,l,mid,i*2+1); lli R=query(ind,s,e,mid+1,r,i*2+2); return max(L,R); } int main(){_ cin>>u>>c>>d; lli beauty=0;k=0; while(u--){ lli x,y,z;char c; cin>>x>>y>>c; if(c=='C')C.pb(ll(y,x)); if(c=='D')D.pb(ll(y,x)); } n=C.sz(); m=D.sz(); sort(C.begin(),C.end()); sort(D.begin(),D.end()); constructST(0,0,n-1); constructST(1,0,m-1); for(int i=0;ic)break; lli aux=c-C[i].fst; int ind=upper_bound(C.begin()+i+1,C.end(),ll(aux,inf)) -C.begin(); ind--; if(i+1>ind)break; lli q=query(0,i+1,ind,0,n-1); lli temp=q+C[i].snd; if(temp>beauty){ k=2; beauty=temp; } } lli K=0,L=0,xx=0,yy=0; for(int i=0;i=C[i].fst){ xx=max(xx,C[i].snd); K++; } } for(int i=0;i=D[i].fst){ yy=max(xx,D[i].snd); L++; } } if(K and L and xx+yy>beauty){ k=2; beauty=xx+yy; } for(int i=0;id)break; lli aux=d-D[i].fst; int ind=upper_bound(D.begin()+i+1,D.end(),ll(aux,inf)) -D.begin(); ind--; if(i+1>ind)break; lli q=query(1,i+1,ind,0,m-1); lli temp=q+D[i].snd; if(temp>beauty){ k=2; beauty=temp; } } if(k==2)cout<
 » 3 years ago, # |   +5 Were there pretest on D that needed rotation before answering? Its sad that after trying optimization to fit into tle , i forgot this part and now i will get WA...
 » 3 years ago, # | ← Rev. 4 →   0 Why my solution Memory limit #4 I don't undertstand About my memory MX=1e5; two (int,int)[4 * MX] = 2*4*4*4*MX = 128*MX two int MX = 2*MX all 128 * MX + 2 * MX = 130 * MX I think int array[1e6] = 4 Megabyte I tnink **** **** **** ******My memory about 50 Megabyte + (void with other) <= 256 Megabyte**
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Why memory limit? 27037536 My solution...
 » 3 years ago, # |   0 How to solve A? xd
•  » » 3 years ago, # ^ |   -20 We can iterate through time and compute the number of cakes that we can do in that time. for (int time = 1; true; time++) { int cnt_cakes1 = ...; // Number of cakes WITHOUT second oven. if (cnt_cakes1 >= needed_cakes) { cout << "NO"; return 0; } int cnt_cakes2 = cnt_cakes1 + ...; // Number of cakes WITH second oven. if (cnt_cakes2 >= needed_cakes) { cout << "YES"; return 0; } } 
•  » » 3 years ago, # ^ |   0 I solved it like this: First, I calculated time needed for oven 1 to bake all the cakes. t1 = ceil(n/k)*tThen I do t1 — t which is the time the last batch of cakes were put in the oven. If it is less than equal to d, there is no need to build another oven.
•  » » » 3 years ago, # ^ |   0 Same here !
•  » » » 17 months ago, # ^ | ← Rev. 2 →   -8 When I follow your mind. I get wrong answer on 7.I think t1 = floor(n/k)*t. When I do this,I get accept. Here is my code: C++ #include int main(void){ int n,t,k,d; std::cin>>n>>t>>k>>d; int temp=n/k; if(n%k!=0) temp++; puts(d
•  » » 3 years ago, # ^ |   0 if (d // t) * k + k >= n then answer is NO, else answer is YES
•  » » 3 years ago, # ^ |   0 if ( ceil ( n * 1. / k ) * t — t <= d ) cout << "NO" ; else cout << "YES";
 » 3 years ago, # |   -13 Can someone tell me why my approach for C is wrong?First, I try to match 1 fountain of C with 1 fountain of D. In that case it will be the most beautiful of each one that I can afford. The other case is to get 2 fountains of C or 2 fountains of D.So I sort them by cost, and build a segment tree of maximum beauty within range. Then, for each fountain, I take its cost and binary search the most expensive fountain that I can afford (which will give me an index j in the array the segment tree was based on). Then I just query the segment tree for the range (i+1, j). Then take the maximum of every iteration on both types.Wrong Answer on pretest 4.
•  » » 3 years ago, # ^ |   0 What if the fountain of maximum beauty lays in the range from (0,i-1) ? It doesn't look like you account for that
•  » » » 3 years ago, # ^ |   0 well, then it would have been found on an early iteration. I always take the fountain i with the fountain returned by the query. If the best fountain to pair with i (let's call it j) is before i itself, then in the iteration of j the query would have returned i.
 » 3 years ago, # |   0 Why aren't others solutions visible?
 » 3 years ago, # |   0 Just wish I am lucky enough to get a T-shirt, please ：）
 » 3 years ago, # |   0 Any help in B please?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 here's my code it's long but very easy to understand.Note: SF(x) means scanf("%d", &x)Code:)
•  » » 3 years ago, # ^ |   +1 I used set of tuples: (color1, price, color2). It contained each t-shirt twice: (front, price, back) and (back, price, front). So on queries i choose the cheapest t-shirt of given color using upper_bound and erase it from set twice( (front, price, back) and (back, price, front) ). If there's no t-shirts of such color, answer is -1.
•  » » 3 years ago, # ^ |   +1
•  » » 3 years ago, # ^ |   +4 Short solution : code
•  » » 3 years ago, # ^ |   0 I made sorted vector of (price, color_front, color_back, is_sold) and three pointers.
•  » » 3 years ago, # ^ |   0 My Solution CODE
 » 3 years ago, # |   0 I solved B using set in O(mlogn) but my solution didn't care about number of colours, though it was limited to 3. So now I wonder whether it can be solved in linear time or not?
 » 3 years ago, # |   0 Great contest!
•  » » 3 years ago, # ^ |   0 it's just the opposite
 » 3 years ago, # |   0 Why WA11 on E? Can somebody help me?
•  » » 3 years ago, # ^ |   0 Is the general solution to fit some 'both like' decorations + minheap on the rest of the decorations?
 » 3 years ago, # |   0 Why TLE on B 27019672. As far as i know the erase function returns number of elements deleted.
•  » » 3 years ago, # ^ |   0 Because of erase works really slow and you call it many times!! Who can solve B faster than me? (249 msec)
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 Can you explain more ,I mean erase should be log(n) and in worst case , I was erasing 3*200000*log(600000)=1.2*10^7 operations which should have worked right?
•  » » » » 3 years ago, # ^ |   0 Insert also adds N*log(N). Hidden constants are quite big I think. I have read on Timus such stories that TLE happens with STL red-black tree but AC with own tree.
•  » » 3 years ago, # ^ |   0 It's because you use set which for some reason it is much slower, maybe someone else can explain that.same code AC using set http://codeforces.com/contest/799/submission/27041754
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you tell me why one passed and the other didn't 27045354 and 27019672
 » 3 years ago, # |   +1 My solution to problem C got WA because I was comparing a price with a beauty by mistake, the idea was to compare two beauties. After the contest I fixed that and I got AC. How could the first solution have passed the damn pretests!?
 » 3 years ago, # |   +5 WA on 27 in D. ARGHHHHH!
•  » » 3 years ago, # ^ |   0 Probably failure to consider rectangle rotation? I also WAed 27 of D by forgetting to swap variables: "if ((curr >= a && area/curr >= b) || (curr >= a && area/curr >= b))"
 » 3 years ago, # |   +30 The Magic returns again Random_shuffle (: http://codeforces.com/contest/799/submission/27038984
•  » » 3 years ago, # ^ |   +5 Sometimes I think maybe try random but never have enough confidence to really try it
•  » » 3 years ago, # ^ |   +26 I believe this shit is the reason of KAN's comment about that the results are not final :D
 » 3 years ago, # |   +8 So weak pretest on C. Jesus, there was only 10 tests and all of them were soooo simple. Nice trap)
 » 3 years ago, # |   0 Problem B-: link-: http://codeforces.com/contest/799/submission/27030194Can any one please have a look at my code it gives Runtime error on pretest 9 ??. i can't figure it out why..??
•  » » 3 years ago, # ^ |   0 Your code assumes that front and back sides of a T-shirt are TWO DISTINCT T-shirts.
•  » » » 3 years ago, # ^ |   0 No,not really that's why why i have deleted the price of current buyer from all color consist of set of price (ie v[i],i=1,2,3) here v[i] is the set of color i.
•  » » 3 years ago, # ^ |   0 I_hate_my_color please have a look at my code ?? got frustrated ..why got runtime error ??
•  » » 3 years ago, # ^ |   +3 You should store (*it) in a variable then delete it from various sets. Consider x=1 and v[1].size()=1. You first delete it then use (*it) for i=2, and i=3 which is invalid and cause run-time error.
•  » » » 3 years ago, # ^ |   0 Thanks it works...But both way of doing it is same but OH MY bad luck solution is correct but due to this error it got runtime on 9. Bad day..
 » 3 years ago, # |   +157 You know you are legendary when you fail E on system tests but you are still the first
 » 3 years ago, # | ← Rev. 3 →   +9 27040141this submission should get wrong ansprinting -1 for this case100000 100000 1 1 499999 99999 99999 99999
 » 3 years ago, # |   -11 what is the problem with this?
 » 3 years ago, # |   +32 The results (and rating change) are not final yet, the final results will be within several hours.
•  » » 3 years ago, # ^ |   +113 What's the problem?
•  » » » 3 years ago, # ^ |   +26 Cheaters were removed.
•  » » 3 years ago, # ^ |   0 seems nothing changed
•  » » » 3 years ago, # ^ |   0 My rating was 1538 and now 1537.
 » 3 years ago, # |   -10 what is problem of this code
•  » » 3 years ago, # ^ |   +7 First thing to do when you get RTE: Check the arrays bounds!!
•  » » » 3 years ago, # ^ |   0 Thanks it works
•  » » » 3 years ago, # ^ |   0 Hey I was also getting runtime error on Case 9 this but as soon as I did del = *it and then used this del to erase then it got passed this but I am unable to understand why this is so ??
 » 3 years ago, # |   0 Why they made pretest in D so that you don't need to swap(a, b) in no way ant it still passes pretests, when after real tests it fails :/ My solution
 » 3 years ago, # |   +27 D was such an amazing problem indeedI guess my solution is a bit odd but it takes 78ms to finishMy idea was to deal with the easiest two cases separately, that's when the answer is 0 or 1For the general case:We are told that the smallest ai value is not less than 2, which means that in worst case we need 17 elements for each side a = b = 100, 000, w = h = 1, n = 100, 000, that's 34 elements at most, cool isn't itWell that number 34 makes it seems like it's dynamic programming with bitmasking, hmmm maybe but I couldn't utilize this fact muchAnyway let's take a look at the worst case, we have 34 elements and we need to choose a subset of these numbers, multiply them together with one of sides, then multiply the complements of said subset with the other side and check if we can enclose an a * b insideBut 34 is a big number, I would gladly do something like that if it was something like 17, but hey, what if split it into 2 halves, each of which is at most 17 elements, that's 217 subsets -- we can sort the second one in descending order and then loop over each subset in the first half, for each one I want to find the best match in the second sorted half, we may add with each subset the value of its compliment, do something like partial sums over them such that subcomplement[i] = Maxi: subcomplement[0..i]Now we can do for each subset in first half a binary search over the range of subsets, if we can satisfy:w * subleft[i] * subright[l...r] >  = a and check if h * subleftcomplement[i] * subrightcomplement[r] >  = b or when w,h are swapped and a,b are swapped i.e. four cases then there is a solution using 34 elementsWe can try to reduce the count to the half and repeat the process around log2(34) timesBasically we are doing binary search over answer (count) and using meet in the middle technique to check it quicklyNot so sure about the big-O though, may be O(2m / 2 * log2(2m / 2) * log2(m)) and m <  = 34Anyway here is the link27042867(Submission link)
•  » » 3 years ago, # ^ |   +5 I believe the expected solution was along these lines. I was trying to do something similar during the contest time. However, I am still not sure how many people got a simple bfs like solution to pass this constrains. It seems like they are actually exploring a tree with a branching factor of 2 (either multiply the current number to w o h) and the shallowest solution can be upto depth 34. Obviously many branches can be easily pruned but why was this optimization so significant?
•  » » » 3 years ago, # ^ |   +6 For a fixed set of extensions, let the final area of the field after applying all of them be A. Then if A/(a*b) > 100000, there must be a solution (Consider moving field extensions from the width to the height 1 at a time).So A < 1e15. Notice that all states we have are divisors of A, and that no number below 1e15 has too many factors (cannot remember how many, but it's way way less than 2^30). Thus pruning is very effective.
•  » » » » 3 years ago, # ^ |   0 Wont there be multiple states corresponding to one divisor of A.Could ou please elaborate on the proof.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 This is similar to the knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem. Here the value and weights are the same. Consider the following solution:Number the items 1 to n. Consider the set S={0}. For 1 to n, do:Update S' to be S union {S*w_i}. That is, we add to the set S the new possible values that we could form with items up to n. To do this, we just need to add at most |S| values, i.e. the size of the already existing set. The pruning of repeated values keep the size of |S| small.If |S| is bounded by 100000, then we require at most 100000 operations per iteration of the for loop, which is still a lot less than 2^30, and hence runs in time.
•  » » 3 years ago, # ^ |   0 I have done the same. Forgot to swap h, w and perform it again. I used set for those 34 elements. When for a particular mask, I select some of those 34 elements, I remove them from mask and give it to h, then to make w >= b, I greedily reverse iterate on the set till I make w>=b. code
•  » » 3 years ago, # ^ |   +5 I also thought subsets are 2 power 34 . So dynamic programming might time out. But if u observe states are not distinct unless all a[i] are distinct . The states will keep repeating(and 17 is possible only if all a[i] are two). So as 10! is less than 10^5 . Total states will be around 2^20 or so (this is just intuitive). So this is the reason why dp works
•  » » 3 years ago, # ^ |   0 please explain the part where we take complements of the sets .Suppose I choose a particular subset and then do binary search in the other set for the height.Then how do I do for the width.DO we have to try all complements of the chosen subset or one full complement of the chosen subset?
 » 3 years ago, # | ← Rev. 2 →   0 Problem C, any case just as test 4 but simpler ?UPD: AC .. sorry for inconvenience.
 » 3 years ago, # |   +3 How to solve problem E? Thanks.
•  » » 3 years ago, # ^ |   0 Denote set of decorations liked by both to be A, set liked by Arkady only to be B, set liked by Masha only to be C, and set liked by neither to be D. Sort these sets in ascending order by cost and keep their prefix sums.We fix the number of decorations we pick from set A to be x. Then we need at least (k-x) items from set B and set C, and (m-x-2*(k-x)) (call this number KK) remaining items from any set. The (k-x) items from set B and C we can just optimally pick the cheapest items. For the rest, we need to pick the cheapest KK items from any of the sets B,C,and D. Call this final optimal set of KK items to be S. We can binary search for the maximum value M in S (look for the minimum M such that the number of items <= to M in sets B,C,D sum up to more than KK). To do this for each set B,C,D we binary search again for number of items less than M and sum them up. If the minimum such M gives us L items that are <= M, then we subtract (L-K)*M from the prefix sum since all the over-counted items will have cost M.Loop through all possible values of x (0 to |A|) and get optimum answer.
•  » » » 3 years ago, # ^ |   0 I had a similar idea.But I saw many people solve it with segment tree. Can someone elaborate on that?
•  » » » » 3 years ago, # ^ |   0 After fixing x, we are trying to solve the following problem:Find sum of z cheapest items in the union of the following arrays: Some suffix of B Some suffix of C All of D We can keep a segment tree to tell us this quantity. Note that as x increases, we keep looking at larger suffixes of B and C, so we can keep two pointers for B and C and maintain all the candidate values in a segment tree, and report the optimal sum in .Ugly CodeBy the way, did anyone else think that problems A-E were sort of standard logically, and focused more toward implementation? I think there is a huge jump in difficulty from E to F. E isn't really difficult to solve on paper but tricky to code quickly..
•  » » » 3 years ago, # ^ |   0 Thanks a lot for the help!
•  » » 3 years ago, # ^ |   0 I think this problem can be done greedily by using 2 min heaps and 1 max heap. In one heap we will keep all the decorations with weight(cost) for common to both and 2*weight for dec that is liked by exactly one.Second heap for minimum common decoration not yet picked(after all buckets are filled).Third for costliest decoration(belonging to exactly one) which has been picked.If we've not filled all the m decorations we remove from third heap and insert from second one.
 » 3 years ago, # |   0 B.SubmittedCan anyone say why my source code takes 280ms (in n=1.0*10^5) and takes over 3000ms in n=2.0*10^5)? I think it's time complexity is O((m+n)logn)... I guess why the program works slowly is that I used std::deque...?cf) I used struct to save p,a,b and saved that structs(t-shirts) at the deque(one,two,three) and sorted and when the buyer want to buy t-shirts, I used "pop_front" and "erase" to erase one t-shirts.. I think "erase" is cause of TLE...please help me
•  » » 3 years ago, # ^ |   0 I guess that your idea may be right. Complexity Linear on the number of elements erased (destructions). Plus, depending on the particular library implemention, up to an additional linear time on the number of elements between position and one of the ends of the deque.quote from:deque::erase
•  » » » 3 years ago, # ^ |   0 Yeah, you are right.. If I use priority-queue(min_heap).. I think I can solve it faster :) Thanks a lot! have a nice day!
 » 3 years ago, # | ← Rev. 5 →   0 I think the final tests for C are too weak. I got AC in the contest 27031840 , but now I realize that I made some mistakes when I decided to reduce the execution time. ex.it will WA on the data below 2 10 0 5 3 C 6 3 C `Now I have fixed the mistakes.27044385 [If you guys can find other mistakes, please tell me. thx!]Sorry for my poor English.XD
 » 3 years ago, # |   0 Problem D is also solvable with Meet-In-The-Middle. Here is my code 27046475
 » 3 years ago, # |   +15 When will the editorial be available?
 » 3 years ago, # | ← Rev. 2 →   +6 when will the random 5 participant who get tshirt be posted .
 » 3 years ago, # |   +19 When will be the editorial uploaded?
 » 3 years ago, # |   0 Why I have TL in my solve: 27047914. It s very strange
 » 3 years ago, # |   0 for problem C is it ok to sort by bi/qi and then use binary search?
•  » » 3 years ago, # ^ |   0 i did that, sorted by bi then binary searched over bi.
•  » » » 3 years ago, # ^ |   +1 i mean sort on (bi/qi)(devide :D)
•  » » » » 3 years ago, # ^ |   +3 No, you can't. Cause worst case is O(n^2), like you picked most quality thing, now you have only 5 c it doesn't mean, what you should buy most expensive thing, cause it can have lower quality then cheap. Sry for me english)
•  » » » » 3 years ago, # ^ |   +3 I meant that the binary search is useless in this situation
 » 3 years ago, # |   +11 What is the intended solution in F? I've accepted solution with no more than 24n queries to the segment tree in upsolving but had some troubles fitting it in time limit. I've seen some solutions without this data structure, maybe someone can share his approach?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 I've posted the problem analysis. My code is 27058630, it uses no more than 2m + 6n queries to segment tree.
 » 3 years ago, # |   0 Can someone explain why this solution fails on C?
 » 3 years ago, # |   +8 MikeMirzayanov KAN, When will you announce the five random T-shirt winners ?
•  » » 3 years ago, # ^ |   +22 Obviously, after Tinkoff Challenge Round.
 » 3 years ago, # |   -16 Why so serious? My corrently account is sina-ss you send me whats your problem
•  » » 3 years ago, # ^ |   0 What are your mistakes in solutions to B?
•  » » » 3 years ago, # ^ |   +3 if(n == 123) puts("LOL");The cheating idea was shared a few days ago by a person who had 20 account in top 30.
•  » » » » 3 years ago, # ^ |   0 Kidding me?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 feeder
•  » » » 3 years ago, # ^ |   -9 The feeders are better than lossers
 » 3 years ago, # |   0 I have seen solutions of C using fenwick tree( also called Binary Indexed Tree or BIT) such as this one : (http://codeforces.com/contest/799/submission/27019364) Can somebody explain this ?