Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Rebryk's blog

By Rebryk, 5 years ago, translation, ,

## 514A - Chewbaсca and Number

Author: Rebryk

It is obvious that all the digits, which are greater than 4, need to be inverted. The only exception is 9, if it's the first digit.

Complexity:

## 514B - Han Solo and Lazer Gun

Author: Antoniuk

Let's run through every point, where the stormtroopers are situated. If in current point stormtroopers are still alive, let's make a shot and destroy every stormtrooper on the same line with gun and current point.

Points (x 1, y 1), (x 2, y 2), (x 3, y 3) are on the same line, if (x 2 - x 1)(y 3 - y 1) = (x 3 - x 1)(y 2 - y 1).

Complexity:

## 514C - Watto and Mechanism

Author: Rebryk

While adding a string to the set, let's count its polynomial hash and add it to an array. Then let's sort this array. Now, to know the query answer, let's try to change every symbol in the string and check with binary search if its hash can be found in the array (recounting hashes with complexity). If the hash is found in the array, the answer is "YES", otherwise "NO".

Complexity: , where L is total length of all strings.

## 514D - R2D2 and Droid Army

Author: Rebryk

To destroy all the droids on a segment of l to r, we need to make shots, where cnt[i][j] — number of j-type details in i-th droid. Let's support two pointers — on the beginning and on the end of the segment, which we want to destroy all the droids on. If we can destroy droids on current segment, let's increase right border of the segment, otherwise increase left border, updating the answer after every segment change. Let's use a queue in order to find the segment maximum effectively.

Complexity:

## 514E - Darth Vader and Tree

Author: Antoniuk

It's easy to realize that , where dp[i] is number of vertices, which are situated on a distance i from the root, and cnt[j] is number of children, which are situated on a distance j. Answer .

Let the dynamics condition

Let's build a transformation matrix of 101 × 101 size

Now, to move to the next condition, we need to multiply A by B. So, if matrix C = A·B x - 100, then the answer will be situated in the very right cell of this matrix. For x < 100 we'll find the answer using dynamics explained in the beginning.

In order to find B k let's use binary power.

Complexity:

• +23

 » 5 years ago, # | ← Rev. 2 →   +1 In C problem I used set< string >. After for every new word I did the same with you. I was changing each letter and I would try to find if changed word exists in set< string >. I think set's search with binary search has same complexity. Then why mine solution took TLE in 20testcase?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 You must use set< hash >, not set< string >. hash may be an int64.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 Set compares strings using O(min(|s 1|, |s 2|)) time, so the complexity of your solution will be , where |s| is the length of the largest string. It should not pass.
•  » » » 5 years ago, # ^ |   0 Yea,I see you are right. So if I had use a hashing method(e.x Rabin Karp-Rolling Hashing) I could pass all testcases?
•  » » » » 5 years ago, # ^ |   0 Yep. Polynomial hashing will work here, but keep in sandeepmohanty's comment below. More details here
•  » » » » » 5 years ago, # ^ |   +1 Could you give me some details about polynomial hashing? And how to use that in this case? Also, is there no stl hash function for strings in c++? I am new to coding. Thanks.
•  » » » » » » 5 years ago, # ^ |   +3 We can calculate the hash of the string this way: h(s) = s[0] + s[1] * P + s[2] * P 2 + S[3] * P 3 + ... + s[N] * P N. We should do all calculations by some big modulo. P must be not even and approximately equal to the size of the alphabet used. We can store this values in array H, where H i — hash of the first i + 1 symbols.Now the key moment: Hash of substring from i to j will be H ij = s[i] + s[i + 1] * P + s[i + 2] * P 2 + ... + s[j] * P j - 1. So H ij * P i = H 0j - H 0(i - 1), now we can divide it by P i and get the hash of this substring, but we can't divide because we do all calculations by modulo. We can use extended Euclid algorithm for division or use other known trick instead... just multiply by P j - i, if i < j. So we can get a hash of any substring using O(1) time.There're no built-in hashing functions in C++, at least I don't know such.
•  » » » » » » » 5 years ago, # ^ |   0 Thanks a lot. It helps me understand others' code
•  » » » » » » » 5 years ago, # ^ |   0 how i can recounting hashes with O(1) complexity!! MiloserdOFF can u help me :D
•  » » » » » » » » 5 years ago, # ^ |   0 Just read my previous answer more carefully. To get the hash H ij of substring of s from i to j we need to substract H i - 1 from H j and then multiply the result by P j - i if i < j (otherwise by P i - j)
•  » » » » » » » » » 5 years ago, # ^ |   0 can you please explain the code??? plzzzzzz....
•  » » » » » » 5 years ago, # ^ |   +1 C++, starting with C++11 has built-in hash function for many standard types. However, its exact behaviour is unspecified, so for example if one character of a string changed, you can't recalculate its hash in O(1).
•  » » » » » » » 5 years ago, # ^ |   0 Yes,you are right. I use this function but I get TLE on test 19.
•  » » » » » 4 years ago, # ^ |   0 Hey miloseroff, there is just one issue i am not getting why this hashing is working with 3 and 257 only and not any other prime number, as i can see the soln, like 5 or 7 11 etc, please i am scratching my brains
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 There ans comparisons in set < string > , which take O(n) and the query of set < string > take O(len ^ 2 * log n) , not O(log n) , as set < int >
 » 5 years ago, # |   0 Complexity of problem E will be , as 1013 is a constant, that should not be counted in big O notation. Although we should keep that 1013 in mind :)
