### Rebryk's blog

By Rebryk, 7 years ago, translation,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #291 (Div. 2). It'll be held on Saturday, February 14 at 19:30 MSK.

Great thanks Maxim Akhmedov (Zlobober), Vasya Antoniuk (Antoniuk) for helping me preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.

Good luck everyone!

UPD: Score distribution will be the next — 500-1000-2000-2000-2500.

UPD: Editorial. Sorry for the delay)

• +248

 » 7 years ago, # |   +43 wish it will be the way to DIV 1 :-)
 » 7 years ago, # |   +31 I hope your next round will be Div. 1 too :)
•  » » 7 years ago, # ^ |   -11 This round was a Div1 itself... :D
 » 7 years ago, # |   0 What a shame ! I have a flight on that time. I will miss that round. I hope not to be busy at next contest on codeforces . Contests make addicted :)
•  » » 7 years ago, # ^ |   0 You can participate virtually...
 » 7 years ago, # |   -21 I want to be a Candidate Master...
•  » » 7 years ago, # ^ |   +33 Not everyone gets what they want. For example I want to be a potato, but I can't... Probably the fact that my name isn't GLaDOS helps.
•  » » 3 years ago, # ^ |   +16 Hey! I just chanced upon this comment, and I see you've become a Master now. Congratulations.
•  » » » 3 years ago, # ^ |   0 thanks, my dreams come true xD
 » 7 years ago, # |   +244 That's why I have no girlfriend...
•  » » 7 years ago, # ^ |   0 yeah! that's because making out in valentines day is too mainstream for programmers :3
•  » » » 7 years ago, # ^ |   +3 Unless you are a brogrammer.
•  » » 7 years ago, # ^ |   0 Relation with Problem.........Codefoces Guy.
 » 7 years ago, # |   -24 hope i will be blue today ...
•  » » 7 years ago, # ^ |   +23 Why do you need to write that here ?
•  » » » 7 years ago, # ^ |   0 Psss, nobody needs to write anything here
 » 7 years ago, # |   0 sorry if you see that I shoudn't write like this..
 » 7 years ago, # |   -9 Have Any Problem Of Valentine's Day?
 » 7 years ago, # |   +86 Today is the birthday of the first electronic general-purpose computer.Happy Birthday ENIAC.
•  » » 7 years ago, # ^ |   +8 Only single yellow guys have such excellent knownledge
 » 7 years ago, # |   +10 very interesting problem set, many thanks for not setting a valentines theme.. star wars theme was a pleasant surprise
 » 7 years ago, # | ← Rev. 3 →   +20 UPD: Finally, +17:-3, including: 1 triple hack, 4 double hacks, 1 last minute hack.Well done!
•  » » 7 years ago, # ^ |   +1 LOOOOL!!
 » 7 years ago, # |   +1 Hopeful of being a room winner for the first time :)
 » 7 years ago, # |   -10 Riiiiiiiiidamtanx
•  » » 7 years ago, # ^ |   +4 I think so for myself! :D
•  » » 7 years ago, # ^ |   +25 That moment when you understand Persian :)))
•  » » 7 years ago, # ^ |   0 I ridam too
 » 7 years ago, # |   +1 I got WA at #6 on problem C. Anyone knows what it is about?I solved the problem using a Trie.
•  » » 7 years ago, # ^ |   0 A hashmap is enough, given the constraints, i think. My approach uses m.log(n)
•  » » » 7 years ago, # ^ |   0 can you explain your solution? I also used Trie but got TLE on testcase 10.
•  » » » 7 years ago, # ^ |   0 Hey, can you please explain your approach using hashmap. I couldn't solve the problem during the contest. But have to solve it anyhow, now.
•  » » 7 years ago, # ^ |   +1 Try this 2 1 aaa aab aaa answer: YES
•  » » » 7 years ago, # ^ |   0 It works on this case.
•  » » » 7 years ago, # ^ |   0 I've used hashing. It gives right for your test but fails on test #6.
•  » » » 7 years ago, # ^ |   0 This is test case 6, I think
•  » » » 7 years ago, # ^ | ← Rev. 4 →   0 I think I found the case: 1 1 aaa aaa Answer: NO, because there should be exactly 1-symbol difference.Oops, didn't notice comment on the bottom
•  » » 7 years ago, # ^ | ← Rev. 3 →   +5 I think Pretest 6 has a string equal to original string, when problem says they must differ by exactly one position. Such as this, output should be "NO":1 1aa
•  » » » 7 years ago, # ^ |   0 OMG! Thanks...
•  » » » 7 years ago, # ^ |   0 You're right :-(. I didn't pay attention to '**exactly** one position'. Now it works. Thanks!
 » 7 years ago, # |   0 How to solve A.Or what is test 8 for problem A.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I failed this pretest in my first submission, i guess it's something like: 9999999999 And answer is: 9000000000 
