### tunyash's blog

By tunyash, 6 years ago, translation, ,

Hi all! This round is prepared by me, caustique, Fata1ist, KAN, malcolm. I thank Gerald, who has organised our work and helped us with tricky situations, MikeMirzayanov for the system of organasing contest delinur for the translation.

I hope that all problems will be OK and everyone will find intersesting problem for him/her.

Winners:

div1:

div2:

I apologise for the mistakes in statements. I will be more careful in the next time.

• +304

 » 6 years ago, # |   +13 scoring system?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +28 Standard. Score distribution is not defined at the moment
•  » » » 6 years ago, # ^ |   +21 The word is actually "standard". I've seen it get misspelled a lot on this site, it's about time I let people know how to spell it correctly.[http://www.oxforddictionaries.com/definition/english/standard] [http://www.merriam-webster.com/dictionary/standard]
•  » » » » 6 years ago, # ^ |   +27 Thank you =)
•  » » » » 6 years ago, # ^ |   +68 This is a common bug for all Russians :) In fact, the word "standard" in Russian is spelled like "standartny" with "t" but not "d". And even if you know the correct English spelling sometimes it may be hard to remember the correct ending.
•  » » » » » 6 years ago, # ^ |   +37 Cool, thanks! Now I know why it keeps happening! :)
 » 6 years ago, # |   +2 Oh,I smelt some special tricks..
•  » » 6 years ago, # ^ |   +6 I think we should careful with problem A. :)
•  » » » 6 years ago, # ^ |   +3 yes ı misunderstood problem A. I thought digits bigger than k werent allowed :(
•  » » » » 6 years ago, # ^ |   0 Yes. And I was spend for 15 minutes to thinking about sample test 2 util the announcement appear
 » 6 years ago, # |   +3 I guess the problems will be short and interesting. Like this blog.
•  » » 6 years ago, # ^ |   -11 You know what's interesting?
•  » » » 6 years ago, # ^ |   0 Did you know facts are considered to be interesting. So this proves there are things that are universally interesting.
•  » » » 6 years ago, # ^ |   0 I don't understand your mind clearly. But I think interesting 's different with every pepple. With me, that 's tricky test and many solution has ben hacked! O_o
 » 6 years ago, # |   0 hope problems will be good..
•  » » 6 years ago, # ^ |   -16 don't even hope that problems would be so easy for you
•  » » » 6 years ago, # ^ |   +2 A strange comment for a gray one...
•  » » » » 6 years ago, # ^ |   +17 Guy that writes gray code?
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   -17 No.Guy who has the rating very small(of colour grey).You are purple, I guess
 » 6 years ago, # |   -74 giygctr gotcs metrr o'le!!
•  » » 6 years ago, # ^ |   0 wut?
•  » » » 6 years ago, # ^ |   -20 giygctr gotcs metrr o'le!!
 » 6 years ago, # | ← Rev. 2 →   +25 why is today's problemset so hard?
 » 6 years ago, # | ← Rev. 4 →   +20 This round is similar to Round 144 Div1 standings This round prepared by tunyash too.
 » 6 years ago, # | ← Rev. 2 →   +23 look at Antoniuk at div. 1. He worked well :DP.S : He is in last page.
 » 6 years ago, # |   0 this exam very suck for div 2 everyone have solved A and B and no one able to resolve the C , D , E
•  » » 6 years ago, # ^ |   -16 I can't agree with U. Problem C was just an exercise for Range Tree, main problem was to realize it(I wasn't successful in it ._.).
•  » » » 6 years ago, # ^ |   +20 sum(x,y,z,t)= (s[x]+...+s[y])*(s[z]+..+s[t]) = ayou can solve this by fixed [x] and [y] and pre calculating [z] and [t]nothing about Range Tree i guess.
•  » » » » 6 years ago, # ^ |   0 Damn, U're right, it's easier way :)
 » 6 years ago, # |   0 Does anyone knows the 4-th test for B?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 I think, something like — 5 0 0 0 0 0, answer is 5