•  » » 5 years ago, # ^ |   +22 Just because we did not call it with a lowercase letter it does not means it is a constant. If author was using 109 instead of x, i think you would say complexity is O(1), would not you?.
•  » » » 5 years ago, # ^ |   0 Hell yes. Please, read this: https://en.wikipedia.org/wiki/Big_O_notation
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +13 Then lets generalize the problem to let m = 101; now the complexity is . Happy?
•  » » » » » 5 years ago, # ^ |   0 To be completely precise, it is .
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 Everyone here understands the theory, it's after understanding the theory can people use shorthands. Are you going to be upset that someone uses u = x, dv = e^x dx while integrating by parts xe^x? No, because they get it, they know dv and dx aren't differentials because differentials aren't rigorous. That doesn't justify using a more cumbersome notation if a shorthand works perfectly fine.Every algorithm we ever write on CF will always be O(1), since it's always capped at MAX_INT or MAX_LONG. But you'd have to be ridiculous to expect them to write O(1) for the time complexity of every algorithm.Or, even if you ignore the 2^32 and 2^64 limits and consider the algorithms from a theoretical perspective with infinite memory, they're still all wrong. Because even addition is O(n), and multiplication is O(nlognloglogn) at best.
 » 5 years ago, # |   +20 Theoretically, anti-hash test cases can be generated for any reasonable hash function. Hence, hashing should never be the intended solution for a task in my opinion. Sad to see something like this happen in codeforces. :(
