ouuan's blog

By ouuan, history, 5 years ago, In English

AtCoder Beginner Contest 141 has just finished, and this is an unofficial editorial.

You can check my solutions, but I used lots of defines in my codes, and they're hard to read.

C — Attack Survival

Let $$$cnt[i]$$$ be the number of times the player $$$i$$$ correctly answered a question. The player $$$i$$$ survived if and only if $$$q-cnt[i]<k$$$.

D — Powerful Discount Tickets

First, you have to know $$$\left\lfloor\frac{x}{2^k}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac x 2\right\rfloor}{2^{k-1}}\right\rfloor$$$(when both $$$x$$$ and $$$k$$$ are positive integers and $$$k\ge 1$$$).

In fact, it is true that $$$\left\lfloor\frac{\left\lfloor\frac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\frac{x}{yz}\right\rfloor$$$ (when $$$x$$$, $$$y$$$, $$$z$$$ are all positive integers).

Proof

Because of this, we can use a single ticket $$$k$$$ times instead of use $$$k$$$ tickets at one time.

Then, we can use a heap (or priority_queue) to maintain all the prices, each time choose the most expensive item, and use a ticket for it.

E — Who Says a Pun?

If we enumberate the split point, it will become a Longest Common Substring Problem.

For example, if we split the string into $$$[1,mid)$$$ and $$$[mid,n]$$$, we need to calculate the LCS of them, and the answer is the maximum LCS among all possible splits.

I used suffix automaton to solve it.

You can also use DP to solve it:

Let $$$f_{i, j}$$$ be the longest length if the first substring starts from $$$i$$$ and the second one starts from $$$j$$$.

$$$f_{i,j}=\begin{cases}0&s[i]\ne s[j]\\min(j-i,f_{i+1,j+1})&s[i]=s[j]\end{cases}$$$

The answer is the maximum value of all $$$f_{i,j}$$$.

F — Xor Sum 3

Consider each bit separately. Let $$$cnt[i]$$$ be the number of "1"s in the $$$i$$$-th bit (the bit of $$$2^i$$$), if $$$cnt[i]$$$ is odd, the sum of this bit is definitely $$$1$$$.

So, we only have to consider the bits with even number of "1"s. If the XOR of the red integers of a bit is $$$1$$$, then the blue one is also $$$1$$$; otherwise they are both $$$0$$$.

So, we have to maximize the XOR of either the red integers or the blue integers (only consider the bits with even number of "1"s), that's to say, find the maximum subset XOR of a given set.

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

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

I think we can also use hash+binary search to solve problem E.

Fisrt,do a binary search on the length. To check the length len is valid, I use hash to judge whether there exist strings that covered twice.

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

In solution of problem F , shouldn't it be taking the maximum subset XOR ?

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

    subarray seems wrong... we should consider sub sequence...

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      Oh, I didn't check the GeeksforGeeks link, I meant subsequence.

      Fixed now.