•  » » » 7 years ago, # ^ |   0 no, it was test 4 )
•  » » 7 years ago, # ^ |   0 number shouldn't have leading 0 so check if 1st character is 9 or not if it is nine do nothing if not change to 9-s[0] or not accordingly if it is greater than 4 or not . rest all was just checking if character if greater than 4 change to 9 -character less let it be
•  » » » 7 years ago, # ^ |   0 So what is anser for 9999.is it 9 or 9000 or what
•  » » » » 7 years ago, # ^ |   +5 9000
•  » » » 7 years ago, # ^ |   +8 I don't know... but by 'with no leading zeros' I understood that you can't write 0003 (for example). I think that the statement should say something like 'with the same nuber of digits'.What do you think?
•  » » » » 7 years ago, # ^ |   +6 The problem should have mentioned "with the same number of digits"! :(
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 Yes , actually this is very poor statement in the question.I am very disappointed like this type of problem statement [user:Zlobober][user:antoniuk].I am also wonder how some top guys think about this in the only first chance.
•  » » 7 years ago, # ^ |   0 Some number where first digit is 9, i guess. Like 9631 with answer 9331.
•  » » 7 years ago, # ^ |   0 According to problem statement "The number shouldn't contain leading zeroes". So the 1st digit can not be 0. May be test 8 has this check.
 » 7 years ago, # | ← Rev. 2 →   0 What was the hack test on C?Overflowing the length in a char array? (up to 6*10^5)Just time outs?WA with the same string as in dict?I submitted a brute force that passed the large pretest (took some work) just to hack on C XD, thinking it was overflowing the char array, but everyone used cin >> string so nothing for meSomehow no one hacked my solution (maybe not enough time)EDIT: WHAT, my brute-force C passed systests...
•  » » 7 years ago, # ^ |   +30 ML/TL for generating all possible strings and putting them into map.WA for using hashes modulo 2^64.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +13 Not necessary 2^64. I have hacked a few solutions that use one hash modulo 10^9 + something. It is also possible to find a collision for two hashes, too(but this generator is slightly harder to implement).
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 I don't think people are so brash, but maybe this is the caseUPD. Turns out that post had only Russian version. That post is about hash collision generator, code: http://pastebin.com/JfTEUwCe
•  » » 7 years ago, # ^ |   0 The one I hacked is looping with strlen(s), which is, of course, linear time.
•  » » 7 years ago, # ^ |   0 pretests are a bit weak, i think. I got pretests passed in my first approach where space complexity was O(n^2) [Unnecessary though]
•  » » 7 years ago, # ^ |   +1 O(Nsqrt(N)) didn't pass. T^T
•  » » 7 years ago, # ^ |   0 That is definitely code to revise, you submission 9848284 is brute force, yet it survived pretests and system tests. I tried the same in my submission 9846794, but it failed pretests.
•  » » 7 years ago, # ^ |   0 why did you write in your submission ~~~~~ if (len<=100) ~~~~~ and if (lineS[j]=='d') 
 » 7 years ago, # |   0 Is in the problem E answer is polynomial of degree ~100?
•  » » 7 years ago, # ^ |   +8 I think matrix exponentiation is the answer..
 » 7 years ago, # |   +1 Is solution of 514E - Darth Vader and Tree related to matrix multiplication?
•  » » 7 years ago, # ^ |   0 yeah I'm pretty sure.
•  » » 7 years ago, # ^ |   +6 I think that it's similar to this problem: https://www.hackerrank.com/contests/w10/challenges/towers.
•  » » 7 years ago, # ^ |   +20 Let's say that dp[i] is equal to number of vertices at distance i. d[i]<=100, so you need only values of dp[i-1]...dp[i-100] to calculate dp[i]. And this calculation can be represented by matrix multiplication, where variables are dp[a],dp[a-1],...dp[a-100], and you are multiplying this vector by some matrix to get dp[a+1],dp[a],...,dp[a-99].In order to solve original question you have to add one more variable, ans[i]=ans[i-1]+dp[i].
 » 7 years ago, # |   0 How to solve B ?