•  » » 5 years ago, # ^ |   0 I didnt really undestand what you mean,so why you believe that hashing should be never an intended solution for a task?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +8 Because the probability that author's solution will produce the correct output on any custom test case is always less than 1 (theoretically). So, basically its not 100% correct.
•  » » » » 5 years ago, # ^ |   0 I see.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 (deleted)
•  » » 5 years ago, # ^ | ← Rev. 4 →   +9 Assume that you have a randomized solution which fails with probability 10 - 50 — you should be familiar with such problems and such solutions from ACM contests, it is a common practice to do some stuff like "let's try some magic for some random permutation of input 1000000 times, let's pick some random elements, let's move in some random direction...". And given problem either have no exact solution for given constants, or this solution is extremely complicated. In this case author should not give this problem at all? Because it have no solution or those cheaters will solve it with wrong solution instead of complicated but correct one?Now let's make your hashing solution non-deterministic. Simplest way to do it — by picking constants for your hashing function using random. Maybe it is still a bad idea to ignore this 10 - 50 risk when you are running space expedition, but for ACM contests it sounds OK. At least for me. Maybe just because I am already used to such problems. Once again, you may not like such problems for some reasons (like that analogy with space expedition); but Petr, Gassa, Burunduk1 and lot of other authors are often using such ideas in their contests, and usually feedback for problems with intended randomized solutions is positive — and I guess they would stop doing it in case most contestants does not like this stuff.
•  » » » 5 years ago, # ^ |   +1 ACM styled contests are totally different because there your solution need not be 100% correct to affect the results. But here, if you submit a solution using hashing, there is always some probability that it'll fail system tests and there is nothing you can do about that (unlike in ICPC where you can modify your hash function until it passes). The biggest risk in codeforces is that if someone tries to hack a solution and gives an input to which the author's solution produces incorrect output then that's not good. What I am saying is that problems like these are fine but the solution against whose outputs our outputs are checked should produce correct outputs for all the inputs that is possible to get in the contest. In an ACM styled contest, these inputs are just the system tests but in Codeforces/Topcoder, since hacking is allowed, these include all possible inputs. Hence this is technically not correct.Of course randomized solutions are many a times much cooler than their deterministic counterparts, but they should not be given in Codeforces/Topcoder as intended solutions.
•  » » » » 5 years ago, # ^ |   +27 Well, in ACM you are also risking — sometimes 20 additional minutes of penalty have same cost as failed problem at CodeForces.But now I finally got your point, thank you for explanation. I thought about the fact that author can check correctness of his cases using slow but correct solution, but totally forgot about hacks. You are right about this part:)I just assumed that author uses some correct solution (like one with trie) for checking hacks (even if he didn't mentioned it in editorial). Long time ago, in Round #109 (prepared by Endagorion) author's solution for one of the problems (154C - Double Profiles) was using hashes, and it was discussed that it's bad idea (for reasons which you mentioned here). Probably Rebryk should also describe safe solution without hashes in his editorial to make this part clear :) And I agree that if hashing was used to get correct answers for hacks, instead of some N*sqrt(N) (or other fast&safe) solution — then it was really author's fault.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +5 The biggest risk in codeforces is that if someone tries to hack a >solution and gives an input to which the author's solution produces >incorrect output then that's not good. The problem is that everyone is using incorrect hashing algorithms (e.g, from here (http://e-maxx.ru/algo/string_hashes ) which may indeed produce incorrect results. I agree that such algorithms should not be used in author's solutions (and, probably, anywhere else).A proper implemented hashing algorithm is always correct, it just has a probability of taking more time than expected (not necessarily much more). It should be allowed for author's solution to run for more than time limit. Even in case some hack suddenly makes author's solution run much more than expected, it be easily detectable. The probability of such a hack is negligible though, if, again, a proper implementation is used.
•  » » 5 years ago, # ^ |   0 Agreed. always expecting a better solution with certainty.(without any possibility of making mistakes.
•  » » 5 years ago, # ^ |   0 How to find anti-hash test case for H = (H * p + s[i]) % q ?
 » 5 years ago, # |   +4 B is easy to solve in O(n) time. Algorithm : Move gun to (0,0) and each points according to this. Calculate tangens of each point and add to set. http://codeforces.ru/contest/514/submission/9857015
•  » » 5 years ago, # ^ |   0 set works O(log), so it's NlogN
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 hashset works in O(1) in java , because it uses hashmap internally. Of course, if hashcode is implemented correctly
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Is there a way to do it in O(n) in C++?
•  » » » 5 years ago, # ^ |   +5 unordered_set — insert works in O(1) on average.
•  » » 5 years ago, # ^ |   0 Putting doubles into set you're just waiting for the precision problems.
•  » » 3 years ago, # ^ |   0 27066819 Can you please explain what is wrong with this solution.
•  » » » 12 months ago, # ^ |   0 u r missing the case for y=y0,its storing -0 if x>x0 & 0 if x
 » 5 years ago, # |   +4 Could someone please elaborate on how they are using a queue in problem D to get linear time?
