errorgorn's blog

By errorgorn, history, 4 years ago, In English

Sumitomo Mitsui Trust Bank Programming Contest 2019 has just finished, and this is an unofficial editorial.

Thanks to my friends oolimry and shenxy13 for helping write some of the editorial.

A — November 30

You can solve it simply by checking for each end date of the Gregorian calendar. However, note that as the second date directly follows the first date (a fact which I think is not clear in the English translation), we can also check whether they're in different months, or whether the second date is the first day of a month. This can be done in constant time.

Code

B — Tax Rate

We note that there is monotonicty in this question. $$$\lfloor 1.08(X+1) \rfloor \geqslant \lfloor 1.08X \rfloor$$$. Hence, we can binary search the answer. When we binary search the value of X(the answer), if $$$\lfloor 1.08X \rfloor = N$$$, then we have our answer. Otherwise, we can search higher if $$$\lfloor 1.08X \rfloor > N$$$ and search lower otherwise. If we find that no number gives us desired N, then it is impossible.

Code

C — 100 to 105

We can simply do a 0-infinity knapsack with weights 100,101,...,105 and check if some value is reachable. We get a time complexity of $$$O(N)$$$.

Code

D — Lucky PIN

First, we note that there are $$$O(N^{3})$$$ subsequences of the string, so generating all of them and using a set to check for number of distinct subsequences is TLE. However, there are only at most 1000 distinct such subsequences, from 000 to 999. We can linearly scan through the string for each of these possible subsequences to check if it is actually a subsequence of the string in $$$O(N)$$$. Thus, this can be solved in $$$O(1000N)$$$, which is AC.

Code

E — Colorful Hats 2

Firstly, we can imagine there are 3 imaginary people standing at the very front, each with a different colour hat. For each person, we consider how many possible people could be the first person in front of him with the same hat colour. If the current person has number X, then the number of ways is:

(no. of ppl with X-1 in front) — (no. of ppl with X in front)

This is because those with X in front of him must be paired with one of the X-1 already, so this reduces our options.

Implementation wise, we can store an array which keeps track of the number of people with no. X who are not paired yet. Initially, all values are 0, except at index -1 with the value of 3. Then when processing the current p[user:AtillaAk]erson X, we multiply the answer by arr[X-1], decrease arr[X-1] by 1, and increase arr[X] by 1.

Code

F — Interval Running

Firstly, if $$$T_{1}A_{1}+T_{2}A_{2}=T_{1}B_{1}+T_{2}B_{2}$$$, the answer is infinity.

Else, WLOG, we let $$$T_{1}A_{1}+T_{2}A_{2} > T_{1}B_{1}+T_{2}B_{2}$$$. If $$$A_{1} > B_{1}$$$, then Takahashi and Aoki will never meet each other. The answer is 0. Now, we have solved all the corner cases. We shall move on to the general case. We shall call the period $$$T_{1}+T_{2}$$$. Now, we shall find the number of periods where Takahashi and Aoki meet each other. If we do some math, we get the number of periods to be $$$\lceil \frac{T_{1}(B_{1}-A_{1})}{(T_{1}A_{1}+T_{2}A_{2})-(T_{1}B_{1}+T_{2}B_{2})} \rceil$$$.

The number of times that Takahashi and Aoki meet each other is $$$2periods-1$$$ since every period they meet each other twice when Aoki overtakes Takahashi and Takahashi overtakes Aoki. We need to minus 1 since we do not count the first time they meet each other at the very start. We submit this and... WA.

Yes, we need to think about the case where $$$\frac{T_{1}(B_{1}-A_{1})}{(T_{1}A_{1}+T_{2}A_{2})-(T_{1}B_{1}+T_{2}B_{2})}$$$ is a whole number. In this case, we need to add one, as there will be one more time where Aoki will meet up with Takahashi but never overtake him. And now we get AC. (Thanks to Atill83 for pointing out the mistake)

Code

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

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the approach described for task-D be accepted if the size of the string is 10^5. If not is there any better way to do it? Thanks.

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

    It may or may not be accepted 10^8 is a bit borderline.

    There is a way that runs in O(100N). It kind of works like dynamic programming, where at each point, we keep track of for each 1 digit, 2 digit and 3 digit code whether it is possible.

    So say the string is 1213 and we are processing the last digit (1). The currently possible 1 digits are (1,2), 2 digits are (12,21) and 3 digits are (121). For each 2 digit, we add in new possible 3 digit. So for 12 and 21, we add in 123 and 213.

    We repeat this process for 1 digit to 2 digit, and finally note that now 3 is possible single digit.

    The slowest part of our algorithm is going from 2 digits to 3 digits, where there is at most 100 2 digit combinations. Hence the run time is O(100N).

    Code: https://atcoder.jp/contests/sumitrust2019/submissions/8729957

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

    I just suddenly thought of another idea, this one runs in O(N + 1000logN).

    For each of the 1000 possible numbers, use binary search to find the leftmost position of the first digit. Then, use binary search again to find the leftmost position of the next digit that is on the right of the first digit. Repeat for the last digit.

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