•  » » 7 years ago, # ^ |   0 Count the number of groups of vectors (positioned to x0, y0) so that for each pair of vectors in the group, their dot product is zero, and no vectors in different groups give zero as their dot product.
•  » » 7 years ago, # ^ |   0 I did a brute force . take the position of gun let it be a,b . then for i=1..n .maintain a array called as killed[i] denoting if you killed ith enemy or not. start a loop from 1 to n check if killed continue. otherwise break .let this position be m. find coefficient of line passing through a,b and this point then for elements m+1..n check if it comes under the line .if it does mark killed[] =1 ; check if all are killed if it did break and print the count
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 I construct a, b, c in equation ax+by+c = 0 for (x0,y0) with (xi,yi) , i = 1..n. And you should make gcd(a,b,c) = 1 and a > 0. After that, you can sort n equation (a,b,c). Remove (a_i,b_i,c_i) == (a_j,b_j,c_j) by unique in C++. So that you have the result in O(NlogN)
•  » » » 7 years ago, # ^ |   0 Hey i did the same but got WA on 8th test case ..
•  » » » » 7 years ago, # ^ |   0 http://ideone.com/uzEJcWMy code link ..
•  » » » » » 7 years ago, # ^ |   0 Try this test: 4 0 0 0 1 0 -1 1 0 -1 0 
•  » » » » » » 7 years ago, # ^ |   0 That did the trick I was dividing delta y by delta x for the slope, and didn't account for delta x being zero.Thanks!
•  » » » » » 7 years ago, # ^ |   0 You can see my code
•  » » 7 years ago, # ^ |   0 you get all N points and you insert tan((y-y0)/(x-x0))in an array tan and the answer is the number of different numbers of array tan .
•  » » 7 years ago, # ^ |   +6 well, let's count the number of the different slope k = (y — y0)/(x — x0). I think so!
•  » » » 7 years ago, # ^ |   0 I did that but I lost 100 point due epsilon precision. What is the default precision we need to use to compare two doubles?
•  » » » » 7 years ago, # ^ |   0 Consider two doubles a and b equal if fabs(a-b)<=EPS, where EPS is something like 10^(-9).
•  » » » » » 7 years ago, # ^ |   0 Then, the number should be 10^(-9). I used 10^(-4) and 10^(-6), getting WA in both. AC after 10^(-9) with the same solution.
•  » » » » » » 7 years ago, # ^ |   0 2 -10000 -10000 7711 946 946 -3235 Correct answer is 2. With epsilon 10 - 6, the answer seems to be 1; the numbers are close enough. (If you're wondering, the differences 6765, 10946, 17711 are consecutive Fibonacci numbers, which is why .)
•  » » » » » » » 7 years ago, # ^ |   0 Got it! Thanks.
•  » » » » 7 years ago, # ^ | ← Rev. 4 →   0 in such cases when you are not sure of what value to assign to eps, you can use set and let the compiler do the rest.I did the same, and it worked like charm. 9834951
•  » » » » 7 years ago, # ^ |   +6 I tried storing numerator and denominator seperately as int after taking gcd, and it worked. You can view the solution here
•  » » 7 years ago, # ^ |   +1 Find the slope of each point with respect to gun. Store them in set. Print the size of the set. If denominator while calculating slope is zero, assign it some infinite value. I hope it helps.
•  » » » 7 years ago, # ^ |   0 Umm did you store the slopes in a double? There could be precision errors then.. not sure though. I prevented myself from doing it this way due to the possibility of this error.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Yeah stored them as long double. I hope there are no precision errors. Edit: It passed.
•  » » » » 7 years ago, # ^ |   0 I stored each slope in a set of doubles and my solution passed tests. Guess I got lucky.
•  » » » » » 7 years ago, # ^ |   0 An alternative would be to write a fraction class as such: class Fraction { public int a; public int b; public Fraction(int a, int b) { this.a = a; this.b = b; } @Override public boolean equals(Object ff) { Fraction f = (Fraction)ff; return (this.a*f.b == this.b*f.a); } } 
•  » » » » » » 7 years ago, # ^ |   0 Or perhaps BigDecimal (seeing how this is Java code)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I calculated the slope of the line (y-tY)/(x-tX) and stored it in a map. In the end I just print the size of the map. Can anyone help me with the complexity of this?
•  » » » 7 years ago, # ^ |   +1 I guess in the worst case it would be O(N*logN) as you have to insert N different slopes in worst case, and each insertion would take at most logN time.
•  » » 7 years ago, # ^ |   +1 I counted the number of differents tans, but I got WA on test 8. Anyway, what is the test 8?
•  » » » 7 years ago, # ^ |   +1 ( area == 0 ) this is my solution which WA on test 8 ( area < 0.00001 ) this AC
•  » » 7 years ago, # ^ |   +2 you choose x1 y1 one point and erase it and ans++ then erase which point on line x,y to x1,y1if which points on line erase it
•  » » 7 years ago, # ^ |   +1 I sorted the points by their slope with (x0,y0) and then compared p[i] and p[i-1] using (p[i].y-y0)*(p[i-1].x-x0) == (p[i-1].y-y0)*(p[i].x-x0). If False, increment the number of shots.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I also counted number of unique slopes with a c++ stl set (9839367). It got WA. But surprisingly, replacing scanf with cin got AC !!!Can somebody explain what's here:
•  » » » 7 years ago, # ^ |   0 Guys, its magic I just move declaration of set at WA code to main scope and got right answerCodeFull 8 testWTF?Seems like that this magic feature forks only under MinGw G++ 4.8 and 4.9 (at Ms works fine) In my Linux machine with g++ 4.9 with same compile keys it works fine.Can someone make disasembly of this code(dont have win machine with Mingw right now) or explain ?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Yes, seems magical. Did spent quite some time yesterday. Didn't disassemble as could not produce on local. I did played around quite some using the "custom invocation" of the code forces and have noticed the following(not sure how relevant they are). The problem seems to be, the set is counting some "similar" doubles as different. the results produce using scanf is always higher than what it should result from cin(which we think is right) If I change to float the behaviour is same for cin and scanf. If I use iterator and simply iterate over the slopes set before the calling cout<
•  » » » » » 7 years ago, # ^ |   +1 I think this may be the answer: https://isocpp.org/wiki/faq/newbie#floating-point-arith2
•  » » » » » » 7 years ago, # ^ |   0 Yes, something like this might happened. Thank you for a nice link.
•  » » 7 years ago, # ^ |   +1 For each query string s with length L, there are 2L possible variants (i.e. replace each character by the other 2, and since you can do this only once, there are 2L such possibilities). You need an efficient data structure to check whether the variants are in one of N strings. I think using trie is sufficient enough.
•  » » 7 years ago, # ^ |   +2 I use set in C++ to save n string in set S. After that, with string i in m string query, consider position j, we have string x = s and set x[j] = {'a','b','c' \ x[j] != s[j]}. You can find x in set S in O(log(N)). I think it ok because The total length of lines in the input doesn't exceed 6·10^5
•  » » » 7 years ago, # ^ |   0 well, i solve it with map (as set) and i couldn't submit it in 2 seconds :(((((
•  » » » 7 years ago, # ^ |   0 "You can find x in set S in O(log(N)) " Not true. Comparing two strings needs O(length(x)) if they have a very long common prefix, so it's O(length(x)log(N)). Consider this case: 1 1 aaa...aa aaa...ab (The first consists of 300000 'a' and the second consists of 299999 'a' and one 'b')
•  » » 7 years ago, # ^ |   0 you make a robin-karp(hashing) all strings of the dictionary but with a different letter at each step ( if str[i]=='a' you get 'b' and 'c') and you insert this value in a hash at each step... and for queries you make a classic robin-karp at string Q and check if this value is in hash... You should double hashing for safety(two different bases and two different MOD)
•  » » 7 years ago, # ^ |   0 I'm not sure if it's correct solution, but you can try to do it with hashing. For each n strings, calculate their hashes without each single letter. Next, do the same with strings from query but this time if any hash of ith string existed before, then answer is "YES" otherwise answer is "NO". There might be some problems, when some strings are equal, but it's not that hard to deal with.
•  » » 7 years ago, # ^ |   0 let's define that: a is number of character 'a' b is number of character 'b' c is number of character 'c' we need to find out at least one element in this set: { [a — 1][b + 1][c], [a — 1][b][c + 1], [a][b — 1][c + 1], [a + 1][b — 1][c], [a + 1][b][c — 1], [a][b + 1][c — 1] } and compare them with string t to satisfied the condition! we should use map(or set) to save the input string with [a][b][c]. I think it could process in 3 seconds :D !
•  » » » 7 years ago, # ^ |   0 I think that is wrong, check this test case: 1 1 caaa aaabthe answer is NO
 » 7 years ago, # | ← Rev. 2 →   0 4 unrated handle spotted the top 5 in current standing! They're unpredictably good o.OUPD: In final standing the number decreased become two and both of them are the top 2! Fast system testing by the way.
 » 7 years ago, # |   0 To solve problem C, Is "c++ STL set" just enough?