•  » » 5 years ago, # ^ |   +2 First of all, you can implement queue using two stacks. And two pointers algorithm can be implemented with a queue (moving right pointer is equal to adding new element to the end of a queue, moving left pointer is equal to removing front element).For every element of every stack you can maintain maximum value in part of the stack bounded by this element (it is either given element or maximum value in part bounded by element below). This value for top element of a stack will be equal to maximum value in this stack.And maximum in queue will be larger among two values for stacks.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Wow that is really neat!Update: Got AC 9858168. Thanks!
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +1 Implementing your queue in that fashion means your .dequeue() operation is O(k) worst case where k is the number of elements in the stack. So your solution is not linear, but quadratic in the worst case.EDIT: Or I guess each element gets moved from the inbox to the outbox exactly once, so it would still be linear.. My bad!
•  » » » 5 years ago, # ^ |   0 great idea, thanks a lot, now I_Love_Bohdan_Pryshchenko
 » 5 years ago, # |   +1 Is it possible to solve C using prefix tree?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +2 Yes, i solved it using prefix tree. :) You can see my code here: http://codeforces.com/contest/514/submission/9841932
•  » » » 7 months ago, # ^ |   0 Great solution! Thank you.
 » 5 years ago, # | ← Rev. 2 →   +12 **Problem C — Watto and Mechanism **It can be solved using trie (prefix tree) and dfs in trie.(did a TLE sol. in contest though)You can see the code here: 9857974
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 deleted
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 deleted.
 » 5 years ago, # |   0 In the first question, only thing that the problem stated was answer should not contain extra zeroes. It didn't make it clear that we should not invert the first digit if it is 9. I mean the answer for 95 could be 4 without violating the problem statement.
•  » » 5 years ago, # ^ |   +5 You can invert digit, but you can't delete digit. So 95 cannot be converted into 4, only to 04, but it violates the statement.
 » 5 years ago, # |   0 In the problem C , I was using set for storing the input strings. Now if I do a find operation with the query strings, what would be the time complexity of single query operation ? (with the total length of query lines as large as 6 * 10^5 ) — O(log n) or O(L log n) or something else ?And how would the set of strings compare any two strings — char by char or using some hash function?
•  » » 5 years ago, # ^ | ← Rev. 4 →   +1 For the first question, the complexity is O(Llogn)... Because in the set(T is a kind of type), we should give the way to compare two Ts, which means we should provide a function like bool operator<(const T&a,const T&b)const; However, the comparing function between two string is provided by #include and it is O(L)And the second question, in order to compare correctly, the comparing function provided is comparing char by char.
•  » » » 5 years ago, # ^ |   0 Thanks a lot mathlover for the answer.
•  » » » 5 years ago, # ^ |   0 in order to compare correctly, the comparing function provided is comparing char by char.Is it literally char by char? I made this hacking attempt yesterday — for given pair of strings, each of length 100000 , provided solution will twice compare pair of strings with lcp==0, twice compare pair of strings with lcp==1 — and so on, up to 99999. It gives us almost 10^10 operations in terms of char by char. But this solution works in 1.6s — a bit fast for 10^10 operations. Isn't there some block comparison used to speed up running over lcp?
•  » » » » 5 years ago, # ^ |   0 I test your hack case and the code in my computer. I find that it cost 9 seconds in my computer! So I think the Online-Judge in Codeforces is very very fast.
•  » » » » » 5 years ago, # ^ |   0 This code costs only about 0.7s in my computer. The most strange thing is that, the time cost by string comparing is 0.00% in all running time according to a gprof analysis. I think there must be some strange optimization in GNU libstdc++.
 » 5 years ago, # |   0 I can not understand, why hash in C is full solution. As far as I can see 3^(6*10^5) is larger than 2^64, and hash is not unique. Moreover, I got full points writing prefix tree Can you prove me?.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I think a prefix tree can be considered as a set of string(if we add a counter, it can be a multiset or map), and it can find whether a string is in the set(prefix tree) in O(length). I think it is correct.
