Vovuh's blog

By Vovuh, history, 3 months ago, In English,

1003A - Polycarp's Pockets

Tutorial
Solution (Vovuh)

1003B - Binary String Constructing

Tutorial
Solution (Vovuh)

1003C - Intense Heat

Tutorial
Solution (PikMike)

1003D - Coins and Queries

Tutorial
Solution (Vovuh)

1003E - Tree Constructing

Tutorial
Solution (Vovuh)

1003F - Abbreviation

Tutorial
Solution (Vovuh)
 
 
 
 
  • Vote: I like it  
  • +39
  • Vote: I do not like it  

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

In E, won't the distance change upon inserting new edges and if yes, how to update the "maximal distance set" efficiently?

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

    The previous explanation was wrong, i had understood it now.

    If the distance for some vertex v will change after adding the new vertex, it means that we attach some leaf that increases the diameter of a tree. But it means that we attach a leaf to the vertex w with distw = d, but in this case we already doesn't have the answer.

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

    It is possible to prove that there exists such a tree iff n * (k - 2) <= -2 + k * (k - 1) ** (d // 2) for even n and n * (k - 2) <= -2 + k * (k - 1) ** (d // 2) + (k - 2) * (k - 1) ** (d // 2)for odd n. We simply check if conditions above are satisfied and proceed with making the tree or not.

    Edit: also, obviously it must be that n > d as said in the article

    Edit: k = 1 and k = 2 should be treated as special cases

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

:

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

My solution to F was to assign an integer to each distinct string (since there's a maximum of 300) while keeping track of lengths for each of these integers and then run a KMP search to find the number of occurrences of each valid subsequence. This solution runs in approximately the same time complexity as the editorial's.

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

There is an O(n) approach in problem C.

code

rough explanation

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

    your pish and pop operations aren't constant time operations.

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

      But each node would be push and pop 1 time.

      I don't know why so much downvotes.

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

        No idea why you're getting downvotes (that shouldn't matter tho, if you think your comment is constructive), your solution is very efficient.

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

          It is a classic method to optimize DP.

          I think I am doing nothing wrong to point it out in the case that editorial doesn't mention.

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

    It seems that people are likely to downvote algorithm they don't know.

    I think that is a very simple way to analysis the complexity, but it might be far too difficult for those rating is under 1600?

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

    Can you please explain your solution?

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

what wrong in problem F makes a lotta participants output 689 in test 6 instead of 581?

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

    Those solutions most likely did not consider more than two segments (only exactly two). The sample tests did not cover this.

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

what is wrong with my solution for D:https://codeforces.com/contest/1003/submission/39974183

or mby i am not getting editorial??

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

    I did not read your entire code, but why are you running for loop until x>=0 it should be x>0.

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

can anyone explain me the method for Problem C becoz despite several efforts i m unable to figure it out

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

    my approach is quite simple what I have done is to check for all segments the average temperature and we will consider which gives best answer and has size >= k my code

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

      Bro really thanks for ur help my approach is also quite the same but i got a TLE i m giving my code link plz help as I m beginner and really want to increase my skills http://codeforces.com/contest/1003/submission/39983625

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

        I think "accumulate" as a third for loop .So the complexity is 5e3*5e3*5e3 , it will give you TLE. In worst case if n is 5e3 and k is 1 .

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

          thanx bro ,,,, rest i think my algorithm is correct am I right??

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

            You're right,but in this problem you don't have to use "accumulate".Think in a different way.

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

              i fixed by using sum=sum+v[i];

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

                Try it : ) . If it gives you a wrong answer , think about "what is the wrong in your code and what is the test you will fail in ", if you don't know , tell me , I will help you : ) .

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

                  thanx bro ...i passed all the test cases... thanx for ur help

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

In problem D my code passed all pretests but it timed out on 27th Case in system testing. No wonder how. Code complexity Q * 32 * 32. Can someone suggest something? Code

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

    unordered_map operations works some more than O(1).

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

    U can easily adjust to only Q * 32 operations with a greedy strategy. A complexity has no constants is it. your complexity is O(Q) if you say so. Map operations are O(log) so the number of operations is even worse in your solution. Just adapt to O(Q * log(MAX_VALUE) + N * log(MAX_VALUE)) which actually is O(N * log(VAX_VALUE)) because N and Q constrains are the same. Now to adapt you can just do this:

    the solution
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain why it didn't pass even the pretests? (problem D, WA test 4)

Code

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

What do think is wrong with my sol for binary string problem here: http://codeforces.com/contest/1003/submission/39907389 I believe it runs perfectly on the four cases you mentioned in your blog

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

For Question B: Binary String Constructing, is there a recursive approach? Does anyone know similar problems like this, where it has a large number of generalized test cases?

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

why it times out on test 23?? (problem E) http://codeforces.com/contest/1003/submission/39989027 but if i assign the values of test 23 and upload the code here it will not time out!!: http://codeforces.com/contest/959/submission/39989086 why????????????? :(

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

anyone with better explanation of F using DP

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

Is it possible to solve problem D using Python?

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

can anyone tell me what does __builtin_ctz(x) do?

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

Why is a random_shuffle performed at the end of the code for problem E?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any O(nlogn) or O(n) method for C?