•  » » » 6 years ago, # ^ |   0 I think 5 0 0 0 0 0 will output 2
•  » » » » 6 years ago, # ^ |   +1 No:)
•  » » » » 6 years ago, # ^ |   0 0 + 0 = 0 .. so 5 zeros will yield answer 5
•  » » » » 6 years ago, # ^ |   0 oh yeah, my mistake, sorry
 » 6 years ago, # |   0 If anyone can tell me what is the pretest 3 for problem A div 2 I would be very thankful...
•  » » 6 years ago, # ^ |   0 Show your code.
•  » » » 6 years ago, # ^ |   0 Here:5162244
•  » » » » 6 years ago, # ^ |   +1 Upload it here.
•  » » » » » 6 years ago, # ^ |   0
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 The digit in number can repeat.It's false. (int) vv.size()==k+1 UPD: It's true.
•  » » » » » » » 6 years ago, # ^ |   0 I'm putting the numbers in a set before doing such count... A test like:1 210000012gives 1 on my code
•  » » » » » » 6 years ago, # ^ |   0 while(n > 0) { if((n % 10) > k) return false; n /= 10; } return true; 
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 k goes from 0 to 9....Why should I return false like that if I am already doing the repeated number exclusion with the set?EDIT: By doing the vv.size()==k+1 I am assuring that my function also returns correct values, yes or no?
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I don't understood problems.
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 What if k == 0 and numbers on liste equals to zero too? Your programm return automatically 0 when k == 0 But for this input: 2 0 0 1 It should return 1 instead of 0
•  » » » » » » » 6 years ago, # ^ |   0
•  » » » » » » » 6 years ago, # ^ |   0 This input is invalid (1 <= ai <= 10^9)
•  » » 6 years ago, # ^ |   0 The test would be like this: 1 6 01234567 Answer should be 1.
•  » » » 6 years ago, # ^ |   0 No leading zeroes are allowed, from my understanding:"The first line contains integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 9). The i-th of the following n lines contains integer ai without leading zeroes (1 ≤ ai ≤ 10^9)."So that wouldn't be a valid test....
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 No leading zeroes are allowed, so it can be like this: 1 6 12345670 Answer still should be 1.MISTAKE: k-good number should contain each digits no more than k, but if number contains each digits no more than k AND other digits more than k, it still be k-good number.
•  » » » 6 years ago, # ^ |   0 a[i] (1 ≤ a[i] ≤ 10^9) 
•  » » 6 years ago, # ^ |   0 case 2 0 0 0answer =2 your code gives 0
•  » » » 6 years ago, # ^ |   +2 Numbers can't be 0.......
•  » » 6 years ago, # ^ |   0 1 0 10interesting observation about k == 9, but k == 0 ...
 » 6 years ago, # | ← Rev. 2 →   0 Does anybody know what's the 5-th tests for C ? I would be very thankful
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 0 00 и 0 110
•  » » » 6 years ago, # ^ |   0 aaaand the naswer is 9
•  » » 6 years ago, # ^ |   0 Kind of: 0 005 answer: 27
•  » » » 6 years ago, # ^ |   +5 i am so f**ing idiot
 » 6 years ago, # |   0 Div 2. Problem CThe moment I realized I can't think better than O(n^3logn) or O(n^4) for MaxSum in a rectangle.
•  » » 6 years ago, # ^ |   0 That was the moment I realized the array contained only digits so I could do it in O(n^2).Most enlightening moment I got in a contest.
•  » » 6 years ago, # ^ |   0 I had an O(n^2log(n)) solution that I couldn't finish coding. I'm not sure if it is correct though, because it uses O(n^2) space.
•  » » 6 years ago, # ^ |   0 how do you do n^3logn?
 » 6 years ago, # |   0 where are the editorials/tutorial to div2 213?