•  » » 7 years ago, # ^ |   +1 I think it's not, I have used hashing to solve it. BTW, during the contest I wanted to hack a solution with set, but when I tried to send the test it was loading for a while and then nothing — I had to try again and then happened the same. If it turns out that set isn't enough I will be kinda sad :D
•  » » 7 years ago, # ^ |   +1 Unfortunately for me,set is not enough. I passed pretests,but in test 20 I got Time Limit.
 » 7 years ago, # |   +3 I've used unordered_map in problem C, but I've got hacked. What could be the problem?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +6 The time complexity of your code is O(n^2) in the worst case. I used a test with two arbitrary strings of length 3*10^5 to hack your solution.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 I got TLE in test 28 :( .. my time complexity is O(m * l * log(n)) where, l is length of string in each query. m,n are from problem statement. Can anyone explain how this doesn't run in the time limits? Upd: (m*l)<=6*10^5 (from statement) and log n cannot exceed 18
•  » » » » 7 years ago, # ^ |   0 The time complexity of your solution is not O(m * l * log(n)). Just consider the input that consists of two string: each of them is a letter 'a' repeated 3 * 10^5 times. Your solution makes O(n^2) comparisons for this test.
 » 7 years ago, # |   0 i am submitting div2 3rd ..but its not showing me the case i m wrong on...!!!!
 » 7 years ago, # |   +5 I am very sad about problem D. This is my code in contest and this is my code after contest. They different exactly one positionL = 0 and L = 1. If I have 10s to think that, then I can accept problem D and my standing not low.
 » 7 years ago, # | ← Rev. 2 →   -8 Finally, top 10 for me!!! :D
