at1's blog

Beta Round #4 - Tutorial
By at1, 15 years ago, translation, In English

A. Watermelon

Only if w can be presented as 2m + 2k watermelon can be divided to two even parts.
So w = 2(m+k), where m, k ≥ 1, that is
(w ≥ 4 и w - even) - necessary and sufficient condition for watermelon dividing.

B. Before an Exam

Problem restrictions allow one to use algo complicated as much as he wants. In my opinion the most simple way is written below.
  1. Fill studying time for each day sсhedulei with minTimei - Peter wants to study as less as he can
  2. Compute rest: need = sumTime - Σsсhedulei. if need < 0 than Peter can't satisfy lower bound of parents restrictions in schedule making: even if schedule is as small as possible he will go over the quota.
  3. In each day Peter has free studying hours: Δ = min(need, maxTimei - sсhedulei) - each day i Peter can additionally study. (With each day sсhedulei increase on Δ and need decrease on Δ).
  4. if need > 0 than Peter can't satisfy lower bound: studying with max power he has no time.
sсhedulei - is correct Peter's schedule if 2 and 4 not fulfilled.

C. Registration system

First, one can see the restrictions ≤ 105, that is he can expect n*log(n) solution.
Next, each string consist of "all lowercase Latin letters", that is it doesn't contains digits.
Because of it for each string we can compute what time we see it in the input. One needs to write "OK" for first request of current string, otherwise <string><computed number>.
This numbers can be computed by associate array (map in C++) or simple by sorting array of:
(string, number in input file),
sorted array would be splitted to blocks with equal strings. In each block one can set numbers from 1 to block_size.

D. Mysterious Present

Problem can be solved by dynamic programming approach for O(n2) by time and O(n) by memory.
  1. Sort all envelopes by pairs (wi, hi) or by product wi*hi in nondecreasing order. Because of it envelope i can be put in envelope j only if i < j. That is for any chain {a1, a2, ..., an} is true that a1 < a2 < ... < an.
  2. Just delete all envelopes in which card can't be put in.
  3. Add to sorted envelopes array a0 - Peter's card.
  4. Introduce DP function: dp[i] maximum chain length which ends in i-th envelope.
  5. dp[0] = 0, dp[i] = max(dp[j]) + 1, where i ≥ 1, 0 ≤ j < i and j can be put in i. This function can be easily got by previously computed values of it.
Problem answer is max(dp[i]), where 0 ≤ i ≤ n.
For each dp[i] one can remember index p[i] = j with which maximum reached in formula p5. If one knows s - envelope index in which maximal chain ends he can restore all answer sequence (i0 = s, ik+1 = p[ik]).
  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
At problem D, why do you have to add Peter's card to the sorted array if you already eliminated the envelops in which the card fits in?
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
*in which the card don't fits in 
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. If we have fake envelope with index = 0, such as dp[0] = 0 we needn't initialize all chains (exact n pieces) with dp[i] = 1 (1 ≤ i ≤ n), it would be done automatically by formula p5.
    2. Simultaneously we will get that all chains will start in Peter's letter.

    PS: In my solution from the contest I was creating chains from big envelopes to small (in decreasing order) and I add fake envelope with (w0, h0) = (+inf, +inf), dp[0] = 0. Because of I didn't catch that letter itself is better candidate to chain origin. And next I was choosing between chain ends in which card can be put in.
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i tried a problem in practice mode.. my code fails on test 6. How to find out what is test 6 input?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Usually, you can't see tests. But if you can't catch your bugs yourself for along time, you can discuss code with some other members (for example, problems from beta #4 can be discussed with me).  I think posting code on forum is wrong way and you can use personal messages.
    Second way - you can write to organizers and ask specific test on specific task. But do not abuse with it. This is the last that you need to do.
    → Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Can problem C be solved using binary search? We at first sort the strings and find the specific name using binary search.

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

excuse me, could you please explain the complexity of your solution for problem D? And why should we sort the envelopes by product wi*hi?

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

    1) One could compute max in any range of «dp» array in O(n) complexity. One must compute all dp[i] = max(dp[j]) + 1 in range [0, j) to get length of the longest sequence. Thus we get O(n²) complexity in my solution.

    2) To solve problem by my solution one must sort envelopes in such a way that if W[i] < W[j] and H[i] < H[j] than i < j

    So it could be stated that if in pair of envelopes one envelope could be put to another than lesser envelope should has lesser area and vice versa.

    3) This is classical problem: find longest increasing subsequence. Unfortunately, I can't give you links to english sources. I have this one e-maxx.ru/algo/longest_increasing_subseq_log.

    I hope it helps!

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

I solved D with an O(n²) memory approach using short int lol

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

The registration problem (C) I am confused if I take input as a list of strings within the range of the number of test cases. input_names = [abacaba,acaba,abacaba,acab] now I can't understand what is referred to the database here where should I compare the input?

I am trying to solve it in Python.

Thanks in advance

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

    Assume your system relies on a database which is any mean of your choice to persist what registration requests were received so far, for example, a set. So,

    • Initially your database is empty, DB = {}.

    • First, a user attempts to register with name abacaba. It is not present in your DB, so you can safely insert it and return OK. At this point your DB is DB = {abacaba}.

    • Secondly, a user attempts to register with name acaba, which is not present in your DB either. Therefore you insert it and return OK. Now, your DB is DB = {abacaba, acaba}.

    • Next, a user attempts to register with the name abacaba, but this time, you observe that this name is already present in your DB, so you cannot add it. Therefore, you need to make up a new user name by appending a number to it, in this case 1, resulting in the proposed user name abacaba1. Hence, you return this proposal and append this name to the DB, DB = {abacaba, acaba, abacaba1}.

    • Finally, a user attemps to register with the name acab which is not in the DB, so, as in the first two cases, you can just append it and return OK. After this, the state of your DB would be DB = {abacaba, acaba, abacaba1, acab}.

    If you look at the sequence of returned values you get OK, OK, abacaba1, OK. Now, in terms of implementation it would be convenient for you to know how many times a name was attempted, for which you might want to consider a C++ map or a Python dictionary.

    → Reply