hanfei19910905's blog

Simple solution to vk cup Qualification Round 1 and 2
By hanfei19910905, 8 years ago, In English,

Qualification Round 1

A 158A - Next Round

Just sort. Notice 0 in the array.

B 158B - Taxi

Choose the 3 and 1 as much as possible. And let 2 combine with themselves. If there are more 1s and 2s, let two 1s combine with 2, and every four 1s take same taxi.

C 158C - Cd and pwd commands

Implement with stack. If the string begin with '/', let top = 0, else remain the top; Then process the substring one by one, when meeting ".." , top--; else remain the top;

D 158D - Ice Sculptures

The number of new regular polygon's edges must be the factor of the given polygon. Listing all the factors take O(sqrt(n)) time. Then choose the best point take O(n). So the time complexity is O(n*sqrt(n)).

E 158E - Phone Talks

It's a classic DP problem. Array dp[i][j] stands for the min rightmost endpoint when choosing at most j segments from the first i segments . dp[i][j] =dp[i][j] = min(dp[i-1][j-1], max(dp[i-1][j],left[i])+length[i]). When the dp array is completed , find the max value of left[i+1]-dp[i][k] and rightmost point — dp[n][k]. Totally take O(n*n).

Qualification Round 2

A 159A - Friends or Not

Compare every two records and find the right friends. Give every name a unique number so as to avoid counting same friend twice. If a and b is friends, let friend[a][b] = true.

B 159B - Matchmaker

Establish two hash tables counting the number of the size (say 2) exiting in set makers and set caps. Obviously the sum of min number of every size in two sets is the first answer. Similarly establish two hash tables in order to count the number of the same size and same color. The hash function can be hash(color, size) = color*1000+size.

C 159C - String Manipulation 1.0

Because the length of string is at most 100*2000, so we can build 26 line-segment-trees to count the 26 Latin letters. The way to build tree and find the position of K-th letter is quite simple if you under stand line-segment-tree :)

D 159D - Palindrome pairs

A dp method is really great~ , sum[i] stands for the number of palindrome string in the first i letters. palindrome[i][j] judges weather the substring i...j is a palindrome string. dp[i] is the answer for the first i letters. dp[i] = dp[i-1]+Sum( palindrome[j][i]*sum[j-1] ) for all j<=i && j>0 . sum[i] = sum[i-1]+Sum(palindrome[j][i]) for all j<=i.

E 159E - Zebra Tower

sort the array with compare condition (cube[i].color < cube[j].color ||(cube[i].color==cube[j].color && cube[i].size>cube[j].size)). Then for the first i cubes , there is a array Max_cube, Max_cube[j] records the max sum of j cubes' size with same color. To the cube i+1, if it's the k-th largest size of its color. Compare the answer with cube[i+1].size + max(Max_cube[k],Max_cube[k+1],Max_cube[k-1]). The time complexity is O(n*logn).

Forgive my poor English :)

gl and hf tonight!

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

Comments Comments (30)
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In 159D - Palindrome pairs, if you know a method to find all the subpalindromes fast, you can get a better than O(L^2) solution:

  1. Make two Segment Trees for counting the starts and the ends of palindromes.

  2. If a palindrome(for example, odd) has center at position K and maximum length 2 * D + 1, then: 1 palindrome starts in K and ends in K, 1 starts in K — 1 and ends in K + 1, ..., last starts in K — D and ends in K + D. So, for adding their ends and starts in O(log L), we use segment updating.

  3. What is the answer on the task? It's just a sum: for all K = 1, 2.., L — 1 we multiply the number of palindromes, that ended in K(exactly), and the number of palindromes starting later, i.e. st[K + 1] + st[K + 2] + ... + st[L]. Each number we can get in O(log L), using ST.

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

I am quite new to sport programming so I have never implemented a segment tree. I heard about it, though, but thought it was complicated. Anyway, I think my solution to 159C - String Manipulation 1.0 is quite neat :)

In short: binary search in a Fenwick tree.

Slightly longer: we start out with 26 arrays, all filled with 1's and having a length of k*repeats[c], where repeats is an array containing the number of occurrences of each character in the initial string. Then, we build a Fenwick tree on top of each of these arrays. After that, we start processing the request. For each request p_i, c_i, we perform a binary search in the corresponding Fenwick tree in order to find the leftmost position with p_i 1's before it. Then, we replace the 1 in that position with a 0. Each search takes O(log(k*repeats[c_i])) queries to the Fenwick tree, each being of O(log(k*repeats[c_i])) complexity, which yields O(log^2(k*repeats[c_i])) per each request. The entire complexity of the algorithm is O(n*log^2(k*|s|)).