•  » » 7 years ago, # ^ |   0 I'm the pathetic No.11 QuQ...
 » 7 years ago, # |   +5 I've used Hashing to solve C. Here's my code 9849480. It failed on the test #27. It's "..." testcase. What's wrong with my code?
•  » » 7 years ago, # ^ |   0 Collision?
•  » » » 7 years ago, # ^ |   0 Maybe...
•  » » 7 years ago, # ^ |   0 WA on same case :(
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 My hashing has collision. I add checking function for 2 strings when their hashes are the same and it became accepted!
 » 7 years ago, # |   +11 Problem A , in my opinion has a very ambiguous problem statement what is the answer to:- 90 90 or 9?
•  » » 7 years ago, # ^ |   -12 1<=X<=10^18The number shouldn't contain leading zeroes.
•  » » » 7 years ago, # ^ |   +7 My point is, they should have explicitly mentioned whether the number should not have leading zeroes before printing the answer, or during computation.
•  » » 7 years ago, # ^ |   -13 Read the problem statement. You should not have a zero at starting index after performing inversions. 9 is not allowed as it is actually "09", which has trailing zeroes
•  » » 7 years ago, # ^ |   +2 I asked author what could be the answer for 9 as it was ambiguous and he said "No comments" -_-'
•  » » » 7 years ago, # ^ |   0 zero is not positive number
 » 7 years ago, # |   +1 ML in problem C! :(
 » 7 years ago, # |   +1 I got MLE on problem C at #19. I solved the problem using a Trie. Can anyone have a look on my submission, please?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 I am stuck at MLE, too. this solution seems to use Trie but does not cause MLE... I don't know why, though...
•  » » » 7 years ago, # ^ |   +1 The solution is embarrassingly similar to mine. Yet i get MLE. WOW! :-)
•  » » » 7 years ago, # ^ |   +1 That is really strange my submissions in practise is also giving MLE on test #19.
•  » » 7 years ago, # ^ |   +2 In your query function, you are passing the whole string and doing recursion. So each time you call query, the whole string will be copied and this increases the memory as well as the time. So I think if you just pass the string by reference string& s instead of string s it might resolve the MLE problem.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 thanku, my solution got AC after passing the string by refrence.was stuck with MLE for a long time :)
 » 7 years ago, # |   +2 Can someone explain the algorithm behind this code: http://codeforces.com/contest/514/submission/9850107
