Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### ouuan's blog

By ouuan, history, 10 months ago, ,

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.

• +74

 » 10 months ago, # |   +6 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.
•  » » 10 months ago, # ^ |   +1 Yes, I did the same but had to compute two different hashes for each string to avoid collisions. Could single hash work?
•  » » » 10 months ago, # ^ |   0
•  » » » » 10 months ago, # ^ |   0 Yup for 31 I had to use two hash. https://atcoder.jp/contests/abc141/submissions/7559498
•  » » 10 months ago, # ^ |   0 Hi, @StudyingFather can you help me with problem E. I have used the same approach as you said but it is failing on some test cases.My code using a single hash — codeThen I used double hash to prevent a collision but it still failed can you tell me what am I doing wrong, please.My code using double hash = codeBoth the codes are failing on handmade test cases on atcoder but large tests are passing.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 frost_ can you help me I have also done what you have done
 » 10 months ago, # |   +5 In solution of problem F , shouldn't it be taking the maximum subset XOR ?
•  » » 10 months ago, # ^ |   +3 subarray seems wrong... we should consider sub sequence...
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +6 Oh, I didn't check the GeeksforGeeks link, I meant subsequence.Fixed now.
 » 8 months ago, # |   0 Thank you! I am stuck at D Powerful Discounts, but I am working on it right now. But I'm doing fine when I saw your editorial. Again, thank you so much!
 » 8 months ago, # | ← Rev. 2 →   0 WAIT, I'm stuck now. Sorry... I'm on the 8th grade, and I'm stupid. Your proof to x/y/z = x/yz: x/y = pz + q, and pz+q/z = p is written.However, I don't understand 2 points. 1st, why does pyz+qy+r(x)/y is equivalent to pz + q ? Shouldn't it be pz + q + r? 2nd, why is pz+q/z = p? And where did the z come from??I'm so sorry I'm stupid, but could you explain this a bit easier? (Well, that is if you see this in the first place.) But again, thanks for this editorial.