Rebryk's blog

Codeforces Round #291 (Div. 2) Editorial
By Rebryk, 10 years ago, translation, In English

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 (x1, y1), (x2, y2), (x3, y3) are on the same line, if (x2 - x1)(y3 - y1) = (x3 - x1)(y2 - y1).

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·Bx - 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 Bk let's use binary power.

Complexity:

  • Vote: I like it
  • +23
  • Vote: I do not like it

Comments Comments (118)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You must use set< hash >, not set< string >. hash may be an int64.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Set compares strings using O(min(|s1|, |s2|)) time, so the complexity of your solution will be , where |s| is the length of the largest string. It should not pass.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yep. Polynomial hashing will work here, but keep in terribleimposter's comment below. More details here

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            We can calculate the hash of the string this way: h(s) = s[0] + s[1] * P + s[2] * P2 + S[3] * P3 + ... + s[N] * PN. 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 Hi — hash of the first i + 1 symbols.

            Now the key moment: Hash of substring from i to j will be Hij = s[i] + s[i + 1] * P + s[i + 2] * P2 + ... + s[j] * Pj - 1. So Hij * Pi = H0j - H0(i - 1), now we can divide it by Pi 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 Pj - 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks a lot. It helps me understand others' code

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              how i can recounting hashes with O(1) complexity!! miloserd can u help me :D

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Just read my previous answer more carefully. To get the hash Hij of substring of s from i to j we need to substract Hi - 1 from Hj and then multiply the result by Pj - i if i < j (otherwise by Pi - j)

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  can you please explain the code??? plzzzzzz....

                  → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes,you are right. I use this function but I get TLE on test 19.

              → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 >

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B can be solve in O(nlog(n)) just by maping the slops.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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?.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hell yes.

      Please, read this: https://en.wikipedia.org/wiki/Big_O_notation

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +13 Vote: I do not like it

        Then lets generalize the problem to let m = 101; now the complexity is . Happy?

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
10 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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. :(

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didnt really undestand what you mean,so why you believe that hashing should be never an intended solution for a task?

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +27 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed. always expecting a better solution with certainty.(without any possibility of making mistakes.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to find anti-hash test case for H = (H * p + s[i]) % q ?

    → Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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://mirror.codeforces.com/contest/514/submission/9857015

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Could someone please elaborate on how they are using a queue in problem D to get linear time?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Wow that is really neat!

      Update: Got AC 9858168. Thanks!

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      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!

      EDIT2: Tried it myself, it works :)

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      great idea, thanks a lot, now I_Love_Bohdan_Pryshchenko

      → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it possible to solve C using prefix tree?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

**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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem C , I was using set<string> 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?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    For the first question, the complexity is O(Llogn)... Because in the set<T>(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<string> and it is O(L)

    And the second question, in order to compare correctly, the comparing function provided is comparing char by char.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot mathlover for the answer.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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++.

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is it really so important that P in hash is prime? I think you can choose any random P in some segment.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem b also can solved by o(nlogn) with save the y/x

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can Someone elaborate on problem C? How to hash the strings. I am not able to get it

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the complexity of problem C is O(26*L*log(n)). Is that true?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thats correct. Still that gives TLE on test 28

      → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can anyone explain the solution to problem E.I cant understand the editorial's solution

→ Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

for problem 'A', nowhere it was written that the final answer should be of the same length of the original number. Disappointed........

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "The number shouldn't contain leading zeroes."

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No,

    It will only check for 3*(Size of word to be checked) in worst case.

    You can refer my code for clarification : 9857974

    i.e.,

    In the dfs recursion i've checked:

    if(i==s.size())

    if(x && cnt==1)

    return true;

    else

    return false;

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
  • Deleted - PS. It was too dumb of a question. The limits are too big even for an iterative dp.
→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody tell what is the complexity of DFS solution for problem C? I agree with PrakharJain.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check previous comment

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Really nice! Thank you

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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).

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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;.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's use a queue in order to find the segment maximum effectively？ how to use the queue？Could you tell me

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for you help.Before that I can only solve the problem by segment tree...

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh!thanks!Now I know I can keep the queue monotonicity.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me why my solution for problem C gets TLE on test case 18? thanks! My submission

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody elaborate solution for E? For me, it escalated too quickly from DP to transformation matrix.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You cannot delete digits...only invert them

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've also solved this problem with N log N algorithm. Got 'Exceed Time Limit' with python implementation, but eventually 'Accepted' with C++.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 <class T, class F = function<T (const T&, const T&)>>
struct SparseTable {
  int n;
  vector<vector<T>> st;
  F func;

  SparseTable () {}

  SparseTable (const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(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<vector<int>> a(m, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> a[j][i];
  }
  vector<SparseTable<int>> st(m);
  for (int i = 0; i < m; i++) {
    st[i] = SparseTable<int>(a[i], [&] (int px, int py) {
      return (px > py)? px: py;
    });
  }
  vector<int> 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;
}
        → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C , i used "trie" to solve the problem .But it is giving memory limit exceeded.Can i know why ?? Submission id: 10300905

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem C, why not put the hashes in an unordered_map<int, bool>, 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)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/514/submission/59140838

Why 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)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone help using the same technique my solution is failing for test case 7 https://mirror.codeforces.com/contest/514/submission/60584041

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My C solution with Trie https://github.com/joy-mollick/Trie-Data-Structure/blob/master/Codeforces-514C%20-%20Watto%20and%20Mechanism.cpp

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

216571360

problem C can be solved using trie submission: 216571360

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this C problem mush be solved using hashing concept,

    can u help me with it:

    243714293

    what more optimization that can be cone to pass the testcases of problem C: Watto & Mechanism

    Do i need to use two hashes and store them as a pair.

    If done so, im confused about applying binary Search on it to pind the pair of two hash values

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

243714293

Can someone help by telling what more optimization that can be cone to pass the testcases of problem C: Watto & Mechanism

→ Reply