•  » » 7 years ago, # ^ | ← Rev. 4 →   +9 It's a technique which can be used to find max(a[i..j]) when we have queries of increasing i and js. However the code given by you is not that efficient. Take a look at this submission: We can use a C++ 'deque' to answer all the queries in a total of O(n) time.It's lengthy to explain why the algorithm works (after all it's not too complicated), but the whole operation is expressed as follow: Everytime we increase j (a.k.a push a[j] into processing) we remove deque.back() while it's smaller than a[j], then deque.push_back(a[j]). Everytime we increase i (a.k.a pop a[i] from processing) we remove deque.front() from the deque if deque.front() is a[i]. The answer for each i..j query is always deque.front(). In order to limit the sum, each time we increase j (process the next element), we increase i until {sum} ≤ k
•  » » » 7 years ago, # ^ |   +3 Thanks much for the algo, it's really simple. In step of increasing j you forgot to push_back(a[j]).
 » 7 years ago, # |   +14 In my opinion Problem A description was not clear.For input 90 output should be 9 according to problem statement but test data says answer is 90."Length of output number must be equal to length of input number" this single line of statement should have been added.
•  » » 7 years ago, # ^ |   0 I also agree with you and got 2 WA on A
•  » » 7 years ago, # ^ |   -6 Nope. "The decimal representation of the final number shouldn't start with a zero."
•  » » » 7 years ago, # ^ |   +3 You could've assumed that you just had to remove the leading zero.. It's not clear...
•  » » » » 7 years ago, # ^ |   0 You can't assume things in a programming contest.
 » 7 years ago, # |   0 Any deterministic solution for C?
•  » » 7 years ago, # ^ |   +5 I solve it using trie, created a trie for each different length of strings and brute-forced to check if there was a string in the respective trie in each query.http://codeforces.com/contest/514/submission/9843858
 » 7 years ago, # |   0 For problem C,why people get TLE in test #19?Suppose,this solution
•  » » 7 years ago, # ^ |   +1 O(3 ^ len)
•  » » » 7 years ago, # ^ |   0 which solution will pass? How to optimize it?
•  » » » » 7 years ago, # ^ |   0 You can use Trie data structure .... My code for problem C : http://codeforces.com/contest/514/submission/9843731Hope , this will clear your concept about Tire .
 » 7 years ago, # |   +13 Why is rating update taking so long?
•  » » 7 years ago, # ^ |   0 Even systest is freezed in the end for some reason...
•  » » 7 years ago, # ^ |   +1 Updated:)
 » 7 years ago, # |   0 I can't find my mistake about C problem, I used hash with unsigned long longthis is my soution: 9844038Is there any problem if I substract from unsigned long long?This is another similar solution, he used two hash, but I'm sure colisions is not my mistake ...somebody?9836207
•  » » 7 years ago, # ^ |   +3
 » 7 years ago, # | ← Rev. 2 →   0 Sorry. Got the mistake.
 » 7 years ago, # |   +1 I am sad I took TLE in C using set-stl,but I am happy because I achieved my first goal that was blue. Now it is div1. I hope to achieve that soon :D. I say that,because I want gray-green users that with "correct" practise everyone is able to achieve everything,and never give up.
 » 7 years ago, # |   0 I am facing a problem. My solution #9848758 to the problem C) Watto and Mechanism is giving correct output for the given pretest case — 2 3 aaaaa acacaca aabaa ccacacc caaacBut, it is showing incorrect output on submitting to codeforces. Please check my submission and help me know why there is difference in results?
 » 7 years ago, # |   0 Guys is there anyone who could help me understand why my submission gives wrong answer in test case #6? By my calculation the output kills 3 droids even though checker comment states my solution kills only 2 of them. Any help is greatly appreciated.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 "How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?"You have been destroyed 1, 3 and 4th droid, so your sequence has length 2. In the correct answer, 2, 3 and 4th droid is destroyed, so the sequence has — better — length 3.Word 'consecutive' is the key.P. S. Sorry for my english :)
 » 7 years ago, # |   0 Why do I get MLE for problem D? http://codeforces.com/contest/514/submission/9850749I have used segment tree so 4*N*5 memory, plus one more array of N*5 (both int). As N is just 100000, this should not exceed 256MB memory limit.
•  » » 7 years ago, # ^ |   0 I also did segment tree and passed. Maybe you can take a look. 9865631
•  » » » 7 years ago, # ^ |   0 Yeah, I got it later. I am creating 2 new arrays p,q in every call to query. This must be adding up to the memory as the arrays must get stored in the recursion stack. (Not sure, but I think this may have been the cause). When I removed that part, and instead passed an array to the query function, I got my solution to pass. http://codeforces.com/contest/514/submission/9858833. Anyways, thanks for your reply! :)
 » 7 years ago, # |   +17 My 2 cents, since everyone writing about problem C seems to have tried hashing:The similarity condition imposed is Hamming distance = 1. This is a metric space and can be solved with any of the metric tree structures. I used a BK-tree, and I got AC.
