haleyk100198's blog

By haleyk100198, history, 3 years ago, In English,

Merry Christmas everyone

As the editorials of Technocup rounds usually comes later than expected, I hope that this problem analysis could help out whose wants the questions immediately.

Div2A: Santa Claus and a Place in a Class

This is a trivial implementation question, by a bit math we could derive that:

Number of row: (k-1) // (2*m)

Number of desk: ((k-1) mod (2*m)) // 2

( x // y means the integral part of x/y )

And the side of the desk solely depends on the parity of k, as each row has even number of desks.

C++ solution:

Div2B: Santa Claus and Keyboard Check

We could solve the question by saving the status of the keys, i.e. not pressed, swapped in pairs, or confirmed in original position, initially all keys have the not pressed status.

When iterating through the pattern, if we’ve found out that the matching of line1[i] and line2[i] different from the current status, we output -1. Finally, we output whose has the swapped status.

One of the hack cases that have gained a lot of points is by exploiting some codes which does not keep the “confirmed in original position” status, which conflicts against the “swapped in pairs’ status.

C++ solution

Div2C: Santa Claus and Robot

Intuitively, we can tell that if the robot changes the vertical / horizontal direction, then the current position of the robot may lie one of the point.

One of the way to approach this question is by keeping whether the robot is free to change it’s vertical or horizontal direction without declaring an extra point. Obviously, when a new point is reached, the robot is allowed to change it’s horizontal and vertical direction for once. By greedy we will make use of this “free to change” status and add points only when we must, thus reaching the minimized amount of points.

C++ Solution

Div2D: Santa Claus and a Palindrome

A key observation is that all strings have the same length, therefore if a string: “111 222 333 444 555” is a palindrome, so is “222 111 333 555 444”.

In order to effectively process the strings, we group the strings and sort their beautiful value (In C++, use std::map<string, vector > does the job.)

Next, we class each string into one of the following conditions:

  1. The string itself is not a palindrome We will reverse the string to find it’s “counterpart” (i.e. concatenating the two strings would produce a palindrome). We greedily select the largest pair available from the two groups until it is not profitable.

  2. The string itself is a palindrome This implies that the string could be used alone (to be placed right at the middle of the final string), or be used twice just as the other case. As the alone string case could only occur once, we shall greedily update the beautiful value of the alone string. This is left as an exercise to the reader.

C++ solution

Div2E: Santa Claus and Tangerines

Note that if we don’t have enough tangerine to spare, we would always to divide the largest ones first.

Using this fact, we would iterate the joy from 1e7 to 1. If there is enough tangerine, we immediate print that as the answer, the question now reduces to maintaining the amount of tangerines.

We could maintain it by keeping track of all tangerines that we have already counted, to avoid duplicated calculation of the partial parts of the larger ones, we could use another array to make a mark at (Size+1) / 2, as we the amount of tangerines collected effectively increases only when we also include the tangerines of Size/2.

If there is no solution even for joy = 1, print joy = -1.

C++ solution

Div2F: Santa Clauses and a Soccer Championship

http://codeforces.com/problemset/problem/700/B

This is an easier version of Div2F. The main idea is to make use of the fact that the most expensive solution will have all its’ path going through the centroid of the tree. Yes, that is exactly what we needed, we could therefore conclude we only need one city to accommodate all teams, don’t be fooled.

Read this editorial, and the discussions in the blog to learn how to find the centroid of the tree for this question.

http://codeforces.com/blog/entry/46283

The rest to do is grouping, we can do that keeping track of the dfs traversal order, which is relatively easy compared to the main dish.

C++ solution

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

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

Auto comment: topic has been updated by haleyk100198 (previous revision, new revision, compare).

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

*For problem D: I don't think that you need to hash. Just assign each string and its reverse an index using map. It should be fast enough.

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

    Yes indeed.

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

      By the way, I just spend the last 5 minutes enjoying your F solution. Such a beautiful observation to match the first K in preorder with the last K in preorder. Have you seen this before or did you come up with it?

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

        It is not the first time that I use this matching approach. I probably read it somewhere else at the first place, but it is a few months ago so I can't tell where I read it from.

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

Auto comment: topic has been updated by haleyk100198 (previous revision, new revision, compare).

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

The first problem (A) can be solved naive.

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

Hi! In your solution to D, why do you ignore the case for str > t?

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

    This is because the code have already considered the beauty gained when we iterate t. For each pair of palindromes we will iterate it twice (or once, if there doesn't exist a pair of it in the list) but we only have to handle it once.

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

How much time does a map (in STL of C++ )take for look-ups when we use strings as keys. I mean what is the complexity of find() when I am using it with map<string,int>.

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

    It would take O(logN) time. (If we assume string comparison takes O(1) time.)

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

      Can string comparison be done in O(1) ?

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

        No, but I just want to keep the O(logN) part clean as it is guaranteed for any maps.

        It could be done in O(1) if you hash it though.

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

          String comparison isO(length of string). Hash value calculation itself requires O(length of string).

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

Could anyone describe a fast way of counting the maximum parts of a tangerine such that each part >=(some value)?
I tried a recursive function in my bin-search solution(23330291) but it times out.

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

    A DP approach works fine (i.e. calculate first the number for tangerines of small size, and iterate). See my binsearch for example: 23322164

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

748C - Санта-Клаус и его Робот Hey, can you explain 748C in simple, didn't understand the question... robot was given a points but it remember it's unit movements, we need to find the minimum sequence, if the robot knows it's unit movements, we can know the entire sequence right??