Igor_Kudryashov's blog

By Igor_Kudryashov, 11 years ago, translation, In English

412A - Poster

One of the optimal solutions is the following. If k - 1 ≤ n - k then firstly let's move ladder to the left by k - 1 positions. After that we will do the following pair of operations n - 1 times: paint i-th symbol of the slogan and move the ladder to the right. In the end we will paint the last symbol of the slogan. If k - 1 > n - k then we will move the ladder to the right by n - k positions. After that we will also paint symbol and move the ladder to the left. Our last action will be to paint the first symbol of the slogan. Total number of sought operations is min(k - 1, n - k) + 2·n - 1.

412B - Network Configuration

In this task you should sort array in descending order and print k-th element. Due to the weak constraints you could also solve the problem in the following manner. Let's brute ans — the value of answer and calculate how many computers already have Internet's speed not less than ans. If there are not less than k such computers then the answer is acceptable. Let's find the maximum among acceptable answers and it will be the sought value.

412C - Pattern

Let's find the answer symbol-by-symbol. Let's consider i-th symbol. If there are two different symbols differ from '?' on i-th positions in the given strings then we must place '?' on i-th position in the answer. If there are '?' on i-th positions in all string then we can write any symbol. Obviously, it is better to write not '?' but any letter, 'x' for example. Lastly we should consider the case when there are only '?' and one the same letter on i-th positions. In this case we should find this letter and put it to the answer.

412D - Giving Awards

Let's build sought permutation by adding employee one-by-one. Let's we already define the order of the first k employees: a1, a2, ..., ak. Let's place k + 1-th after ak-th. If ak-th employee owe money to k + 1-th then we will swap their positions (and will get permutation a1, a2, ..., ak - 1, k + 1, ak). If ak - 1-th employee also owe money to k + 1-th then we will also swap their positions and so on. If all first k employees owe money to k + 1-th then k + 1-th employee will be placed first in permutation. This algorithm has time complexity O(m), where m is the number of the debt relationships.

412E - E-mail Addresses

Let's consider position i such, that si = '@'. We are going to calculate the number of such substrings that are correct addresses and the symbol '@' in them is si. Let's go to the left from i until we find '@' or '.' — the symbols that aren't allowed to be to the left of '@'. Let's calculate cnt how many letters on the segment we went through. This letters can be the first symbols of the correct addresses. Let's now move to the right of i while considered symbol is letter or digit. If we stopped and the string is over or the following symbol is '@' or '_' then there aren't correct addresses. If the following symbol is '.' then let's go to the right of it while the considered symbols are letters. The correct address can finish in every such position, so we should add cnt to the answer. In the described solution "move" means "brute by cycle for". We can do this because we will go through each symbol not more than 2 times. Total time complexity is O(n).

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

| Write comment?
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

there is a much easier way to solve D. explanation is here.

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

In problem D how do we find that the described order does not exist and print "-1"

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

    It's always exists.

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

      Omg.. can you please tell me how you figured that out ??

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

        I figured it out while making my greedy solution. It's takes out employee that has minimal amount of debts to those who wasn't invited yet. And what if we can't do a valid step? It means, the previous chosen (name him A) has debts to every employee remains. Then any of the remaining couldn't have debts to A. Therefore they all had less debts than him (he's got to all, and everyone else not to all) and we had to take someone of them instead of A. Contradiction.

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

If I follow the instruction of the 412D, which data structure should I use?

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

Hi everyone !

I have hard time with the problem D. My solution always fails on test 26 for an unknown reason. Thanks for helping.

Here's my code: https://www.dropbox.com/s/268jubesjbyld2b/email.c