mkrjn99's blog

Manthan, Codefest 16: Editorials
By mkrjn99, history, 9 years ago, In English

Problem A: Ebony Ivory

The problem is to find if there exists a solution to the equation: ax + by = c where x and y are both positive integers. The limits are small enough to try all values of x and correspondingly try if such a y exists. The question can also be solved more efficiently using the fact that an integral solution to this problem exists iff gcd(a, b)|c. We just have to make one more check to ensure a positive integral solution.

Complexity: O(log(min(a, b))

Problem B: A Trivial Problem

We know how to calculate number of zeros in the factorial of a number. For finding the range of numbers having number of zeros equal to a constant, we can use binary search. Though, the limits are small enough to try and find the number of zeros in factorial of all numbers of the given range.

Complexity: O(log(n)2)

Problem C: Spy Syndrome 2

The given encrypted string can be reversed initially. Then dp[i] can be defined as the index at which the next word should start such that the given string can be formed using the given dictionary. Rabin Karp hashing can be used to compute dp[i] efficiently.

Also, care must be taken that in the answer the words have to be printed in the correct casing as they appear in the dictionary.

Complexity: O(n * w) where n is the length of the encrypted string, w is the maximum length of any word in the dictionary.

Problem D: Fibonacci-ish

The key to the solution is that the complete Fibonacci-ish sequence is determined by the first two terms. Another thing to note is that for the given constraints on a[i], the length of the Fibonacci-ish sequence is of logarithmic order (the longest sequence possible under current constraints was of length~90) except for the case where a[i] = a[j] = 0, where the length can become as long as the length of the given sequence. Thus, the case for 0 has to be handled separately.

Complexity: O(n * n * l) where n is the length of the given sequence and l is the length of the longest Fibonacci-ish subsequence.

Problem E: Startup funding

Let us denote the number of visitors in the ith week by v[i] and the revenue in the ith week by r[i].

Let us define z[i] = max(min( 100 * max(v[i...j]), min(c[i...j]))) for all (j >  = i). Note that max(v[i...j]) is an increasing function in j and min(r[i...j]) is a decreasing function in j. Thus, for all i, z[i] can be computed using RMQ sparse table in combination with binary search.

Thus the question reduces to selecting k values randomly from the array z. Let us suppose we select these k values and call the minimum of these values x. Now, x is the random variable whose expected value we need to find. If we sort z in non-decreasing order:

E(X) = (z[1] * C(n - 1, k - 1) + z[2] * C(n - 2, k - 1) + z[3] * C(n - 3, k - 1)....) / (C(n, k))

where C(n, k) is the number of ways of selecting k objects out of n. Since C(n, k) will be big values, we should not compute C(n, k) explicitly and just write them as ratios of the previous terms. Example: C(n - 1, k - 1) / C(n, k) = k / n and so on.

Complexity: O(n * lgn)

Problem F: The Chocolate Spree

The problem boils down to computing the maximum sum of two disjoint weighted paths in a tree (weight is on the nodes not edges). It can be solved applying DP as in the given solution : http://pastebin.com/L8NNLF3f (Thanks to GlebsHP for the solution!)

Complexity: O(n) where n is the number of nodes in the tree.

Problem G: Yash and Trees

Perform an euler tour (basically a post/pre order traversal) of the tree and store it as an array. Now, the nodes of the subtree are stored are part of the array as a subarray (contiguous subsequence). Query Type 2 requires you to essentially answer the number of nodes in the subtree such that their value modulo m is a prime. Since, m ≤ 1000, we can build a segment tree(with lazy propagation) where each node has a bitset, say b where b[i] is on iff a value x exists in the segment represented by that node, such that . The addition operations then are simply reduced to bit-rotation within the bitset of the node.

Complexity: O(n * lgn * f), where n is the cardinality of the vertices of the tree, f is a small factor denoting the time required for conducting bit rotations on a bitset of size 1000.

Problem H: Fibonacci-ish II

The problem can be solved by taking the queries offline and using a square-root decomposition trick popularly called as “Mo’s algorithm”. Apart from that, segment tree(with lazy propagation) has to be maintained for the Fibonacci-ish potential of the elements in the current [l,r] range. The fact used in the segment tree for lazy propagation is:

F(k + 1) * (a1 * F(i) + a2 * F(i + 1)...) + F(k) * (a1 * F(i - 1) + a2 * F(i) + ....) = (a1 * F(i + k) + a2 * F(i + k + 1)....)

Example: Suppose currently the array is [100,400,500,100,300]. Using Mo's algorithm, currently the segment tree is configured for the answer of the segment [3,5]. The segment tree' node [4,5] will store answer=500*F(2)=1000. In general, the node [l1, r1] of segment tree will contain answer for the values in the current range of [l2, r2] of Mo's for the values that have rank in sorted array [l1, r1]. The answer will thus be of the form a1 * F(i) + a2 * F(i + 1).... We maintain an invariant that apart from the answer, it will also store answer for one step back in Fibonacci, i.e., a1 * F(i - 1) + a2 * F(i).... Now, when values are added (or removed) in the segment tree, the segments after the point after which the value is added have to be updated. For this we maintain a lazy count parameter (say k). Thus, when we remove the laziness of the node, we use the above stated formula to remove the laziness in O(1) time. Refer our implementation for details: http://pastebin.com/MbQYtReX

Complexity:

Tutorial of Manthan, Codefest 16
  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (130)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any advice for how to make sure that our hashing solution passes the systests in future contests ? I used a pair hash with constants( b = 31 , 37 and m = 1e9 + 9 , 1e9 + 7) this contest but that was not enough.

Were we also supposed to keep track of the pairs that we have already processed in problem D besides from what's mentioned in the editorial ?

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

    With hashing you can never be so sure. A personal trick I use is storing hashes of different length strings in different sets to reduce probability of collision.

    In D, no need to keep track of the previous pairs, just calculate the next term and see if it is present in the remaining set. It should be ensured that the number of times you use an element should be less than or equal to the number of times the element is present in the given array.

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

      In that case, the cases for D are a bit too strict as my solution got TLE:

      http://codeforces.net/contest/633/submission/16362591

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

        Sure the time limit was too strict. :(

        But just a small piece of advice, instead of using an another map 'used', you could have subtracted the numbers from the actual map 'have' itself. Just push the used numbers in an array 'used'. Later one could simple restore 'have' using 'used'.

        'used' map will result in system calls as it needs to allocate memory every-time for new nodes as u insert elements in it (say malloc/calloc or new) and they are quite costly.

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

      My solution TLE'd on test 99. I changed it to store pairs I already calculated the answer for and it AC'd. Isnt TL a bit too strict here?

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

      My submission is almost same as StoneCold_ — 16362591 and himanshujaju -16364394 but it is taking 904 ms for 99th Test case while in their cases it timed out (>3000 ms).

      Can anyone explain. Why ? (was it because of use of 2 maps or something else ?)

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

        I suspect two maps, since it needs allocation space. Also my constant involved should be lot higher than yours due to multiple map value comparisons in my code.

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

I tried solving C with aho-corasick + weighted job scheduling but got MLE in test case 58. I think this is because in worst case aho-corasick can generate O(m^2) matches when every pattern matches the input string. Am i right?

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

    theoritically yes, I hesitate to use aho corasick yesterday because of that O(m^2) matches, but I just submited it few hours ago and got accepted with speed=265ms and memory=127932 KB

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

    The number of matches isn't too bad, each word has a length of at most 1000, so for any position there are at most 1000 words that match there, giving 107 matches in the worst case, which is quite a lot, but not the worst problem.

    How you build the initial tree is a lot more important. For reference, here's my solution that MLE'd one case later than yours: 16359251, and here's one that got accepted: 16382076 (while admittedly still using a lot of memory).

    You can compare the two solutions to see what I changed, basically, in the earlier version, a node would store all matches at that position, while in the new version I store a single match, and the index of the next vertex that also contains a match. I'm not sure if this will make the performance much worse (I doubt it), but it reduces memory consumption significantly.

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

In problem C, I think the O(N × w) time complexity means to check every character ti in the haystack string and a certain length l — to check if titi + 1... ti + l - 1 matches any words in the dictionary. You can calculate the hash of that string in O(1) time, but is it possible to check if the hash exists in the dictionary in O(1) time?

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

    It is possible if you use a dictionary which uses O(1) operations for insert and delete such as unordered_set

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

There is deterministic solution of problem C without hashing. Just use trie.

Code: 16357979

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

    My solution ( 16364008, 155 ms ) of C without hashing uses another idea: map [length of words] to set of words of this length.

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

      Algiz used similar idea. He had map from length of the string to set of value of hash function.

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

      The only problem is that your solution's complexity is O(n × sumlen).

      For example on test generated by this script your solution makes about 14 × 109 operations. Thanks to fast strcmp it works about 4 seconds on my Macbook Pro, but it is not intended solution.

      #!/usr/bin/env python
n = 10000
print n
print "b" * n
m = 1000
print 2 * m + 1
print "b"
for i in xrange(m):
    print "a" + "b" * i
    print "c" + "b" * i
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are right, my solution would fail, if this test was present in systests.
        That's strange, that max time was 124 ms on systests, so weak set..

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

    Could you elaborate your trie solution a bit, please? I'm not sure if I got it. And, by the way, what is its time complexity?

    Thanks

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

      It's the same idea as the editorial, but instead of looking for hashing values, you will traverse the trie, looking for a word in the dictionary that match with a substring starting from some position.

      Let's say dp(i) =  it's possible from position i. You will traverse the trie from the root, finding the same characters as the string starting from the ith-position. When you reach a node in the trie that represent a word in the dictionary, make the transition (dp(i + k)) where k is the length of the path you've traversed (which is the length of the word you will use).

      The time complexity is the same: O(n * w). For any position, the worst case is using the longest word in the dictionary (maximum: 1000)

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

What was the solution used by checker for hacks in problem C? A deterministic solution with a trie? Or some other deterministic solution? You can't use straightforward hashing because in this case you can't be sure that you'll get correct answer to a given hack (and you can get wrong judge vertict for a hack as a result).

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

Too short explanations. Please atleast provide the solutions according to your editorial.

A bit more explanation needed for problem D.

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

I guess complexity for D should be O(n * n * l) not O(n * lgn * l) ?

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

Auto comment: topic has been updated by mkrjn99 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by mkrjn99 (previous revision, new revision, compare).

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

what is wrong in my solution for problem D : 16373289

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

    Try this: 0 2 -1 1 0 1 1

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

    The logic is wrong and you can't use line if(dp[l1][l2] != -1) return dp[l1][l2];. Maybe before with some other remaining numbers it was possible to build longer suffix starting from l1, l2 but later it will be impossible because needed numbers are used.

    And small counter-test for you. Your code prints 5 (the answer bigger than n) for:

    4
0 1 1 2

    You calculate dp[0][1] = 4 and later you start from 1, 0, 1 and you check dp[0][1].

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

For E it is said:

Thus, for all i, z[i] can be computed using RMQ sparse table in combination with binary search.

Complexity: O(n * lgn)

The complexity should be O(n * log2 n) in this case, shouldn't it?

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

Could someone tell me why my answer is wrong?[submission:16375142]if gcd(a,b)|c,put Yes.

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

Why am I getting TLE for my solution for problem D? http://www.codeforces.com/contest/633/submission/16375958

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

    Your solution is TLE as well as WA.

    TLE reasons: O(N3) complexity, slow I/O using Scanner. WA: Case 0 -1 -1 2

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

Why TLE?

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

Delicious contest: in the only interesting problem solutions with complexity O(N·Q) pass.

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

    The difference between the expected O(N.(sqrt N)(log N)) and O(N.Q) solution will only be apparent at higher values of N and Q. But at that point the better solution also takes a lot of time. I guess one could micro optimize the better code to observe the difference at lower values too, but that is something contestants shouldn't have to do. Therefore, sadly it ends up being a very good theoretical question only. I guess it is one of the few reasons dynamic scoring was used

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

      Then it's not a problem for a programming contest, especially if you were aware of that situation

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

Why did my solution got WA on test 9? I used the same solution with the editorial.

My submission: 16376759

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

    I failed on the same test. Here is a hint: think about the initial elements of your Fib-ish sequence.

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

      Thanks for your hint. I got AC now.

      It turned out that sequence with f0 = a[i], f1 = a[j] is different from sequence with f0 = a[j], f1 = a[i].

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

My solution for A problem (http://codeforces.net/contest/633/submission/16362922) was hacked during the contest and the same solution is now accepted when i submitted it again (http://codeforces.net/contest/633/submission/16377008).

Infact the test case on which i was hacked is not itself valid.(1 1 100000) since range of cwas less than 10000.

HOW IS THIS POSSIBLE??

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

Solution for H: We will use MO's algorithm and segment tree.
Nice!

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

in E, how to deal with increasing size of C(n, k-1)?

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

    Misunderstood the editorial. But my mistake was not in preciseness, in binary search I took the largest index such that vmax[i]*100 <= cmin[i]. But we also need to check (i+1), because cmin[i+1] may be smaller than vmax[i+1]*100, but larger than vmax[i]*100.

    Sad that I had code for that but somewhy decided that it's not needed and commented it..

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

Can someone please elaborate why is 90 the longest sequence length in D ?

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

    Fibonacci(-ish) sequence increases (or decreases) very quickly -- also, it is given that |a_i| <= 10^9. So at some point numbers will be larger than 10^9 -- to actually know what is the longest sequence length, you can take 2 arbitrary values and check for yourself.

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

    Fibonacci numbers increase exponentially. There are actually about 45 Fibonacci numbers from 0, 1, 1, 2, ... till 10^9.

    In this question, excluding the case when all the input is zero, the numbers are being added so they will soon reach the maximum limit specified 10^9 quickly.

    To actually know the sequence which reaches the length of approximately 90, it is formed as follows-

    .....13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13....

    i.e. on right side of 0, write the original fibonacci series and on the left side of 0, write the fibonacci series in reverse with every even position being multiplied by -1.

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

    Well, we can say that the series is completely defined by the first two elements.

    In order to get the maximum length of the series, pick the smallest two elements that you can, consider (0, 1).
    Now the series that has this will be the smallest, (is what I claim).
    0,1 can be had by starting with some number we don't know. Let's build our series backwards and forwards.
    Backwards: (0, 1) => (1, 0, 1) => (-1, 1, 0, 1) => (2, -1, 1, 0, 1) => (-3, 2, -1, 1, 0, 1) and so on.
    Similarly the forward way is (0, 1, 1, 2, 3, 5,..) (The fibonacci series)
    We do this to keep our values as small as possible. Any other series will exceed 1e9 earlier than this.
    Total elements in this series = 90 Code

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

      This analysis is good, but I was wondering is there a formal proof of number of fibonaccis <= MAXVAL ?

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

    Great explanations, thanks.

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

Author after his editorials

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

Here is link to AC solutions to A, B and D according to the required complexities as given in editorial

A- log(max(a,b)) for extended_euclid algorithm http://codeforces.net/contest/633/submission/16374965

B- log(n, 2) * log(n, 5) where log(a, b) represents log(a) wrt base b. http://codeforces.net/contest/633/submission/16375458

D- n*n*l in worst case http://codeforces.net/contest/633/submission/16375898 (Thanks to adkroxx for his nice solution)

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

    Hi, I know it's an old comment, but could you please clarify why you took the ceiling of t1 and the floor of t2 on 633A?

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

the number of numbers having a particular number of trailing zeroes are either 0 or 5 . is there anyway to detect a number whether it have 0 or 5 zeroes mathematically ??

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

    Yes. The highest power of prime p in n! can be given by:

    Since the number of zeros in a number is min(power of 2 in the number, power of 5 in the number), we can simply calculate the power of 5 in n by the above formula and assume it to be the number of zeros in n!, since in n!, the power of 5 will definitely be less than the power of 2 (trivial to see by the above formula).

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

if the expected solution of E had sparse table, why was the memory limit so strict?

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

    Even in 3rd and 4th, Maps and Sets take an extra LOGN time. They have simply ignored it. I don't understand how?

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

      In the editorial, we have mentioned the theoretically correct solution complexity since we assume that we can use unordered_map instead of map and the similar for set. The time limits definitely allow correct solutions which use map, set, etc. instead.

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

        Even unordered_map has high constants. Since some solutions passed doesn't justify these constraints. The proper bound on complexity is (len(str) * 1000 * logn).

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

    We have seen even Java solutions using RMQ sparse table passing well within the memory limits so I would not called it very strict.

    On another note, I have often noticed that we as competitive programmers often tend to ignore the importance of space complexity; to stay safe we often use long long instead of int, etc. In this question the 100*x part in the question was deliberate to make some people believe they need long long, whereas in actuality they just need an int since x ≤ 107

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

What can be more frustrating?

TLE AC

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

not true

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

Where can I get test input? I need for Problem C.

Есть ли возможность скачать тест, на кот-м программа завалилась? Похоже нет это очень неудобно.

По-моему было бы очень полезно добавить возможность на форме протокола тестирования для скачивания нужного теста и/или всех.

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

Could anybody can give some tips in Problem F?

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

    The task is to find two paths in the tree so that no node appears in both paths and the total weight of all nodes in the paths is maximum.

    This can be calculated efficiently using dynamic programming. Let d[a][b] the maximum weight of a single path in a subtree "downwards" from node a when node b is considered as the parent of node a. Now the answer is the maximum of all d[a][b]+d[b][a] where a and b are any two adjacent nodes.

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

    This may be too late, I wrote a description in quora

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

In E, we can do without RMQ sparse table using normal dp. Say visitors and revenue are v[] and c[] respectively, and z[] stores then : int max_v = v[n-1]; int min_c = c[n-1];

z[n-1] = min(max_v,min_c);

for(int i = n-2; i >=0; i--){
    int max_v_till_element = v[i];
    int max_c_till_element = c[i];

    int ans1 = min(max_v_till_element,max_c_till_element);

    int max_v2 = max(v[i] , max_v);
    int max_c2 = min(c[i],min_c);
    int ans = min(max_v2,max_c2);
    if(ans1 >= ans){
       max_v = max_v_till_element;
       min_c = max_c_till_element;
       z[i] = ans1;
    }else{
       max_v = max_v2;
       min_c = max_c2;
       z[i] = ans;
    }
}

http://codeforces.net/contest/633/submission/16382326

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

Plz tell me why am i getting WA on test case 28 In ques C(using trie)... http://codeforces.net/contest/633/submission/16384219

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

My solution for C is Accepted , but I still think it could have been TLE.

I didn't use hashing or trie.

can someone find a testcase that could have been used to hack my solution ?

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

    yes, someone could hack it :)

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

      thanks for this neat testcase :)

      I guess I was lucky there was nothing like this in the main tests :D

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

Could someone, please, clarify these questions for me?

..dp[i] can be defined as ..
What is i here? What are we iterating?

.. the index at which the next word should start ..
What is the next word? Next after what?

.. such that the given string can be formed using the given dictionary ..
What is the given string? What is the given dictionary?

I tried my best to pinpoint the places of confusion. Forgive me, if these questions seem stupid. I needed to come up with something better than 'please, help, I don't understand' :)

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

In problem B why factorial of a number trailing zeros are min value of highest power of 2 and highest power of 5. I just want to feel this logic can anyone please explain it easily? Thanks.

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

    Any number containing one or more zeros at end must be a multiple of 10, right? 10's are formed by the primes 2 and 5. 2*5 = 10.

    That's why. If you still don't feel it, it's a very well known mathematical problem, google it and you'll find many sources.

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

Someone please explain the solution of problem C using Rabin-Karp hashing...

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

Hey , Could somebody explain the solution for problem H? I couldn't understand how to use the mentioned fact in lazy propagation to solve this problem.

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

hi please help: i submitted the problem D but i get Time Limit Exceeded on Test 3 :( this is my code:16392423 Thank You.

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

Can somebody explain, in problem E, how the binary search works? For each z[i], ans(j) is some function that first increases and then decreases, but it's not strict? (It is the minimum of an increasing function and a decreasing function, so it either decreases or increases and then decreases)

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

    It is the minimum of the increasing function, say f(x) and decreasing function say, g(x).

    Binary search uptill the maximum index i such that f(i) is strictly less than g(i). Then the answer is either going to be on index i or index (i + 1) .. If you try to think about it using diagrams then it would be clearer.

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

      Oh, yes, I see it now. I thought of it before as simply function that is used in the ternary search, and didn't consider the combination of individual functions at all XD

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

Auto comment: topic has been updated by mkrjn99 (previous revision, new revision, compare).

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

Can someone please explain ? What is bitset and how to uptade it ?

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

    Bitset is just a set of bits (binary digits) that can be used as an efficient alternative to a boolean array. The advantage of using a bitset is that certain operations such as OR, AND, count are faster than a boolean array. The underlying structure of bitset utilises the fact that a word (32-bit or 64-bit depending on platform) is just a combination of bits and bit operations on them are very efficient due to the hardware support. In this case taking a bitset of size 1000, we can assume that the and of two bitsets is computed in 1000 / w machine operations, where w is the word size (typically 32 or 64).

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

In Problem B , on test case 41

My code gives 0 as number of values of n having 26151 zeroes on terminal and ideone.

But on codeforces it gives 5 as output.

I can't understand why?? Can somebody help me?

My ideone solution :- Ideone Solution Link My codeforces solution :- Codeforces Solution Link

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

    Constarints for problem B are wrong. Upper limit of m is given 10000 where in Test case 41 it's 26151. plz try to Resolve such issues.

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

      Please read the problem statement carefully. Constraints for problem B state M <= 100,000.

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

    Increase the upper limit of the cases you are calculating for. Your link on Ideone doesn't work correctly either because the numbers are of the order 1e5, and you are computing till 5 * 1e4.

    This is correct now.

    Make the constant = 1,000,000.

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

The editorial right now does little to help me find the solutions since it uses jargon like Rabin Karp hashing, euler tour, Mo's algorithm, lazy propagation etc. which I have no clue about (I do hope I am not the only one with this problem). It would help if you could dumb it down a bit so that even amateurs like me can follow what you say.

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

Why am I getting WA for my solution for problem C? 16406153

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

Explanation of problems C and D could have been explained in a more detailed manner :)

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

For Problem E, to calculate z[i], it can be observed that if 100*v[i] >= c[i] then clearly z[i] = c[i]. When 100*v[i]<c[i] we can only get better value for z[i] if z[i+1]>100*v[i] but we cannot get better than c[i] therefore z[i]= max(100*v[i],min(z[i+1],c[i])) in this case.

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

Problem 633C - Spy Syndrome 2 :

My solution using prefix trie should get TLE on a test like this :

10000
aaa.....aaab
100
a
aa
aaa
.
.
.
aaaaa........aaaa
aaaaa.........aaab

my AC solution : 16367453

Test File Here

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

    Can you provide some reference for prefix trie?

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

      Unfortunately, I've studied Trie from Arabic tutorials. But he uses slides written in English, So I hope it helps.

      Here

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

I can't understand problem F by just reading codes by others...Who can help me?I have not find discussion about it....

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

Why this solution is TLE 16435289 whereas this is AC 16431586 in problem D 633D - Fibonacci-ish

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

In Problem 633C - Spy Syndrome 2 I got AC and WA in 2 solutions only differ in map<int,int> gets AC and when i changed it to unordered_map<int,int> i gets WA on test 53!! could anyone explain why that happened?!

First AC submission 16433158

Second WA submission 16433164

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

    Can anyone explain the difference between hash_map and unordered_map

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

    Hah, deceivingly it has absolutely nohting to do with those maps. You have integer overflows when computing h and v which leads to undefined behaviour, which means that behaviour of your code is not defined. More precisely it is allowed to behave differently when executed many times. That is not just plain and unreal theory, it is really happening :). I copied your code that got accepted and submitted it two times and first time 16559248 I got WA on 17th test and second time 16559257 I got WA on 53rd test. However when I copied your code with unordered_map and removed overflows it got ACed 16559243 :).

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