•  » » 5 years ago, # ^ |   +8 Most hashes are certainly not unique or why do we use hash? If C is in ACM/ICPC, you can simply choose a prime other than 3 because the problem setter does not know which prime you used so he can not construct data against you. He can only guess some contestants will choose 3 and build some data to make them failed. However, in Codeforces, hackers can construct data against a solution. So you have to compare two strings themselves when the hash of them are the same. However the probability of two different strings have same hash is low so only a few strings will be compared. So, the hash helped you to evade TLE.
•  » » » 5 years ago, # ^ |   0 It is very strange for me to see the solution based on hashes as the official solution on such a competition as codeforces, especially when another solution, not involving hashes is possible, because a participant does not see if his solution is fully accepted or not during the contest. That is why i expect that prefix tree solution should be somehow much worse, but I do not see the reason.
•  » » » » 5 years ago, # ^ |   0 Yes, its very strange indeed. There is a possibility that a legitimate hacking attempt of some user failed because the author's solution also produced wrong output.
•  » » » 5 years ago, # ^ |   +5 I think you can make the prime in hash be a variable P. Then you prepare hundreds of different primes and make a table of them, when the program begins, it choose P randomly from the table. I think no one can hack you, or your program has some bugs out of hash.
•  » » » » 5 years ago, # ^ |   0 Another thing we have to consider: in this problem if we regard character 'a' as number 0, then a, aa, aaa... will have same hash 0, whatever P. So it's better to regard 'a', 'b', 'c' as 1, 2, 3.
•  » » » » 5 years ago, # ^ |   0 Is it really so important that P in hash is prime? I think you can choose any random P in some segment.
•  » » 5 years ago, # ^ |   0 Can you please explain your check() function?
 » 5 years ago, # |   0 problem b also can solved by o(nlogn) with save the y/x
 » 5 years ago, # | ← Rev. 3 →   0 Can Someone elaborate on problem C? How to hash the strings. I am not able to get it
•  » » 5 years ago, # ^ |   +4 Let every letter has value ('a' — 0, 'b' — 1, 'c' — 2), and there is a KEY (in this case suitable to take KEY=3, usually it is prime number greater than size of alphabets(3)) than simplest hash of the string s[0], s[1] ... is value (s[0] * KEY ^ 0 + s[1] * KEY ^ 1 ...) modulo 2^64, where s[i] — value of the letter on i-th position
•  » » » 5 years ago, # ^ |   0 Ok so After doing this I just insert them in set and for each query I use the find() function to find whether that particular hash is in set or not correct?
•  » » » 5 years ago, # ^ |   0 I Implemented the above solution but getting wa on test 6 any suggestions? http://codeforces.com/contest/514/submission/9879346
•  » » » 10 months ago, # ^ |   0 I don't think it's correct. Since you assign $'a'$ to $0$, that means that the strings $bc, bca, bcaa, bcaa, ...$ will all have the same hashes. In other words, in your case, the no. of trailing $a$'s don't matter. To avoid this, all the chars must be assigned to non-$0$ values.
•  » » » » 10 months ago, # ^ |   0 also modulo 2^64 is not that good idea: https://codeforces.com/blog/entry/4898
•  » » » » » 10 months ago, # ^ |   0 I have recently solved some problems on hashing and I realized that even modulo $10^9 + 7$ is also not a good idea. Hashing with a fixed base and modulus can be hacked. So, I've started using double hashing now, since it's very difficult to hack double hashing solutions.
 » 5 years ago, # |   0 I think the complexity of problem C is O(26*L*log(n)). Is that true?
•  » » 5 years ago, # ^ |   +5 Size of alphabet is only 3, not 26. So, O(3*L*log(n)) ~ O(L*log(n)) is enough. Correct me, if I am not right.
•  » » » 2 months ago, # ^ |   0 Thats correct. Still that gives TLE on test 28
 » 5 years ago, # |   +3 can anyone explain the solution to problem E.I cant understand the editorial's solution
 » 5 years ago, # |   +2 for problem 'A', nowhere it was written that the final answer should be of the same length of the original number. Disappointed........
•  » » 5 years ago, # ^ |   0 "The number shouldn't contain leading zeroes."
 » 5 years ago, # | ← Rev. 2 →   +9 How is it that Trie solution, with DFS on Trie, passing for C? Won't DFS check the whole input tree and the complexity will be O(M.(Sum of length of input strings)), which can be very slow?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 No,It will only check for 3*(Size of word to be checked) in worst case.You can refer my code for clarification : 9857974i.e.,In the dfs recursion i've checked:if(i==s.size())if(x && cnt==1)return true;elsereturn false;