•  » » 6 years ago, # ^ |   0 not posted yet i guess
 » 6 years ago, # | ← Rev. 11 →   +26 The bad description of problem D div2（problem B div1) really makes me mad!!!!I read it more than 5 times and still don't know what are you talking about, until I found the Note at the bottom and read the Note more than 5 times.How can you use nothing to exchange something?You should say: Set x can contain nothing. Set x and Set y can't contain the same item instead of the shit of "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y."."John knows that his city has n items in total." Ok, there are n items in the city, but how many items in the market?
•  » » 6 years ago, # ^ |   0 For the second sample, why cost two days? why not three days? Input 3 5 1 2 3 output 6 2
•  » » » 6 years ago, # ^ | ← Rev. 5 →   0 first day = {} -> {1,2} now assume he leaves {1,2} at his home.second day = {} -> {3} so now he has all of {1,2,3} with him in two days.
•  » » » » 6 years ago, # ^ |   0 Thanks, I got it. It's hard to understand this problem of the poor description, but the solution seems not that hard.
 » 6 years ago, # |   0 Any Ideas for problem C , Div 2 ?
•  » » 6 years ago, # ^ |   0 You observe that in a rectangle the sum is (Ax1+A(x1 + 1)+...+Ax2)*(Ay1+A(y1 + 1)+...+Ay2), where x1,y1,x2,y2 are the corners, and the maximum sum of a sequence is 9*n.
•  » » 6 years ago, # ^ |   0 Range Tree. U just need to find all x1, y1, x2, y2: sum(x1, y1) * sum(x2, y2) == a. But you should do it smart: 1)Find all x, y: a % sum(x, y) == 0 2)for each of them find all x1, y1: sum(x, y) * sum(x1, y1) == aIt seems like this solution is )(n ** 4 * log(a)(because of Range Tree)), but it is O(n**2 * k * log(a)), where k is number of divisors of a(close to log(a)).
•  » » » 6 years ago, # ^ |   +3 No range tree. You just need to factor n and n is equal to the multiplication of range sums that can be calculated in quadratic time
•  » » » 6 years ago, # ^ |   0 No.You just keep a vector ap where ap[i]=number of sequences of sum i, i<=9*n. For a subsequence [i,j], if A%sum(i,j)==0, you add at result ap[A/sum(i,j)].Take care at the case when sum(i,j)=0 and when A=0
 » 6 years ago, # |   +1 Anybody home ? someone start system testing
 » 6 years ago, # | ← Rev. 3 →   +3 In problem AWhen writing Let's call a number k-good if it contains all digits not exceeding k (0, ..., k).Here, doesn't it mean that a k-good number can't have any digit greater than k ???So far I know, it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.It has given me a lot of pain.
•  » » 6 years ago, # ^ |   0 You cannot assume that it does not contain digits greater than k as long as it has not been mentioned in the statement.Actually, you just cannot assume something when it has not been specified in the problem statement.
 » 6 years ago, # |   0 Nooo, finally found out one minute after the competition, that my C gave time limit exceeded because I forgot to print the final \n. First time I've had that bug :(
 » 6 years ago, # |   +7 Got owned for the 100th time by integer overflow for div1 A T_T
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 in my code was:typedef int li;... #define int liP.S. Of course, it must be typedef long long li
•  » » 6 years ago, # ^ |   0 Same here, mistakes like this will kill me someday.Hoping rating doesn't decrease much ...
•  » » 6 years ago, # ^ |   0 Overflow too. T_T
 » 6 years ago, # | ← Rev. 2 →   +114 Congratz lovelymoon for his E 5163338 :D (11.996s, TL is 12s)
 » 6 years ago, # |   +63 What is the intended solution for Div1 C? Is it possible to prove it without testing all valid inputs?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 UPD: Sorry, here was the solution for B, not C.
