Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 4 месяца назад, По-русски,
Tutorial is loading...
Код на C++ для уточнения деталей
Tutorial is loading...
Код на C++ для уточнения деталей
Tutorial is loading...
Код на C++ для уточнения деталей
Tutorial is loading...
Код на C++ для уточнения деталей
Tutorial is loading...
Код на C++ для уточнения деталей
Tutorial is loading...
Код на C++ для уточнения деталей
Tutorial is loading...
Код на C++ для уточнения деталей
Разбор задач Codeforces Round #496 (Div. 3)
 
 
 
 
  • Проголосовать: нравится  
  • +52
  • Проголосовать: не нравится  

»
4 месяца назад, # |
Rev. 6   Проголосовать: нравится +15 Проголосовать: не нравится

The problem E1 is the same as that one.

translate
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Although the problems are (very) similar, the one you linked does not ask the user to account for sequences of even length.

    While a rather small difference, it's still worth noting.

»
4 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Very detailed editorial Thanks

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I like the solution for E2 .

I can only use segment tree nesting BST to count 3d partial order .

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Can someone please tell me what's the error in this approach from Problem D? Solution

  • »
    »
    4 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    Looks like you don't handle following case:

    3

    111

    Answer is 1, your code will return 0.

    Edit: or maybe you do, didn't see next for j loop. Will check with computer in an hour or so and come back with counterexample :)

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Ok, found one (posting in another comment so you can get notification):

    313

    your code gives answer 1, but correct one is 2.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody help me out I can't understand why my same solution is both TLE and AC. AC:40160742 TLE : 40160895 It has cost me a problem in this contest which I was sure would pass the test cases.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The execution time of a code is not exactly the same when you run it all the time. There are various factors for this. For example — server load(i think).

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    its strange but i just removed comments it got Accepted,don't know why

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I just copy pasted your code (One which got TLE without any change) and submitted it and it got AC: 40215523

    This is really strange.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah that's the reason I posted it.It cost me a problem in contest which was assumed by me to be AC.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem C why we are taking the upperlimit as 2^30? Because of range of int? And what if we use long int ?Is there any other way of solving this by Bit manipulation?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Because max a[i] is 10^9. 2^29 < 10^9 < 2^30

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Shouldn't we take 2^31 as the upper limit? since sum of two number ,if each of them is 10^9 will be 2.10^9 and since 2^30 < 2.10^9 then we will need 2^31 for checking.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We need to test all powers of 2 until 10^9 since a[i]<=10^9, so we test whether each power of 2 until that is less than 10^9 makes a complement that already exists in the set. Since 10^9 < 2^30.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

how to solve E1/E2 using a binary indexed tree? Thank You

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://codeforces.com/contest/1005/submission/40129757