•  » » » 5 years ago, # ^ |   0 I guess complexity is:Max(building trie, 3 x Σ(Size of m words) )Which is O(max(n,Σ(Size of m words)))Which can be max 3 * 6 * 10^5 operations
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 no, it's N * sqrt(N)let A = sqrt(N);long words more than A -> count of them < A.short words lower than A.so copmplexity is N * A
 » 5 years ago, # | ← Rev. 3 →   0 Deleted - PS. It was too dumb of a question. The limits are too big even for an iterative dp.
 » 5 years ago, # | ← Rev. 2 →   0 Can anybody tell what is the complexity of DFS solution for problem C? I agree with iwtbaRTlAE.
•  » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 The constructed trie can contain atmost nlog3(n) nodes. For every query, we would traverse the whole tree in worst case. Then the complexity will be O(nlog3(n) * m). That would go above 10^10. That should give TLE right?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 No, i break off the function if there are more than 2 mismatches as well...So if there are more than 2 mismatches, that dfs is dropped, else it will go only till the size of string.I figured out that it will pass in time by trying to disprove that it won't. (couldn't really find a case)
•  » » » » 5 years ago, # ^ |   0 Suppose we're trying to construct max test for problem. Let's define L as length of strings in input.Let's take query strings as "aaa...aaa".To make DFS run as deep as possible we need it not to meet two or more different characters till it reaches last character of the string, so DFS could scan whole tree. We can change only one character in any position. And we need last character to be different from 'a' not to interrupt DFS. Then we have 2 * 2 * (L — 1) strings satisfying these constraints or ~ 4 * L.Then total number of operations is 4 * L * L * (Total — 4 * L * L) / L where 4 * L * L is number of characters of strings for trie and (Total — 4 * L * L) / L is number of queries for strings of length L.To maximize this expression we need 4 * L * L to be equal to Total / 2. Notice that total number of characters in input is 6*10^5. Having this we can estimate total number of operations and see that it's about ~ 3 * 10^8.
•  » » » » » 5 years ago, # ^ |   0 Really nice! Thank you
•  » » » » » 3 years ago, # ^ |   0 How did you obtain 2*2*(L — 1) strings? Shouldn't it be 25 * 25 * (L — 1), since we can choose any character from the first L — 1 positions and replace it with any character other than a (which is one from bcd...yz).
 » 5 years ago, # |   0 I'm new to Hash Can someone teach me how to avoid HashValue overflow or make hashValue still work? My submission looks like my hash will overflow in some case and then get wrong ex: 1 1 bccbccababcaacb bbcbccababcaacb
•  » » 5 years ago, # ^ |   +3 newfp -= Pow*(p[j]-'a'+1)%PRIME_Q;newfp += Pow*(k-'a'+1)%PRIME_Q;After the first operation newfp can become negative (too large if you use unsigned type) and the second one might not return it to "positive" numbers.Generally, if you want to subtract a from b modulo m, it's advised do it the following way: a = ((a - b) % m + m) % m;.
•  » » » 5 years ago, # ^ |   0 I got it ! thank you so much
 » 5 years ago, # |   0 Let's use a queue in order to find the segment maximum effectively？ how to use the queue？Could you tell me
•  » » 5 years ago, # ^ |   0 When you increase the right end of the segment, you add the corresponding number to the queue; when you increase the left end, you remove the number. We need a way to maintain the maximum of all numbers in the queue. Let's first do that for a stack. That's easy: we just maintain a parallel stack that contains current maximum. Now recall that a queue can be implemented with 2 stacks. If those stacks maintain their maximums, we calculate the maximum value in the queue as the max of the two maximums. Submission: 9842348
•  » » » 5 years ago, # ^ |   0 Thanks for you help.Before that I can only solve the problem by segment tree...
•  » » 5 years ago, # ^ |   0 Use doubly-ended queue (Linked list) here. Whenever you have to insert a number, remove all the numbers from the back until you find a number that is more than it. After that, insert the number. In this way, you'll have a queue with numbers sorted in decreasing order from front to back.
•  » » » 5 years ago, # ^ |   0 Oh!thanks!Now I know I can keep the queue monotonicity.
 » 5 years ago, # | ← Rev. 2 →   0 Problem B can be solved in O( N logN ) instead of O(N^2) by creating a set of slopes, for N slopes, and inserting :-1* slope if slope== -std::numeric_limits::infinity() , where std::numeric_limits::infinity() is a special double value reserved for infinity in C++, and is the result of division of positive number by zero.else insert the slope , whether it is a normal value or positive infinity.This is because slope of -ve infinity and positive infinity both refer to same line of equationx=x0The solution is the size of the set.see my submission: 9876315 and stack overflow: Negative infinity
 » 5 years ago, # |   0 Can someone explain to me why my solution for problem C gets TLE on test case 18? thanks! My submission