For problem B, I don't know whether it's correct or not, but my first intuition was to consider two values of $$$x$$$ i.e., $$$\left\lfloor \frac{n}{1.08} \right\rfloor$$$ and $$$\left\lceil \frac{n}{1.08} \right\rceil$$$.

But, it turned out that only choosing $$$x = \left\lceil \frac{n}{1.08} \right\rceil$$$ and checking whether it satisfies or not was enough. My submission

I would be happy if someone posts a counter-example (if it's incorrect) or a proof (if it's correct).

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

    We shall let $$$f(x)=\lfloor 1.08x \rfloor$$$. The function $$$f$$$ is injective, which implies that its inverse $$$f^{-1}$$$ exists. We can show that $$$f^{-1}(x)=\lceil \frac{x}{1.08} \rceil$$$

    I think this is a sufficient proof??

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

      I am not that strong at maths, but isn't the existence of inverse possible iff the function is bijective?

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

        Im going to ignore the surjective part because we can change our codomain to only the numbers that have a valid untaxed price.

        But yeah youre right

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

I have a $$$O(1)$$$ solution for C. Code

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

    Can you explain your idea? Thanks.

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

      Since each item has a cost $$$\ge 100$$$, we only care about how to obtain the $$$(x \% 100)$$$ by purchasing appropriate no. of items. The idea is to buy as many items as possible so as to have more chances of obtaining the required cost below $$$100$$$. Since cost of every item is $$$\ge 100$$$, you can buy atmost $$$n = (x / 100)$$$ items. Now, you have to make $$$(x \% 100)$$$ using $$$n$$$ items where each item contributes $$$0, 1, 2, 3, 4$$$ or $$$5$$$. To minimize the no. of non-$$$0$$$ value items needed to achieve this, we greedily do this by taking items contributing $$$5$$$ and then one more item if the resultant is not $$$0$$$. This requires $$$m = \left \lceil \frac{x \% 100}{5} \right\rceil$$$ items contributing a non-$$$0$$$ value and some (possibly none) items contributing $$$0$$$. Now, you just have to check whether $$$n \ge m$$$ or not.

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

Can anyone explain how to get the number of periods in problem F? Thanks.

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

    So, Takahashi and Aoki will only meet each other if at the start of a period the distance between them is lesser than $$$T_{1}(B_{1}-A_{1})$$$. At first, the distance between Takahashi and Aoki are 0. After 1 period, the distance is $$$(T_{1}A_{1}+T_{2}A_{2})-(T_{1}B_{1}+T_{2}B_{2})$$$. So, for the $$$K$$$-th period, Takahashi and Aoki meet each other only if $$$K((T_{1}A_{1}+T_{2}A_{2})-(T_{1}B_{1}+T_{2}B_{2})) \leqslant T_{1}(B_{1}-A_{1})$$$. We can rearrange the equation to find the biggest $$$K$$$ period where they meet up.

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

I don't understand why "(no. of ppl with X-1 in front) — (no. of ppl with X in front)" would be the number of ways since we have 3 colours . Can someone explain this part ?

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

    Let A be the (no. of ppl with X-1 in front) and B be the (no. of ppl with X in front).

    We see that B must be less than A, and each of the B people must be matched to one of the previous A people. That leaves A — B people for us to map the current person to.

    Edit: by map, I mean that the person has the same colour hat as the person they are being mapped to. Sorry if my English is bad.

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

I think you have a mistake in F (Not in the code but in the editorial).

You said that if $$$T1(B1−A1)/(T1A1+T2A2)−(T1B1+T2B2)$$$ is a whole number, we need to minus one. This is false because $$$⌈T1(B1−A1)(T1A1+T2A2)−(T1B1+T2B2)⌉$$$ means the next integer greater equal to the fraction inside. Let's say the fraction inside is an integer $$$A$$$. $$$⌈A⌉$$$ will give $$$A$$$. If we do it your way. Our answer before the final paragraph is $$$2*A - 1$$$. However, because you told us to minus one once again if the fraction was a whole integer in the final paragraph, according to you we should print $$$2*A - 2$$$. I checked your code and it prints $$$2*A$$$ in these situations if I'm not mistaken.

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

    The answer is indeed 2*A-2.

    Its just in my code i floor instead of ceiling. Sorry for confusion

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

      I'm not really sure if our definitions for ceil is same. You used $$$q1$$$ and $$$q2$$$ for the fractions so I'm gonna use them. Let's say $$$q1 = 10$$$ and $$$q2 = 2$$$. In this situation $$$A = ⌈\frac{q1}{q2}⌉ = ⌈\frac{10}{2}⌉ = 5$$$

      your code prints $$$2*q1/q2 =2* 10 / 2 = 10$$$. Which is equal to $$$2*A$$$ not $$$2*A - 2$$$. If I know correctly, ceiling means next integer greater equal to this number. If the number you are ceiling is already an integer you return it.

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

        Oh my mistake. Thanks for pointing that out, will change the editorial

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

Can you please elaborate solution of 3rd question ,what's knapsack ??

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

    Google "Knapsack problem". It is a common Combinatorics DP.