Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

KAN's blog

By KAN, 22 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +71
  • Vote: I do not like it  

»
22 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Is there a specific reason for having N = 106 in the 3rd problem ? This makes it almost impossible to solve it in Java.

I had 2 submissions with 100% idential complexity, number of iterations, the one in Java gave me TLE, the one in C++ gave me AC.

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

    Good day to you,

    well the reason might be (in my humble opinion) to get rid of O(Nlog(M)^2) solution (I've tried it and got TLE).

    I know it is naive, yet if you (in each binary-search body) copy all possible elements and sort them (with some basic sort algorithm) you will get such complexity (and also TLE :P)

    So that is what I imagine as reason

    Good Luck & Have Nice Day ^_^

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

      Problem C, and not D

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

        Oh apologies, I simply can't read :'(

        In this case, nothing reasonable came to my mind :/

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      For problem D, when n = m =10^6 and t =10^7, O(n(logn)^2) is really same as O(tlogm). But to my surprise, the former get TLE!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I wrote dfs using my own stack and got accept in 1 second in Java. But constraints are really bad :(

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

    I totally agree with you!

    My exactly the same algo (O(N)) got TLE in Java. Is it possible to get tests e.g. Test-12?

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem A, it seems OK to have a trailing space at the end of a list of numbers. Is this standard in Codeforces (i.e., trailing spaces are ignored)?

By the way, I LOVED, LOVED problem A. It looked sooo clear and simple but I just couldn't wrap my brain around it until the very end. It was really infuriating!! And even then I didn't end up with the intended solution which was really beautiful.

"Implementation problems" are often just a bunch of boring details. This one was a real gem!

»
22 months ago, # |
  Vote: I like it -7 Vote: I do not like it
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I've already mentioned it here.

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 3   Vote: I like it -8 Vote: I do not like it

      For D question,

      I have an N *Ackermaninverse of N solution i feel. which is based on pure simulation with greedy.It is working because of poor systests or is it fine(Can anyone say what is the exact complexity of my solution)

      code here

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

    so weak tests(

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another solution for problem D: - First, store all the cartons you can buy at the store in a vector and sort them non-increasing.

  • Then, iterate all the possible dates from the biggest one down, store a value to keep track of the amount of cartons that needs to be drank in the current date. Let's call this value cur

  • If at a certain moment, cur > 0, that means we have drank enough from this day forward. Update our answer using the vector of milk cartons. This can be done by using a pointer.

  • Therefore, our total complexity is O(N log N + t)

For more details, here is the code

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I got surprised to know that the intended solution uses the binary search. Many people actually did solve D using binary search.

    My solution is O(n log n + m log m), due to the costs of sorting two input arrays. The solving part is in fact greedy and linear O(n + m).

    The short description of the solution is as follows:

    • Sort cartons in the fridge and in the shop by the expiration date.
    • Each day, take at most K cartons from the fridge. If there is a carton left in the fridge due on today (or an earlier day), then output -1 and terminate.
    • Skip all the cartons in the shop that have already expired for the current day. Then buy some cartons such that the total number of drank cartons is at most K (sum it up with what Olya has drank today from the fridge).
    • Terminate if Olya has drank no cartons today and output the result.

    Link to the Java code

»
22 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Hello, Can somebody please explain why my solution here receives a TLE, even if the solution complexity is the same as in the presented solution? Thank you :D

»
22 months ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

yay! :) Then I can consider my O(107 + m) solution for D pretty good. :)

»
22 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Solution for B: ~~~~~ ~~~~~

long min = 0;
        long mins = ts+t;
        int pl = 0;
        for (; pl<n; pl++) {
            if ((ts+(pl)*t+t<=tf) && (ts+(pl)*t+t-(mas[pl]-1)<mins))
            {
                mins = ts+(pl)*t+t-(mas[pl]-1);
                min = mas[pl]-1;
            }
        }
        System.out.println(min);

So easy...

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone help me understand why my solution to problem D is getting TLE???. I am pretty sure complexity is O(10^7+n+m). Shouldn't it get accepted???

My solution

Please help me.....

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    When dealing with large input size with C++, consider desyncing the IO stream by "ios_base::sync_with_stdio(false);", or use printf/scanf to improve IO time.

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

      Wonderful!!!!!! Very much thank you.

      Could you please explain it to me why and what happens by adding above statement in code??? I haven't came across such thing till now. Hope I don't sound stupid....

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, could someone write more detailed explanation of C problem, I still don't understand how the second case works, even though I took a look at a couple of solutions and read the editorial.

Any help would be greatly appreciated, thanks!

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

    The first sample in the problem is illustrating the second case, which v1 = 1 and v2 = 4. As you can see, neither v1 nor v2 is the ancestor of other. Also, s1 = s4 = 5 = x / 3. You can take a look at the explanation below the statement.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please help me in question C.I have created a tree and used recursive calls to find sum.Implementation is O(n) but still it gets time limit exceeded in Testcase 12. Please check my solution and tell me the problem please. Code is with proper comments. Thanks http://codeforces.com/contest/767/submission/24804939

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

The solution is much more simple that the author's. Do DFS from root node, and for every subtree, can calculate the total heat using regular tree DP. Then, when returning the value, if the total heat of subtree is equal to total heat of whole three / 3 then set to 0 in order to avoid double counting. Code explains the concept much better than words, in my opinion.
Code: 24764409

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, Both cases can be handled by this trick —

"While calculating sub tree sums, If you find a node with sub_tree_sum == sum/3 then do not add this sum to it's ancestors :D"
This will solve the first case as well as second case.

Now you just need to find just 2 such nodes :) Which can be memorized while calculating the sums. If if we can't find at least 2 such nodes then there is no solution.

My Code — 24812043

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Ques C was a nice Question . Given it was direct but few tricks involved .

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried solving D using binary search similar to what was described in this editorial but I still get TLE.

My submission can be found here. It's time complexity is logm * ( n + m (for merging) + n + m (for checking if we can buy middle cartons) ) so I don't see why it get TLE.

Any ideas?

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

427896

Why is my C WAing?