I think someone said this before (on another blog?) but I couldn't find it and I think it is worth repeating.

The editorial solution as written doesn't really work without additional tricks, since it's complexity is actually

This becomes O(n2) for a star graph, and for example the given author's solution seems to TLE on such a test.

To fix this, we need to have a way to accumulate values from a subtree and also invert one value (of the child to be calculated next) — which can be done with prefix+suffix "sums" or just working it out based on the problem. I would love to see simpler ways to use the idea of dp[edge] if anyone has any!

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

Oh god I thought problem C is similar to GGCJ Round D problem C, where the ciphertext is shuffled in random order.

Somehow this code managed to stay up till case 67. Your text to link here...

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

for C why this code aint work WA at test 46 https://codeforces.net/contest/633/submission/77006664

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

For problem D can someone explain me how to prove that the length will be logarithmic.

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

Alternative solution for 633F - The Chocolate Spree

Find the diameter. If you remove the diameter, you get some subtrees. There are two cases for the two optimal paths:

  • the diameter, the diameter of a subtree
  • a prefix of the diameter + a vertical path in the corresponding subtree, a suffix of the diameter + a vertical path in the corresponding subtree

You can check both cases in $$$O(n)$$$.

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

216754901 Problem C solution using trie

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

Anyone solved A using the gcd(a,b) divides c ,i understand that the parameters should be positive , but what if the ones i find weren't both positive , i try doing a translation but doesnt work.

→ Reply