Why my code gives TLE on Test case 26 ? Is it because count in multiset is slow as compared to map ? This problem messsed up my rating anyway.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E1 can anybody explain why does the segment p[l...r] have median equal to m, if and only if m belongs to it? What if I'm looking for median 3 and I have segment [2, 4]? The median of this segment is also 3, even though there's no 3 there.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    "If the length of the sequence is even, the left of two middle elements is used." Since the segment [2,4] is of even length, than the median will be the "left-middle" element. In this case 2.

    M must be in the sequence because the median will be equal to one of the elements in seg[l..r].

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are talking about average. Problem asks for median. Those are different notions.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      No, he is talking about median. Median is usually defined as average of two middle values if lenght of an "array" is even. Of course, one should be aware of how it is described in the problem statement

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yeah, my fault. The version with average seems to be a different problem.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes, you are right, my mistake.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I didn't understood the concept of traversing the string in reverse in solution of problem D. Here is a simple code by TangentDay, I was using to understand: http://codeforces.com/contest/1005/submission/40122504

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    This helped me understanding the greedy solution, thanks. But there is actually no need to reverse the string, maybe that's why you couldn't understand the reason behind it. I couldn't find any reason or counter-example so I decided to submit without reversing and it got accepted.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem D, greedy works fine. My submission : http://codeforces.com/contest/1005/submission/40141981

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Will you please explain the logic behind this snippet:

    else if(szz(t) >= 18) t.erase(0,1);
    
    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      to avoid overflow of the integer when the size of the string is >=18, i.e, 10^18.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      During contest i wrote it to avoid overflow. Butin fact this line will never run. Because every third number have to be divisible by 3. Why ? For numbers to be divisible by 3, the sum of the numbers should be divisible by 3. So, there are only three possibilities for remainder 0, 1, 2 in which 0 is favorable. Let's say u get sum%3, 1, then 2 now it has to either repeat or 0. 0 is fine. If it is 1 that means sum from next to last 1 to here is zero. So it has to divisible by 3. This way you only have to check at most legth of 3 at each stage, abc, bc, c. Greedy works because you should take lengths as short to maximize the number. I hope it's clear.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hey, can any body help me understand problem E1 I can't understand the solution till now :)

  • »
    »
    4 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    I feel like description is quite good. Can you tell me if there is a part in explanation that you specifically don't understand? If it's even first sentence, that's fine, just say it, It will be easier to help you that way.

    EDIT: negative votes for trying to help? Why? :)

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I understood that he searches for the right L for every r but we in the map at beginning he mad C[0]=1; the map of sum=0 = 1 and for a case like: 2 2 1 2 ans = 1 but it comes from c[-1]+c[-2]=1 c[-1]=1 how come ?!

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 7   Проголосовать: нравится +16 Проголосовать: не нравится

        Let's start with simpler, but similar problem. You have array containing only -1's and 1's. You want to find number of segments that end at position m and have sum equal to 0.

        How would you go with it if you did start from place where m is and go left to find all "good" segments? Probably will still calculate "sum" and check when it is equal to 0.

        What if you did start from the beginning though, iterate to the right and stopped at place where m should be analyzed? Obviously you already have some "sum" at this place. What positions for left side of segment are now "good"? Example: we have something like that:

        [1, 1, 1, 1, -1, 1, -1, 1]

        and are looking for segments with sums equal to 0 with right side at the end of the array. Those one would be:

        [-1, 1, -1, 1] (so from "before" position 4 to "after" 7 with indexing from 0) and [-1, 1] (positions "before" 6 — "after" 7)

        What is sum at the end of the array if you did start from the beginning? 1+1+1+1+(-1)+1+(-1)+1 = 4. What is sum at our "good" left sides? 1+1+1+1 = 4 and 1+1+1+1+(-1)+1 = 4. Wow, they are all the same, but not equal to 0, why? It's because our prefix ([1,1,1,1]) affects all sums, but we want to cut it off! So now that we reached end of the array and have "sum" 4 we are looking for places that have also "sum" equal to 4. That way difference in sums between those places will be 4 — 4 = 0, so exactly what are we looking for.

        And now advantage of this approach lies in the fact that calculating how many segments end at the next position is just matter of checking how many places have "sum" equal to "sum" at this next place, no need for going through the whole array again.

        Now, also important is to add one to "sum = 0", why? Consider following:

        [1, 1, -1, -1]

        What are the right answers here if we are looking only at segments ending at the end of the array?

        only [1, 1, -1, -1] (so whole array, from position "before" 0 to position "after" 4)

        So how would our sums look like after each step:

        [1, 2, 1, 0]

        and you would look that at the end you have 0, so we need to count all other 0's that were there before. Unfortunately, we didn't consider segment starting at position "before" 0, because we were calculating only sums after going through each number (so positions "after" in my terminology). That's why our sums should rather look like this:

        [0, 1, 2, 1, 0]

        so we just added 0 at the beginning and now everything works. That's because thos sums are more like values inbetween values of original array (and that's also why there is one more value).

        I think that now coming back to original problem is quite straightforward. We are basically doing the same thing after converting all numbers to -1's and 1's. Also, we need to check both values for sums equal 0 and -1 as if there are both segments that can have odd number of elements, so m will be in the middle (and sum should be equal to 0) and those with even number of elements (so with sum equal to -1).

        Here is my related "painting mastery" prepared in, well, Paint: https://imgur.com/a/pHwTfzX

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks a lot, I understood after reading twice.

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thank you very much you did a great job ^_^

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          Thank you very much. awesome explanation.

        • »
          »
          »
          »
          »
          6 недель назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          it should be for 0 and 1 instead of 0 and -1. am i right?

          • »
            »
            »
            »
            »
            »
            5 недель назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            (I am assuming you're asking for the last paragraph)

            Not exactly. Even in proposed solution you have ans += c[sum] + c[sum — 1], not c[sum] + c[sum + 1].

            Example:

            array [1, 2, 3, 4], m = 2

            good answers: [1, 2, 3], [1, 2, 3, 4]

            "sum" after each step (with 0 inserted at the beginning): [0, -1, -1, 0, 1]

            At the last position you have sum = 1 and you need to look for segments with sum = 0 (so c[sum — 1], not +1), since that means that after you cut off that prefix you will be left with a segment where number of bigger elements is one more than number of smaller ones. You can look at it that way: when you refer to c[sum] + c[sum-1] you are not asking for sum in the current segment, but you are asking what prefix to cut off so that you will be left with your desired sum.

            • »
              »
              »
              »
              »
              »
              »
              3 недели назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Thanku. i Got it. You are really great with the concepts.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      why ans+=c[sum]+c[sum-1] is the answer ??

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I answered the question above, in comment:

        http://codeforces.com/blog/entry/60511?#comment-444221

        Please take a look and ask questions if you don't understand something.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I just figure out a better way to explain it. You have to split the array into two part -- m has appeared and m hasn't appeared.Find the sum in first part equal to sum or sum — 1 in the first part. Because when a p[l…r] is the one we want the value greater−less equals 0 or 1.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain me why using map I got TLE ? But work when using unordered_map .

Here is my code map 40152865 unordered_map 40153361

thank you!

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    std::map has guaranteed O(log N) complexity for search, insertion and deletion. It uses a comparison operator, and iteration happens in the order defined by that comparison operator.

    std::unordered_map only guarantees O(N) complexity for search, insertion and deletion, but you normally expect it to be O(M), where M is (more or less) the size of an individual key. Assuming keys are small relative to the number of items, it's basically O(1).

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    if(mp[j-a[i]]>=1){ If map does not contain j - a[i] value, it will create it and your code will check new created values, what goes into TL.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    To add to what shivamgor498 said, while logn access would be completely fine for this problem normally, what is actually creating the problem is the way you're accessing the map. Checking if mp[j-a[i]] >= 1 will add the pair {j-a[i], 0} to the map if it doesn't already exist, and since that can happen many times, the size of the map can become very large. In that case, log(size_of_map) might actually be big enough to slow things down a bit, while the (amortized) O(1) access saved you in the second submission.

    For reference, look at 40168171 — I've fixed your map code to not do this, and it's actually faster than the unfixed unordered_map, with the memory usage also being positively tiny in comparison (8000kB vs 170000kB)

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Well, I see structure/binary search in C, dynamic in D and I didn't read E1, E2 and F. Looks like div2 round (maybe a bit harder, 7 tasks instead if 5).

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain why we do this: "So for each r that p[0..r] contains m do ans +  = c[sum] + c[sum - 1]". And why we add sums into c only before meeting m?

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For C works binary search in sorted array with testing that found index not the same as index of initial number. http://codeforces.com/contest/1005/submission/40138415. For D it is enough to use the fact that every three consequtive digits contain at least one number divisible by 3, so greedy works well.

»
4 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Why in code of E1, c[0]=1 is taken at the beginning?

  • »
    »
    4 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

    Consider the case where median (or m as in input) is at the first index of array p. There should be increment in ans there for pair (1,1). But ans will remain 0, if u don't initiliase c[0] = 1. Take other cases like 1 3 2 (m=2). You will realise this is the requirement to consider the pair or segment from beginning to median i.e. 2 here. Infact, as sum = 0 initilally we have to take c[0] = 1 to take all values from beginnning to median or after median for first time where sum becomes 0.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    Let us denote position of m in the array as pos.

    We will be adding values to ans only for subarrays whose R (right index) is in the range [pos,n]. However, pos is a valid L (left index) as well, since it could be the starting index for a valid subarray. Hence they have used c[0] = 1. Let me know in case my explanation was unclear.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

In D why do we need to take z[i]=max(z[i], z[fin[r]] + 1) and not directly z[i]=z[fin[r]] + 1 in the editorial solution? It is getting wrong on case 11 but the input is too long to understand the logic

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Because you are not considering the best value at z[i].. Consider the case s=1002 The output should be 2,but according to your logic you would get z[n]=1,thus neglecting the best value at z[n-1] which is 2.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Don't forget to do this : z[i] = z[i — 1] And then you want to maximize your answer so you do this z[i]=max(z[i], z[fin[r]] + 1). The point is that i-th number can either make answer bigger or not. So in case 11 you probably have already found best answer, but then did z[i]=z[fin[r]] + 1 and lost it.

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In problem E2, Why did you say "In other words, find sum of all s[w], where w < sum" ?

i thinks, it should be "find sum of all s[w], where s[w] < sum" or not ?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    no

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    oh, i'm sorry. i understand the misconception.

    i didn't notice that s is number of partial sum, so w is sum of a prefix any sequence.

    thank you for good solution idea.

»
4 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

I think that the time limit for prob C was too rigid, My solution got time limit exceed at test case 28, the only thing I missed was storing the number of occurrences of all the numbers. I think that while programming we assume that all the numbers would be unique and writing code for this kind of optimization as unnecessary.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    So if we go along your thinking we should make all problems easier and easier to the point where all cases are just one big case and answer is always 42, right? :)

    Also, I'm not sure if you can claim anything about time limit writing in Java without fast I/O. Maybe you should try looking at codes of top coders writing in Java and specifically at how do they deal with reading input if you really want to stick with using this language for Codeforces. Petr is probably your "go-to user".

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ok, will check the input / output of the other java coders here. 28th was the last test case. That gave the burn.

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I am finding it really hard to understand dynamic programming approach for problem D.Could anyone please explain that briefly.

Thanks a ton.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    it's basic DP. If you didn't understand this then don't worry first go and learn basic DP theory and solve some problems. Then come back, you will surely understand then that it's not that hard here.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

can someone please help me with the test case 8 of C 40188877

Thanks in advance for the assistance.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Hey, writing just to let you know that someone here actually tried to help, so you are not alone :) Unfortunately I wasn't able to find main mistake, but few quick tips anyway:

    a) don't use pow if you don't have to — you can achieve here the same result by doing a[i] = 2 * a[i-1]

    b) don't use log2 if you don't have to — you can achieve here the same result by going through the number and checking number of bits set or just simply using __builtin_popcount (as you are using gcc)

    c) it's just easier to declare a[40] or something like that and then checking all bits up to 31 always than making some error-prone code like the one with "max" and "c" — imho you are not gaining enough time/space to justify writing so much additional code just for that purpose

    d) you have mistake for case with only one number 1 (although it's not why test case 8 doesn't work)

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks you so much, these tips matters a lot to me. I'll give my best shot to impliment all of these in my future codes.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Just to clarify: pow, log2 — > floating point types — > imprecision. Lots of explanations in internet if you are interested. Oh, if you find error please, please let me know. I looked at your code for like 2 hours or so. Logic looks fine to me. Either I'm blind or it's something really tricky.

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In question E1, why don't we consider any case when p[r]==m? Isn't that important?