After processing all requests, we extract the result by merely moving through the input string k times, each time either printing the corresponding character (if there's a 1 in its array) or omitting it.

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

I was trying a tree solution for C, but was getting wrong answers and eventually decided to make a solution that supposedly took advantage of the fact that the string is cyclic. Yet in reality, I think it can easily become a solution that needs O(sqrt(|ss|)) time to process each command. (Where ss is s repeated k times) (Currently it is O(|s| + k ).

There are initially k fragments of the ss string what you could do is for each of the k fragments, ad each letter, know the number of times the letter appears in the fragment and the positions of those appearances.

Now, in order to delete the P-th instance of a letter in the overall string (ss), you can first do a O(|k|) loop to find the fragment that has the p-th instance (Use the sums for each fragment instead of going through the letters in the fragment manually). After you find the fragment, you can use a O(|s|) loop to naively remove the [p — (sum of the letter counts of previous fragments) ]-th instance of the letter in the fragment.

This only looks like abusing the format of the string, because you can adapt it to work in O(sqrt(|s|)) time for any string (not just cyclic). So, let's say that ss has |ss| elements, you can always split it into O(sqrt|ss|) fragments of O(sqrt|ss|) letters each. The overall complexity would become O(sqrt|ss|) per step. The constraints make this good enough.

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

I am trying understand the 158E Phone calls solution but it seems a little complicated for me. In my little experience with dp I haven't found a problem like this. Could you explain the solution in more detail? Please!

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

    Suppose we processed the first i calls and j of those were ignored, the best way is to minimize the last minute of conversation (i.e. maximize the length of freetime until the current moment). It's the meaning of dp[i][j]. If you still can't get it, feel free to point out what you are confused :)

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

      Problem is, topicstarter's formula for dp[i][j] is wrong. It should be:

      dp[i][j] = min(dp[i-1][j-1], max(dp[i-1][j],left[i])+length[i]), not

      dp[i][j] = min(dp[i-1][j], max(dp[i-1][j-1],left[i])+length[i])

      Here is my submission with this solution: 1355912.

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

        In my opinion, understanding its meaning is more important. If you know how it work, it isn't difficult to get the correct formula.

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

          The meaning is pretty straightforward. Suppose that you know, for all previous i's and j's, the least time at which all calls end. You are currently considering whether it is a good idea to add the current call to the ones you omit, or not. This depends on the time all calls are going to end at.

          • If you choose to omit it, you need to look at the time at which i-1 calls ended, and you dropped j-1 of them (because the newly dropped call is going to be the j-th).

          • Otherwise, you're going to look at the time at which i-1 calls ended, out of which j were dropped (since it is always preferable to drop as many calls as possible). Then, you should find the time at which the i-th call is going to end. Since you already know when i-1 calls ended and when the i-th call is supposed to start, you should find the time at which it actually starts — by merely taking a maximum. After that, you just add its length to the time it starts.

          You are interested in minimizing the time, so you take the minimum.

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

            Thanks for your replies! I was out for a day and I was unable to reply. Already understand the solution.

            I am used to solve DP problems with top down strategy using recursion since it's easier to me to understand the solution.

            I know that recursion is expensive and it should be avoided when possible so I am trying to change my strategy.

            Thanks again!

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

            Thank you very much that made it very clear, just started learning dp, I would never have got it if you didn't posted this, it's been 7 years, since this post was made, but I wanted to ask a question, how do you form the base case that is what values must be stored initially in the two-d array dp[i][j]? is there a procedure you follow, what do you check or think before you form dp[][] for initial cases. thank you

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

        thx for correcting my mistake :)

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

          if somebody can help me here in 158b, my test case 74 is wrong but my code seems to be okk. its in gnu c++ 4.6

          include

          using namespace std; int main() { long n,ne,i,count=0,newe,fours=0,three=0,two=0,ones=0; cin>>n; short s[100005]; for(i=0;i<n;i++) { cin>>s[i]; if(s[i]==4) fours+=1; else if(s[i]==3) three+=1; else if(s[i]==2) two+=1; else ones+=1; } count=fours;

          count+=three;
   if(ones>=three)
   ones-=three;
   else
   ones=0;
   newe=two/2;
   count+=newe;
   two=two%2;
   ne=ones/4;
   count+=ne;
   ones=ones%4;
   if(ones==3&&two==1)
   {
            count+=2;
            cout<<count;
            }
            else if(ones<=2&&two==1)
            {
            count+=1;
            cout<<count;
            }
            else if(ones<=2&&ones>0&&two==0||(two==1&&ones==0))
            {
            count+=1;
            cout<<count;
            }
            else
            cout<<count;




            return(0);
            }
          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

was somebody able to solve D using python? I implemented the DP solution above but I run out of time in test case 9 and the subsequent ones.

On my machine python finds the solution in ~9 seconds (past the time limit).

how can I find out if somebody ever solved this problem in Python?

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

This is not tutorial of VK 2015, can some body remove the tag?

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

Here is my Solution for 158D - Ice Sculptures: 15272199 My ans got WA in test case 39. Can anyone help finding my bug.

Thanks in advance.

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

Thanks for all!

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

B taxi. wrong answer on 67. can't even see inputs!

http://ideone.com/cTEsEx

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

Can someone help me with 158B - Taxi ? I did exactly as this editorial guides, I took the number of 4's and added them to the number of taxis, then I combined the 3's with 1's. Now, either (i) 3's are in excess or (ii) 1's are in excess or (iii) none of the 1's or 3's are left.

I combined the 2's with themselves. Now, either (a) an extra 2 is left or (b) isn't. Taking these 6 cases:

(i)(a) I added the number of 3's left to the answer and the 2 goes in a seperate taxi.

(ii)(a) I added at max two 1's with the 2, and then combined the remaining 1's in groups of fours.

(iii)(a) only that last 2 is left, which goes separately.

(i)(b) I added the number of 3's left to the answer.

(ii)(b) I combined the remaining 1's in groups of four.

(iii)(b) nothing is left, everyone has been grouped.

It seems to work, but I'm getting a wrong answer on test case 66. (49551813) The test case is too big and isn't shown fully. I can't find where it's wrong. Can someone help?

→ Reply