•  » » » 6 years ago, # ^ |   +13 Correct. That is, however, the solution to Div1-B :)
•  » » » » 6 years ago, # ^ |   0 Ah well, that makes sense:) Sorry
•  » » » » » 6 years ago, # ^ |   +7 Well, since you already wrote it, you should probably leave it around, maybe in a separate thread.
•  » » » 6 years ago, # ^ |   0 I think this is solution for Div1 B, not Div1 C
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 I understand that the reduction works, but why does that mean that the restriction doesn't mean anything? Why can't the algorithm still find a move that is illegal?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 Consider any two sets A and B, with c(A) + d >= c(B). Let their intersection be denoted as C, meaning A\C and B\C don't have anything in common.c(A) = c(A\C + C) = c(A\C) + c(C) >= c(B) — d = c(B\C) + c(C) — dc(A\C) >= c(B\C) — dWe can substitute set A\C with set B\C, thus turning A into B.Therefore, for any two sets A and B such that c(A) + d >= C(B) we can turn one into another in one step.Every step in our algorithm does exactly that, so every move we make is legal.Does that explain it?
•  » » » » » 6 years ago, # ^ |   0 Yep, I got it now, thx.
•  » » » » » 6 years ago, # ^ |   +18 I thought we have to swap whole set we have currently with some other set. Really poor problem statement. :(
•  » » » » » » 6 years ago, # ^ |   +3 Yes, I thought that too, until I analyzed the sample test cases.
•  » » 6 years ago, # ^ |   0 Mmm. My solution constructs correct set with k' ≥ k elements. It's possible to prove, that we can obtain correct set for any k. But then I use statistic to prove, that I can obtain correct set with exactly k elements. I will write about it in editorial.
 » 6 years ago, # |   -6 Nice contest and interesting problems.... Like your other contests....thanks!
 » 6 years ago, # |   0 Is there an alternate solution for Prob:C Div2 ? Something using Data-Structures ?
 » 6 years ago, # |   0 k-good numbers input 1 0 1000000000Output1really 1<0?
•  » » 6 years ago, # ^ |   0 It must contain all digits who doesn't exceed k, so if 0 wasn't present, the number was invalid. But it can contain digits who exceed k, that's not a problem. So, yes , 1 > 0, but 1 0 1000000000 should get for output 1
•  » » » 6 years ago, # ^ |   0 very bad translation, it is k-good if it contains all of (0,..,k) was better, I'm not American by the way
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 kind of know the reason. "the number contains all digit from 0 to k " is not equal to " the number only can contains all digit from 0 to k.". I should not have this assumption.
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   +1 Actually problem is in "not exceeding k (0, ..., k)". There was no need of this portion.When writing Let's call a number k-good if it contains all digits not exceeding k (0, ..., k). it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.Anyway which happened it was to be happened. No doubt, short description of last contest was nice to see. But we also hope better translation from this great community.
 » 6 years ago, # |   +12 tanks for the contest. this was to this date my best contest and I don't think I am ever going to get a better rank in codeforces. I didn't like problem C, I solved using simple backtrack. problem A and B and D were great.
 » 6 years ago, # |   +11 That moment in which you get WA #115 on Div1-D because you forgot that rand() only goes up to 32767... :(