•  » » 5 years ago, # ^ |   0 Firstly you are computing length again and again using strlen() function inside a loop. Remember that strlen() is O(L). Secondly, you are also computing hashes using getHash() function inside a loop which is again O(L). Third, you are taking array of size 300001 instead of 600001. However the last one is not causing the TLE but Segmentation fault. Look at your corrected submission here
 » 5 years ago, # | ← Rev. 4 →   0 Never Mind, I had a problem in the submission and it is now acceptedMy idea was to not avoid division by zero , as division by zero for floating-point variable is well defined and allowed by the IEEE 754 floating point standard. So I check for negative infinity slope, and change it to positive infinity, as both represent the line parallel to y-axis. The solution is accepted in C++ 9876315 #include #include #include using namespace std; using namespace std; int main() { double n, x0, y0, xi, yi, dy, dx, slope; set shotS; cin >> n >> x0 >> y0; for (int i = 0; i < n; i++) { cin >> xi >> yi; dy = yi - y0; dx = xi - x0; slope = dy / dx; shotS.insert(slope == -std::numeric_limits::infinity() ? -slope : slope); } cout << shotS.size(); } . The solution in Java is now accepted 9880392 import java.math.RoundingMode; import java.util.Scanner; import java.util.TreeSet; public class CodeForces514B_HanSoloAndLazerGun { public static void main(String[] args) { double n, x0, y0, xi, yi, dy, dx, slope; Scanner a = new Scanner(System.in); boolean hasInfinitySlope=false; TreeSet shotS=new TreeSet(); n=a.nextDouble(); x0=a.nextDouble(); y0=a.nextDouble(); for (int i = 0; i < n; i++) { xi=a.nextDouble(); yi=a.nextDouble(); // Division by zero for floating point is allowed, it returns positive infinity or negative infinity dy = yi - y0; dx = xi - x0; slope = dy / dx; // line of slope infinity or negative infinity is parallel to y-axis, same line. // line of slope positive zero or negative zero is parallel to x-axis, same line. // the check for zero is required because while +0.0==-0.0 returns true, //the TreeSet calls Double.equals, Double.equals(+0.0,-0.0) returns false // see http://docs.oracle.com/javase/7/docs/api/java/lang/Double.html . shotS.add(slope==Double.NEGATIVE_INFINITY ? Double.POSITIVE_INFINITY :slope==-0.0? +0.0: slope ); } System.out.print(shotS.size()); } } 
 » 5 years ago, # |   0 Can somebody elaborate solution for E? For me, it escalated too quickly from DP to transformation matrix.
•  » » 5 years ago, # ^ |   0 It may help:Matrix Expo Tutorial
•  » » » 5 years ago, # ^ |   0 Thanks a lot man. It did.
 » 5 years ago, # |   0 In problem A, for input 90909, AC soln gives 10000, shouldn't the right answer be 9 as it is asking for minimum positive number without leading zeroes.
•  » » 5 years ago, # ^ |   0 You cannot delete digits...only invert them
 » 5 years ago, # |   0 Am I the only one who failed D because of binary search over length of segment and increased complexity to N log N. The tags have binary search but my solution didn't pass is it so because of poor complexity or poor implementation?
