nikola12345's blog

Codeforces #307 (Div. 2) Editorial
By nikola12345, history, 9 years ago, In English

Problems proved to be much harder than we expected. There were some corner cases we didn't include in pretests, so many solutions failed, which was definitely a mistake. Anyway, I hope you find this problemset interesting!

Problem A. GukiZ and Contest

Very simple implementation problem. Just implement what is written in the statement: for every element of array, find the number of array elements greater than it, and add one to the sum. This can be easily done with two nested loops. Total complexity O(n2).

Solution: link

Problem B. ZgukistringZ

First, calculate the number of occurences of every English letter in strings a, b, and c. We can now iterate by number of non-overlapping substrings of the resulting string equal to b, then we can calculate in constant time how many substrings equal to c can be formed (by simple operations on the number of occurences of English letters in c). In every iteration, maximise the sum of numbers of b and c. Number of iterations is not greater than |a|. At the end, we can easily build the resulting string by concatenating previously calculated number of strings b and c, and add the rest of the letters to get the string obtainable from a. Total complexity is O(|a| + |b| + |c|).

Solution: link

Problem C. GukiZ hates Boxes

Problem solution (complete work time) can be binary searched, because if the work can be done for some amount of time, it can certainly be done for greater amount of time. Let the current search time be k. We can determine if we can complete work for this time by folowing greedy algorithm: find last non-zero pile of boxes and calculate the time needed to get there (which is equal to it's index in array) and take with first man as much boxes as we can. If he can take even more boxes, find next non-zero (to the left) pile, and get as much boxes from it, and repete untill no time is left. When the first man does the job, repete the algorithm for next man, and when all m men did their maximum, if all boxes are removed we can decrease upper bound in binary search. Otherwise, we must increase lower bound. Total compexity is .

Solution: link

Problem D. GukiZ and Binary Operations

First convert number k into binary number system. If some bit of k is 0 than the result of or opertion applied for every adjacent pair of those bits in array a must be 0, that is no two adjacent those bits in array a are 1. We should count how many times this is fulfilled. If the values were smaller we could count it with simply dpi = dpi - 1 + dpi - 2, where dpi is equal to number of ways to make array od i bits where no two are adjacent ones. With first values dp1 = 2 and dp2 = 3, we can see that this is ordinary Fibonacci number. We can calculate Fibonacci numbers up to 1018 easily by fast matrix multiplication. If some bit at k is 1 than number of ways is 2n — \t{(number of ways bit is 0)}, which is also easy to calculate. We must be cearful for cases when 2l smaller than k (solution is 0 then) and when l = 63 or l = 64. Total complexity is .

Solution: link

Problem E. GukiZ and GukiZiana

First we divide array a in groups with numbers. Every group in each moment will be kept sorted. For type 1 query, If we update some interval, for each group, which is whole packed in the interval, we will add the number it is being increased to it's current increasing value (this means all the elements are increased by this number). If some part of group is covered by interval, update these elements and resort them. Now, let's handle with type 2 queries. When we want find GukiZiana(a, j), we search for the first and the last occurence of j by groups. One group can be binary searched in , because of sorted values, and most groups will be searched. Of course, for the first occurence we search for minimum index of value of j, and for the last occurence maximum index of value of j in array. When we find these 2 indexes, we must restore their original positions in array a and print their difference. If there is no occurence of j, print  - 1. Total complexity is .

Solution: link

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

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

Hi this was my exact solution for problem E; but I get MLE. Can anyone tell me why? 11555983

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

    I personally can't find anything wrong with your code..

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

    I had the same problem, it was because I used set. When the complexity is for queries is O(Q*sqrt(n)*log2(sqrt(n))), my code would generate at the worst case up to 300000000 new set, which is definitely not ok.

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

Could you tell me why my code is giving TLE test #23? 11554583 I think my algorithm is O(4*26*|a|). I can't find the error :(

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

    Because multiply of minC * let[2][i] can be more than int. MinC <=1e5, let[2][i] <=1e5 . Very tricky. I have the same problem.

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

    When declaring the variables as global in the same code it works O.o 11560581

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

      I had the same problem, you have an uninitialized variable ans, so it's value can be anything.

      And in our case it was a large value, so the program keeps printing the second string until it gets TLE.

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

A bit too hard for Div2, the solution ideas are great though. Not even sure if it was a good or a bad round, to be honest.

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

is there an online/offline solution of Problem E using Segment Trees?

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

I have a different solution for problem E that works in less than one second for the given test cases.

  • Make a list of pairs [n, pos] which means that number n is at position pos. Sort this list.
  • Keep a list of segments affected by type 1 operations and store in each one of them the increase value. Initially, there's only one segment: [1, N]. Later, each type 1 operation will create at most 2 new segments, so we iterate over all existing segments, updating data as necessary (for all segments contained entirely in the range [l, r], update the increase value by x) and creating new ones if needed.
  • For every type 2 operation, iterate through all segments. Let's say the current segment has a total increase value of a, then we must look for number y - a in this segment, so we search the sorted list of pairs for the first element that exceeds [y - a, l], and for the last element that is not bigger than [y - a, r]. Let's say we found a pair [n, p]. If n = y - a and l ≤ p ≤ r, we have an answer. Among all p found, we keep the minimum and the maximum, and that will be our answer. If we didn't find any suitable pair for any segment, then we output  - 1.
  • Finally, one thing to consider is that if there's a segment with increase value  > 109, then it's useless 'cause it would mean the initial value for the sought number would have to be  < 0, so you should ignore it.

This is my submission: 11560232

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

    What is the complexity of your solution? If a type 1 operation creates at most 2 new segments, and you iterate over all these segments in every type 2 operation, doesn't it make it O(N*Q) in the worst case?

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

      Yes, theoretically, something like that. If half the operations are type 1 and half are type 2, and all the type 1 operations create new 2 segments and are small enough so that no segment ever goes beyond 109, then the total number of operations would be , or something like that, but it seems the test data is very weak, that's why I said "for the given test cases" in my original post.

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

        It's difficult to design test data for such unusual solutions. Nice solution by the way, it seems for the given test cases, even my O(√N*Q) solution is a tad slower than yours.

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

    This solution 11556101 seems to use your last idea, but I'm not sure why it passes, as it appears to be pretty-much brute force. Any ideas why?

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

Why greedy solution for problem C works? I get idea intuitivelly, but hav no good proofs. Why we should at first go the farest pile?

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

    Someone has to go there inevitably, so just send the next student and make him collect as many boxes as possible there. If he still has time, make him collect some on his way too, always the ones most to the right (clearing the farthest piles of boxes first means the next students will have to walk less, thus saving time).

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

    To clarify the explanation in the comment above (this helped me understand myself, so thought I might just elaborate): in any valid schedule, at least one student s has to collect boxes from the last pile. Suppose he doesn't move all the boxes at the last (non-empty) pile, but instead spends time moving boxes at an earlier pile. This means at least one other student s' also arrives at the last pile to move boxes. But s can move more boxes at the last pile instead for s', and transfer some of the box work at the earlier pile to student s', since s' had to pass through the earlier pile anyway to get to the last pile, so it doesn't cost any additional moving for s'. By repeated such exchanges, s will end up moving all the boxes he can (within the time limit) in the last pile. If he still has time left, he might as well help move some boxes in second to last (non-empty) pile since he has to go through the earlier pile to arrive at the last pile anyway. And we repeat.

    Also, I think this implies that the opposite greedy strategy of sending students one at a time and make them move any left-most boxes before moving onto the next pile is also provably correct (let's call a schedule obeying this constraint "front-first" schedule). This is because given a "back-first" schedule that runs in time t, we can easily transform it into a "front-first" schedule that runs in time t.

    I modified the sample solution to use this strategy and passed all the tests.

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

      Thanks for explanations. Really cool idea with front-first. I think about it and can't proof that it is optimal strategy too.

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

Hello.

Here is my submission for problem B.

On test 3 my code can output a string K of 4 non-overlapping strings: ab, ab, ab, and aca. However, the sample output was only 3 non-overlapping strings.

Any help?

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

    There are only 4 'a' letters, but your algorithm output has 5.

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

Why doesn't a simple greedy one work for Problem C?


boxes = array of boxes
students = array of number of student at indices
Start with all students at index=0 at t=1
while(totalBoxes > 0) {
 for(i = n-1 to 0) {
   b = boxes(i)
   s = students(i)
   boxesToRemove = min(b, s)
   boxes(i) -= boxesToRemove
   totalBoxes -= boxesToRemove
   studentsToMove = s - boxesToRemove
   students(i) -= studentsToMove
   students(i+1) += studentsToMove
 }
 t += 1
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Imagine what happens if you have 2 students and [2 1] array of boxes. The optimal way takes 3 rounds, the greedy algo takes 4 rounds.

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

    Even I had a similar algorithm. But the greedy strategy I applied was from 0 to n. As the students move into the piles, they clear the boxes. The problem comes when you need to take care of multiple piles of length 0. Also Consider 2 5 3 7 Initially when 3 are lifting pile 1, 2 would have reached 5 and by the time the previous 3 reach the second pile, the two already there would have lifted two boxes. A thing similar to this, I am unable to find in your code. Shouldn't there be a while loop saying while(boxes(i)>0)...

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

What's wrong with my solution for problem D? Why did I get wrong answer on test 16?

My code

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

    This test case asks you to count numbers below 264 but you stop at 260 (or so).

    fdto(i, min((ll)60, l-1), 0) {
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That's the loop I used to calculate binary-bit array of k.

      Since 2^60 = 1 152 921 504 606 846 976 > 10^18, no number k will have 60-th bit equal to 1. The same is true for bit 61, 62 and 63-th bit of k. So, it isn't necessary to check if these bit equal to 1 (their default value is 0).

      And the final loop I used to calculate the answer:

          fto(i, 0, l-1) {
        if (s[i] == '0') ans=(ans*c0)%m;
        else ans=(ans*c1)%m;
    }

      It has covered all bit of k (from 0 to l-1).

      (Please tell me if something in this comment was wrong)

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

        Sorry, didn't notice that. In this case the problem is that last positions are filled with zeros, not '0' characters.

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

Is there a way to/place where we can see how many of the participants in a given round were in division 1/ division 2 at the time of participating?

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

Even if I were smart enough to figure out the solution for problem E, I would never risk implementing an algorithm of such high asymptotic complexity in a programming contest.

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

Hello guys,I am little weak in strings :( Can anybody explain me what was asked in DIV 2 B.In simple words and the editorial too :).Many thanks

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

    We want to use letters in string A, to build as much B or C as possible.
    e.g.
    A: keekeejj
    B: kee
    C: ej
    we can make K : kee kee jj,so we have 2 B,we get 2
    if we make K: kee k ej ej, we have 1 B and 2 C,we get 3
    so we can make K:keekejej or ejejkeek or ejejkeek...
    editorial: we can enumerate if we make 0 B, how many C we can make
    if we make 1 B, how many C we can make
    ....
    and we get max B + C
    Hope it helps.

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

      That was helpful . But I guess it will get TLE?

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

        Depends on the way you implement it! I got TLE twice during the contest, had to reduce the number of times I did string formation to a minimum.

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

        Time complexity is O(n)，n is max number A cobtains B，and here is my submission.
        11561839

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

      Why is it necessary to enumerate through 0 B, 1 B, 2 B, 3 B... MAX B?

      I thought that we can just test MAX B, and then MAX C with what's left. And then use the same thing but with MAX C first and see which way is greater?

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

        I did it ,too. But cannot past pretest.I wonder why.

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

          It doesn't work on this case: aaaaaabbbbbb aab abb

          Thanks to zadrox for the test case! Link

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

          So the answer is not necessarily going to maximize string B or C. We can sometimes get a greater answer if we use a combination of B and C.

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

On problem B,the same method,but i got a TLE,who can help me?11562139

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

    I did the same thing as you. The only difference is that i iterate the b string only till a. size() /b. size() and store the count after taking i times string b in a new_count, for later reference, to reduce no of times it's calculated.

    Don't know if that made a difference...

    my submission —11556629

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

I used BIT for problems A @@ lol so stupid. I wasted my time :(

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

Problem B: Can anyone explain why the greedy method would fail here? Taking max(maximum b then c, maximum c then b) from string given

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

    Sorry, I meant this: If b = "aab", c = "abb" and a = "aaaaaabbbbbb", greedy answer is 3, but real answer is 4: "aab" + "abb" + "aab" + "abb".

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

      Thank you for your reply very much.

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

    test
    aacaacbbaac
    aac
    ab
    greedy algo: 3
    correct answer: 4

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

Which test case am I missing for Div 2 A ? 11549286

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

Of course, for the first occurence we search for minimum index of value of j, and for the last occurence maximum index of value of j in array. When we find these 2 indexes

how we can find 2nd index? with hash of values,but then how update?

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

    You can binary search both of them through the sorted groups of elements, which are sorted by value and index.

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

      on each sorted subgroup: we should binary search on indexes,but what is the answer for this segment? I mean,it's MAXindex-MINindex on segment,and how you are finding them?

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

        You don't have any segment in query, you just need to find minimum and maximum position of occurrence of some number j in array (if I understand your question).

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

Problem B was very similar, albeit a little bit more general, to this problem: http://mirror.codeforces.com/contest/519/problem/C

The idea (How many to take form the first kind, how many to take form the second kind?) is exactly the same.

Surprisingly, it was solved by 1750 coder, in contrast to this contest.

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

Why compexity of C isO(n*log n) ? In your solution upper bound of binary search is sum a_1+...+a_n . And for every call of binary search you use O(m) operations . So I think that total compexity must be O(m*log(a_1+...+a_n)) .

PS. Sorry if I wrong but I have no idea how did you get your compexity .

UPD . I'm not sure that every call use O(m) operations . It can be something like O(m+n) but it's compexity must depends of m (your compexity doesn't depend of m)

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

    You are right, if we want to be strict total complexity is . Look at the lower and upper bound before binary search in the solution.

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

Where can I find the I/O test cases for problem B? I need it because my code fails test 7 and i want to find put what is so special about that test.

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

    You cannot, but I see from checker log of your submission 11559886 that your solution cannot be obtained by swapping letters of input string.

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

      Yeah, I know, but i can't create that bug :(

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

        One thing you can do is:

        1) make test cases by yourself.(I usually write script. it's not that hard)

        2) Run someone's AC solution and your solution

        3) Compare outputs

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

        Test which your code fails contains 100000 "a" characters in string a, and b = c =  "a".

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

In problem D, why the case l=63 and l=64 has 0 as answer ?

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

It seems to me, or E is easier than C and D? There is the obvivous usual sqrt-decomposition. I think many people would solve this problem, if it were C or D. Because so many of the participants look at the complex problems after the contest, as they do not solve B, C, D, and have no reason to look any next. All the more that the time limit allowed to send the solution with the high constant (I have send solution for q*(6*sqrt(n)*log(sqrt(n))+n) instead of the author's q*sqrt(n)*log(sqrt(n)). Thanks for the contest!

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

    10 seconds is probabily too high for time limit, but Zlobober proposed this. Problems B and C are harder than usual, but I don't see why is problem D so hard. From my point of view, it has quite straight forward solution, but there are cases that require extreme care when dealing with them, and it proved to be wrong not to put them in pretests.

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

      Yes, you are right. Though I think D would be even more interesting if n,k,l and m were all <= 10^18.

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

        Any ideas on how we will handle it if l was not guaranteed to be a power of 2?

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

          Given the constraints in the original problem, I can't think of any solution.

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

Keep doin' it til' ya do it :)!

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

    I had some 30 incorrect submissions in this problem :( But got it finally :)

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

Problem D. Can someone explain me? Why for test 3 3 2 10 answer is 9? In my opinion, answer should be 5. All possible combination Thanks!

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

Is there an online/offline solution of Problem E using Segment Trees? Someone has asked before, but no one answers. Here is my submission Yeah, its worse case will get O(nq), cannot pass the problem, and I also got TLE on test 12. Just because these times I was practicing the segment trees' pros, I hope someone can help me. I will appreciate it if someone has the answer.

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

    No, couse there no function to update a segment with O(u) < O(n) or I can`t imagine this function=)

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

      thx all the same. I also cannot think function to maintain that — -

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

For Div. 2, Problem B, why does it not work to:

  • count the number of occurrences of each letter
  • find the maximum number of B that will fit in A
  • find the maximum number of C using what's left in A
  • repeat this process but with string C first
  • take the larger of the two answers
Example
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this test case, aaaaaabbbbbb aab abb

    Your solution gives output as 3 (aab aab aab OR abb abb abb), while optimal solution is 4, aab abb aab abb.

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

nikola12345 my solution for problem E have the same complexity as yours but it give me TLE what's wrong this is my code 11586909

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

For Problem C:

Here is my submission.

Can anyone help me with a test case?

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

    In your can funcn, since you re using forward approach, when you use a single student to finish more than one jobs, you need to subtract the time needed to traverse from one position to the other. You haven't considered that.

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

It is a strange problem. The program works correctly in my pc but gives me a wrong answer when submitted. To be precise it shows that my result is 0 while when the same code is run on my pc the answer that comes matches with that of jury's answer. Here is the submission link: 11593383

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

    I think you're having the same issues I did. Switch 1l to 1ll. (if you use 1l, then if the parameter l >= 32 then (1l << l) would wrap around since 1l is interpreted to be a 32-bit integer. This makes your program pass the check (1l << l) <= k and return 0 prematurely). Not sure why; difference in compiler? Also, be careful with subtracting and mod in C++. For instance, -1 % 3 evaluates to -1, not 2. You can just do (-1 + 3) % 3 to be safe.

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

1

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

For problem E, it seems that a lot of the solutions that use a map based implementation (within each group, map from integer y to its earliest and last occurrence) goes over the time limit, while the sorting implementation (as described above in the editorial) does fine. This seems bizarre to me as the map based implementation shouldn't be any slower asymptotically (and perhaps as faster update if we use a hash map). Why might this be? This seems to be due to the higher efficiency of a C++ vector. But in that case, the input sizes seem to be a little harsh and unnecessarily eliminating the map-based solution.

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

In the editorial of problem D you wrote — \t{(number of ways bit is 0)}. Is it a typo? I'm asking because that '\t' doesn't make any sense. BTW, problem D was really great!!! :D

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

    I think the \t is just a byproduct of latex/formatting. He just meant 2^n — (number of ways bit is 0).

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

Cannot get AC for problem D 551D - GukiZ и двоичные операции.

Here is my code: 11604669

I'm getting WA on 10th test case

1000000001 1000000002 37 1000000007

Output: 187032448

Answer: 472514342

Can someone give me an idea where I'm wrong? Thanks in advance

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
    if ((k & (1L << bit)) != 0)
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      What is wrong with it? There is some overflow here?

      It seems that it's not the only problem in my solution, because changing that check to if ((new BigInteger(Long.toString(k))).testBit(bit)) gives WA on 16th test case 11607178

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

        Yes.. An overflow. Don't need to use BigInteger. Long is enough.

        for (int bit = 0; bit <= Math.min(l, 63); bit++) {
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, I already wrote it using Long, but it didn't help to get AC.

          So & can be used only for Integer, not Long?

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

            You should modify the last cycle as above.

            & can be used for both of them. The problem was in (1 << bit) which is an Integer, but bit was > 31, so you got a negative value.

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

              Ahhh.. Ok, understood now! Thank you

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

      It's interesting that I have a line above if (l < 63 && k >= (1L << l)) {

      that uses 1L not 1 :-)

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

My solution in B div2 got WA on test 12 .. My code idea depends on get how many string b i can get from a then how many c ... then replace b , c and maximize the result .

is that a case that this idea didn't work ? or can anyone provide me a sample test to drop this ? http://mirror.codeforces.com/contest/551/submission/11568722

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

dp(i) = dp(i - 1) + dp(i - 2)
What is the idea behind this equation in problem D ?

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

Hey I wrote this code for problem C the strategy that I implemented was

For every time unit if number of students is greater then the number of boxes then the difference of student and boxes will forward to the next box and the remaining will take care of the boxes.

So on each step student will start from the beginning on each block a[i]/m student will stay whichever is minimum and rest will go to the next stop. until all the boxes are picked.

Got wrong answer on test case 4 can anyone please tell me what is wrong with this strategy.

submission

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

can anyone tell me where did i do it wrong?11836732

Thanks

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

I was trapped into some terrible small mistakes solving Problem D! First I got WA10, because the number (1<<64) can't be expressed so you can't check by if(k>(1ULL<<l))! And then I got WA18, I surprisely found out that m=1... So we should initialize ans: ans=1%m but not: ans=1!!!

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

Getting wrong answer in Problem E on 53 no test case... Can't see the test case... Can anyone help me? Here is my submission: 11946047

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

how to prove complexity of C ? Why the complexity is (n+m) ?

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

Problem C: why doesn't this approach work? The time taken overall to reach the boxes will always the the index of the farthest non-zero pile of boxes. What we really have to do is only distribute the boxes among the students in optimal time. How does it matter if we send the first guy to the last non zero pile and then send other people? Every non zero box has to be covered atleast once. Also it seems counter-intuitive to me that me send the first guy to the last pile and then send other people. He will have to cover the distance all the way and plus the time taken to come backwards. Instead, why can't we assign the a sequence of boxes from the start to end?

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

    I know this is late, but it's possible to accept this problem by subtracting from the front. ( it actually makes much more sense to me..).

    I'm also doubtful about subtracting from the end...

    Here is the submission, remove first greedy approach.

    http://mirror.codeforces.com/contest/551/submission/15264958

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

      Yes, it is the same thing. For us, substracting from the behind was more natural, but both approaches are correct.

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

        I am unsure if this is a correct way to prove both ways are similar so please correct me if it is not the case. First the array can be flattened so that for each a[i] we include a[i] indexes. Therefore the array will contain the sum over a[i] indexes. Next we note that all optimal answers are to be partitions on this new array. Lets denote f(i) to be the maximum index we can get to if we start choosing all elements from i. Let's also create f^-1(i) to be all the elements we can get to if we do the operation starting in reverse from i. It can be seen that f^-1(f(i)) = i. Now in the worst case we have f^m(0) = N. Through algebra we can see this implies f^-m(f^m(0)) = f^-m(N). Or 0 = f^-m(N). This means that in worst case if we apply the operation m times from front it also means we can apply operation m times from back. In cases other than worst case we have similar but always better results.

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

    the first guy doesn't need to come back

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

Could anyone please help me? Problem E. I don't understand what's wrong with my solution... 14473801

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

damn, solution to problem E is awsome

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

In Problem D, can someone explain how dp[i]=dp[i-1]+dp[i-2] ?

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

Using Hash tables for problem E could offer a better time complexity $$$O(n + q \sqrt n)$$$.

→ Reply