»
4 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

In e1 why you put c[o]=1?

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

nice problemset and editorials are also awesome! thanks a lot :)

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I like the solution to D.My solution is TLE.hh.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

someone help in F did't understand clearly want to solve F desperately ...

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

in F: why f[j]=0 is done in else part....anyone plz explain

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please help me understand the recursive solution of Problem D by talking about states and transitions. Thanks in advance.

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

In solution for problem 1005E2 - Median on Segments (General Case Edition), when we want to calculate sum of all s[w], where w < sum , could someone explain why this works:

  • If you decrease sum, just subtract the value s[sum].
  • If you increase sum, before increasing just add s[sum].
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Can anyone explain the last problem, why and how the "red" edges are used in calculating the answer??

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A simpler approach to problem D — for a given number k find the smallest prefix that can be cut into pieces k of which are divisible by 3. It is easy to get the solution for k based on the solution for k - 1. This leads to a greedy solution to the original problem — solve for consecutive values of k starting from 1 until we reach the maximal value for which the solution exists.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The last line of tutorial for problem D should be:

Sequentially calculating the values of z[0...n], we obtain a linear O(n) solution.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I like the solution for Problem D! :) Thank you!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in the problem E1, why am i taking c[0]=1 ?? please explain me this

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is wrong fwith my programm for problem D