•  » » 7 years ago, # ^ |   0 Your solution is interesting. Can you explain your solution ??
 » 7 years ago, # |   +142 no one can reach real coders (Even cheaters!)
•  » » 7 years ago, # ^ |   0 How he managed to get the solutions before starting of the contest ??
•  » » » 7 years ago, # ^ |   +4 See that '00:28' near his handle? It means he's a virtual contestant (submitted the solutions after the contest finished).
•  » » » 7 years ago, # ^ |   +3 That's virtual contest. I think he first took 5 submissins which passed all tests, started virtual contest and submitted them on the first minute.
 » 7 years ago, # |   +8 When editorial is going to come? It will be interesting to see author's solutions to these problems :)
•  » » 7 years ago, # ^ |   +12 I'm working on it.
•  » » 7 years ago, # ^ |   0 Done.
 » 7 years ago, # |   +12 Still waiting for jury to start upsolving... :/
 » 7 years ago, # |   0 How could always the new comers be in the top list in division 2 ?!!!
•  » » 7 years ago, # ^ |   +3 They are usually Div 1 coders that make new accounts.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Doesn't that affect others ratings :( !!? They can easily compete in offline mode. Why would they need to have another account..They are already div1 coder !!!
 » 7 years ago, # |   0 Is O(M*N*log^2(N)) using segment tree supposed to TLE for problem D ?
•  » » 7 years ago, # ^ |   0 No.
 » 7 years ago, # |   +31 Rebryk, I think data set of problem C ( 514C - Watto and Mechanism ) of today's contest was a little bit weak. Consider this submission: 9852063 which fails the test case: 1 1 abc aa Should not the output be NO? It gives YES instead.Thanks. :)
•  » » 7 years ago, # ^ |   +14 Yes. You're right. It's my fault.
 » 7 years ago, # |   0 became expert for the first time
 » 7 years ago, # |   0 where can i find editorial to the problems .Thanks
 » 7 years ago, # |   0 i am getting memory limit exceeded on test 18 in C... i have used map to do it.. can anyone suggest the reason for this? and also what would be a more memory efficient way of doing this question...
•  » » 7 years ago, # ^ |   +8 When you use if (f[s]) with a new string s, it makes f[s] = 0 and therefore uses |s| additional bytes of memory.Try to use set f and if (f.find(s) != f.end()) instead of map f and if (f[s]).
•  » » » 7 years ago, # ^ |   0 thanks a ton :D that was a new thing for me :D
 » 7 years ago, # |   0 Can somebody please check why I got a run time error on test_25 http://codeforces.com/contest/514/submission/9848840I have tried the test case on my computer and it worked.
 » 7 years ago, # |   0 this contest really interesting though i didn't solve any problem. actually i wonder why i can't solve at least problem A, and then i know that because some case (case 8) like this:input :91730629my output : 1230320answer : 91230320in my opinion, i think my answer actually didn't wrong because we could make the minimum positive number by inverting 1st, 3rd, 6th, and 8th character from the input and discard the leading zero. is somebody has the same opinion with me?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 the length of the output should be the same as inputs ! :)
•  » » » 7 years ago, # ^ |   0 really? then i should miss that in the description :) btw, which statement says that?
•  » » » » 7 years ago, # ^ |   +1 It is exactly because the statement never said that you can discard any digit. Which means you can only invert digits but then the result cannot contain leading zero(s).You should not make your own assumptions.
•  » » 7 years ago, # ^ |   +5 Problem description says: "transform the initial number x to the minimum possible positive number by inverting some (possibly, zero) digits". so you can't discard leading zeros,only operation you are allowed to do is invert some (or zero) digits.
•  » » » 7 years ago, # ^ |   0 but, how about the next sentence : "The decimal representation of the final number shouldn't start with a zero." ?i see that as when after we (if need) invert the digits and there are leading zeros, then we should discard those zeros. cmiiw.
 » 7 years ago, # | ← Rev. 2 →   0 I used TRIE in Problem C but perhaps it should be String Hash? Anyway I FST beautifully.
 » 7 years ago, # |   0 I used TRIE in Problem C but perhaps it should be String Hash? Anyway I FST beautifully.
 » 7 years ago, # |   0 Where is editorial???