•  » » 6 years ago, # ^ |   0 Can you describe your idea?
•  » » » 6 years ago, # ^ |   +16 Suppose you know GHD divides some element a[i] of the array. You can then take the gcd of a[i] and all other elements, and count how many times each of the divisors of a[i] also divides other elements of the array (should be easy to do in n log n). The largest one that appears more than n/2 times is the GHD.Now, the question is finding such an element a[i] quickly. But as GHD divides at least half of the a[i]s, the chance that you take an a[i] that has the required property is over 50%! So just take a[i]s randomly until you run out of time.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +5 for (int i = 0; i < d.size(); i++) { for (int j = 0; j < i; j++) { if (d[i] % d[j] == 0) cnt[d[j]] += cnt[d[i]]; } } I see such chuck of your code. It doesn't seem to be O(NlogN) as announced in your short editorial, it's rather O(NlogN + (number of divisors of a[i])2 which consumes much more time.Can you tell how you're going to process this part of solution in O(NlogN) time?
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 Maximum number of divisors for a number up to 1012 is less than 7000. So it is not considerably worse than O(NlogN) part I think.
•  » » » » » » 6 years ago, # ^ |   0 It's true assumption when one is trying to code working solution during a contest but what if the numbers will be up to 10^16? You still we be able to factor one number quite quickly and to calculate all GCDs quickly but the part with 2 loops to traverse list of divisors will be bottle-neck in such solution.I'm just trying to figure out better approach to solve this problem.
•  » » » » » 6 years ago, # ^ |   0 vector d represent the divisors of a[idx] which is theoretical have at most 2*sqrt(a[idx]) elements. but practical it is much less.
•  » » » » 6 years ago, # ^ |   0 What a weird solution !thank you.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 that too, it was the last test! really unfortunate!
 » 6 years ago, # |   -9 please update ratings! thank you so much
 » 6 years ago, # |   -22 I hope Petr rise again :)
 » 6 years ago, # | ← Rev. 3 →   0 :)
 » 6 years ago, # |   0 very short and clear problem statements . thank you for this nice round although my score decreased :D .
 » 6 years ago, # | ← Rev. 3 →   +3 I just found the "problem revision"(30) in the detailed submission page.But What is the problem revision? Thanks for help! Problem Lang Verdict365D — 30 GNU C++ Wrong answer on test 8
 » 6 years ago, # | ← Rev. 2 →   +5 This contest is very great, with so many rand() needed and some hard problems :-P
 » 6 years ago, # |   +8 Editorials please !! :)
 » 6 years ago, # |   0 hi everyone, for problem B,why this verdict???1 1000 Answer 1 Checker Log wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
•  » » 6 years ago, # ^ |   0 You don't print anything. Look at if(n==1)
•  » » » 6 years ago, # ^ |   0 Thanks !! bad luck!
 » 6 years ago, # |   0 Could anyone have a look on my submission 5162269 for Matrix problem? I don't understand why I am getting a run time error...
•  » » 6 years ago, # ^ |   +1  if(a%(it->first) ==0 && m.find(a/(it->first))!=m.end() ){ It looks like you divide by zero in this string.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 i think it maybe because you are trying to compute a%(it->first) and a/(it->first), but the value of it->first maybe zero if the string contains a 0 character.
 » 6 years ago, # |   +1 Thanks for the contest, Finally I became blue!! :D ..
 » 6 years ago, # |   +8 at the very beginning i got problem A,B done within half an hour while just before the contest end,i wrongly took the lower bound of ai as 0 and think i may be able to hack some careless guys who also didnt handle the data 0,so i quickly submitted problem A again with speical judgement for the case when ai is 0,...then the system reply tell me ai must be >= 1.and my rank in room suddenly drop from 8 to 16.. it really proves that evil will be rewarded with evil.ToT
 » 6 years ago, # |   0 A and B 's very easy. But C 's so hard. (Just with me :) )
 » 6 years ago, # |   0 i liked the problems, though i could not participate
 » 6 years ago, # |   0 Is there someone fix the description of problem D. Free Market？ How to understand this statements: "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.". For the samples, second one, why 2 days？ one change a day, at least three days? input 3 5 1 2 3 output 6 2How could those get AC?
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   +14 I look forward to editorial
•  » » 6 years ago, # ^ |   +3 it has been published here
 » 6 years ago, # |   0 Hey i am new to codeforces and would be thankful if anyone could tell me as to when the editorials to the round #213 Div 2 would be issued.
 » 6 years ago, # |   +10 Thanks for beautiful problems.I enjoyed so much :)
 » 6 years ago, # |   +5 Unbelievably lucky! lovelymoon's (div1 winner) E problem takes 11996 ms (TL is 12s) on the maximum test case :)
 » 6 years ago, # |   0 Any hint for problem #213 div1 'A'..........