•  » » 5 years ago, # ^ |   0 I've also solved this problem with N log N algorithm. Got 'Exceed Time Limit' with python implementation, but eventually 'Accepted' with C++.
•  » » » 5 years ago, # ^ |   0 alexander.kolesnikoff: I also tried the segment tree + binary search approach but getting TLE on test case 14. Link to my submission: 11563790. Can you help me finding where I am going wrong. Thanks
•  » » » » 3 weeks ago, # ^ |   0 In problems that require binary search over segments, it is always preferable to use SparseTable (RMQ) over Segment Trees. The problem with latter is that it adds another logarithm factor while querying hence degrading the complexity.Here is my solution with SpareTable implementation: template > struct SparseTable { int n; vector> st; F func; SparseTable () {} SparseTable (const vector& a, const F& f) : func(f) { n = static_cast(a.size()); int maxlg = 32 - __builtin_clz(n); st.resize(maxlg); st[0] = a; for (int j = 1; j < maxlg; j++) { st[j].resize(n - (1 << j) + 1); for (int i = 0; i <= n - (1 << j); i++) { st[j][i] = func(st[j-1][i], st[j-1][i + (1 << (j-1))]); } } } T get (int l, int r) const { int lg = 32 - __builtin_clz(r - l + 1) - 1; return func(st[lg][l], st[lg][r - (1 << lg) + 1]); } }; signed main() { #ifdef READ_FILE freopen("input.txt", "r", stdin); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); int n, m, k; cin >> n >> m >> k; vector> a(m, vector(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cin >> a[j][i]; } vector> st(m); for (int i = 0; i < m; i++) { st[i] = SparseTable(a[i], [&] (int px, int py) { return (px > py)? px: py; }); } vector res(m, 0); int ans = 0; for (int i = 0; i < n; i++) { int lo = i; int hi = n - 1; int mid = lo + (hi - lo) / 2; while (lo <= hi) { long long cur = 0; for (int j = 0; j < m; j++) cur += st[j].get(i, mid); debug(i, lo, hi ,mid, cur); if (cur > k) { hi = mid - 1; } else { lo = mid + 1; if (ans < (mid - i + 1)) { ans = mid - i + 1; for (int j = 0; j < m; j++) res[j] = st[j].get(i, mid); } } mid = lo + (hi - lo) / 2; } } //cout << ans << "\n"; for (auto x : res) cout << x << " "; cout << "\n"; return 0; } 
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 As I can see you have got runtime-error, not time limit. My solution's complexity was O(N**M*log^2 N) because of segment tree(I can code it faster than RMQ) + binary search and it passed.
•  » » » 5 years ago, # ^ |   0 P_Nyagolov: My solution also has the complexity same as yours but I am getting TLE on test case 14. Can you please help me? Solution id: 11563790
 » 5 years ago, # |   0 In problem C , i used "trie" to solve the problem .But it is giving memory limit exceeded.Can i know why ?? Submission id: 10300905
•  » » 4 years ago, # ^ |   0 I had the same problem, there is no need for the string to be in the function parameters I solved it hours ago, my submission: 20196208
 » 5 years ago, # |   0 Can someone please explain solution for D? Why are we using queue in the first place? I understand its a DP based problem but not able to get the solution.
 » 4 years ago, # |   0 plz can any one suggest what should i do i am gettin tle in 19th case also explan how i think my time complexity is O(2*L*log(N)) here is ideone link http://ideone.com/pe1h4Y
 » 19 months ago, # | ← Rev. 2 →   0 Deleted
 » 11 months ago, # | ← Rev. 2 →   0 In Problem C, why not put the hashes in an unordered_map, instead of a set? Expected time of searching for a element in an unordered_map is O(1) while in a set it would be O(logn)
 » 11 months ago, # |   0 https://codeforces.com/contest/514/submission/59140838Why does this soltion fail? It saves all the entry string's hashes in a map, goes through the queries, changes the current string in all possible ways (2*|s|), and checks if a hash of any of the changed strings is saved in the map. P = 5, MOD = (1 << 64)
 » 10 months ago, # |   0 Please someone help using the same technique my solution is failing for test case 7 https://codeforces.com/contest/514/submission/60584041
 » 5 months ago, # |   0
•  » » 3 weeks ago, # ^ |   0 nice work bro! it helped me.