include

include

using namespace std;

int main() { string str;

cin>>str;
int len = str.size();
long sum = 0;
int ctr = 0;
int x = 0;

for (int i = 0; i < len; i++) {
    int num = str[i] - '0';
    if (x == 1 && num == 0)
       x = 0;

    x += num;
    if (x % 3 == 0) {
       ctr++;
       x = 0;
    }
}

cout<<ctr<<"\n";

return 0;

}

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you go to your last solution, click on it's id, scroll down you will see test with wrong answer. It's very small, so you should be able to debug based on it. Have you done that?

    Also, it's better to link your solution than paste code. Look at other comments.

»
4 месяца назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone know this algorithm used by problem F?

if the current used red edge is not the last for the vertex, use the next and stop. Otherwise, use the first red edge for this vertex (and go to the next vertex) and continue with the next vertex.

I think naive DFS can also implement the same idea.

Suppose n is the number of vertex, k is the average number of red edge for each vertex,

then time complexity for naive DFS O(k^n)

and time complexity for this algorithm O(kn^3)

Am I right? BTW, this algorithm is really amazing!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Somebody please help, in the C code generating extra map index which is further causing TLE. BUT not happening in unordered_map.40527567 ........Try printing it->first for all index of map before and in the last for loop. Thanks in advance.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

40527567 Some one please help me out, this giving a TLE in the 7 test case, and when i'm printing the it->first values for all elements of the "hash" named map declared, in the last for loop its giving some adding extra elements the same map. and may be this is the reason for TLE. Can someone please explain why all this is happening. Thanks in advance for your assistance.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    http://www.cplusplus.com/reference/map/map/operator[]/

    Comment below example: "Notice how the last access (to element 'd') inserts a new element in the map with that key and initialized to its default value (an empty string) even though it is accessed only to retrieve its value. Member function map::find does not produce this effect."

    So when you do for example "hash[a[i] — it->first]" if "a[i] — it->first" is not in the map it will be inserted there with value 0, because that's how [] operator works on maps in cpp. You should use function "find" in this case.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hey my approach for problem d was : 1. get the whole array in the following form arr[i] = (arr[i]%3) ; 2.you can prove by induction that greedy approach will work fine for example 1011 ans will be 1 no matter what you choose either full segment or only 1 -'0' 3 now see how many zeroes are there add them in ans; all '12' and '21' form strings form a multiple and one digit will only contribute to single multiple; and also all strings of the form '111' and '222' ;

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me understand the logic behind the tutorial of 1005C? Why are we subtracting a powers of 2 with the number we have?