•  » » 7 years ago, # ^ |   +20 Sorry, I'm a slowpoke
•  » » 7 years ago, # ^ |   0 Done.
•  » » » 7 years ago, # ^ |   0 Good job)
 » 7 years ago, # |   -6 I got AC on 514B - Han Solo and Lazer Gun,but I alos have a question. gun is situated at the point (x0, y0). can stormtrooper at (x0,y0),too ? if so, i think some code maybe got WA。
•  » » 7 years ago, # ^ |   +6 It is guaranteed that no stormtrooper stands at the same point with the gun.
•  » » » 7 years ago, # ^ |   0 sorry,I am too careless，I haven't see the sentence..Thank you for your reminding
 » 7 years ago, # | ← Rev. 2 →   0 I am trying to solve C problem. I see a lot of solutions where there is something like this :for (int i = 0; i < n; i++) { ... for (int j = 0; j < s.length; j++) {where n <= 3*10^5 and s.length <= 6*10^5 , so in worst case it works in 9*10^10 ~ 10^11 . Why it pass ? How can I calculate the worst complexity withing given time limit ?
•  » » 7 years ago, # ^ |   0 if n = 3 * 10^5 s.length can't be 6*10^5, because 6*10^5 in the worst is a sum of all s.length
•  » » » 7 years ago, # ^ |   0 Yes, thank you. I misunderstood problem statement. Anyway, is there any good algorithm to determine the worst complexity withing given time limit ?
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 What does it mean: withing given time limit?Time limit in this problem is 3sec.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 I want to know algorithm with 2 inputs complexity, time limit . The output will be answer YES/NO For example:C = 10^6 T = 1 s => YESC = 10^19 T = 1 s => NO etc
•  » » » » » » 7 years ago, # ^ |   0 1 second on Codeforces is ~ 2 * 10^8
•  » » 7 years ago, # ^ |   0 Total length of all strings in input is 6*10^5, thus, the code you described does 6*10^5 iterations.
•  » » 7 years ago, # ^ |   0 Your solution couldn't even read input if these two loops would TL
 » 7 years ago, # |   0 The problem A has too many traps, and some of them is so boring, such as the fist digit can't be zero. I think it is meaningless......
•  » » 7 years ago, # ^ |   +8 What is/are the other trap(s)?
 » 7 years ago, # |   0 Why does this give TLE for problem C? => http://codeforces.com/contest/514/submission/9853243
 » 7 years ago, # | ← Rev. 2 →   0 In problem C, I did not understand why the hash value of a string will not overflow long long. And if I mod using a 4 digit prime then there should be collisions.Given the clue, "The total length of lines in the input doesn't exceed 6*10^5. Each line consists only of letters 'a', 'b', 'c'.", there can be a string of length 10^5 whose hash value can be huge.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 I used mod 10^16+3 and base 203. Collisions are still possible but have a very low probability. However, there are solutions that do not use hashes, for example: http://codeforces.ru/blog/entry/16394
•  » » » 7 years ago, # ^ |   0 Thanks for the link :)
 » 7 years ago, # |   +1 Hi, somebody else used hash for the problem C?I have WA #6 but I don't know why. Any help would be appreciated! :)http://codeforces.com/contest/514/submission/9860261
•  » » 7 years ago, # ^ |   +2 The string must differ by one char, i.e. here's the test: 1 1 aa aaNO
•  » » » 7 years ago, # ^ |   0 Oh, right... I didn't see that constraint. Thanks a lot!
•  » » » 2 years ago, # ^ |   0 You helped me 5 years in the future 5 years ago. xD
 » 7 years ago, # |   0 For hashing, if I use 101 then I get WA for test case 8 but if I use 257 then it is accepted. Why so?I chose 101 because the ascii value of c 99, hence I thought 101 was enough.
 » 7 years ago, # |   0
 » 7 years ago, # |   0 If you see a passed solution you think is wrong, is there a way to hack it in the practice room?
•  » » 7 years ago, # ^ |   0 NO
•  » » » 7 years ago, # ^ |   0 that's too bad, it would be nice to be able to double-check that your hack was correct, and also keep other people for thinking a wrong solution was actually correct.
 » 7 years ago, # |   0 Codeforces Round #291 (Div. 2) champion ppfdd got AC on problem C.But there is massive hack for his code.While hashing, He converted a,b,c to 0,1,2.So the result for this input: 1 1 abc babc the output generates YES `which definitely WRONG ANSWER.There should have been at least one test case regarding this factor. :3