Блог пользователя LNight121

Автор LNight121, история, 96 минут назад, По-английски

Thanks to everyone who participated in this round! I hope you enjoyed the problems! Apologies for the overly simplistic Div2D and the trivial Div1D(and the statements with poor readability). I think that the whole difficulty of Div1D lies in how people hack the solutions of other participants: if nobody hacks, this problem is easier than Div1C, but if somebody hacks, it becomes hard. I will explain this in more detail in the tutorial below.

2288A - Youmu Konpaku and the Duel

Hint 1
Hint 2
Tutorial
Code

2288B1 - Yukari Yakumo and the Boundary Stones (Easy Version) / 2287A1 - Yukari Yakumo and the Boundary Stones (Easy Version)

Hint 1
Tutorial
Code

2288B2 - Yukari Yakumo and the Boundary Stones (Hard Version) / 2287A2 - Yukari Yakumo and the Boundary Stones (Hard Version)

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Code

2288C - Reimu Hakurei and the Youkai

Hint 1
Hint 2
Tutorial
Code

2288D - Satori Komeiji and the Metro / 2287B - Satori Komeiji and the Metro

Hint 1
Hint 2
Tutorial
Code

2288E - Cirno and the Math Problem / 2287C - Cirno and the Math Problem

Hint 1
Hint 2
Tutorial
Code

2287D - Patchouli Knowledge and the String

Hint 1
Hint 2
Hint 3
Tutorial
Code with high-resolution clock
Code with sha-256

2287E1 - Marisa Kirisame and the Game (Easy Version)

My initial problem only had an $$$n \le 10^5$$$ version and an $$$n \le 500$$$ version; thanks to Error_Yuan for proposing this $$$n \le 10^4$$$ version.

Hint 1
Hint 2
Hint 3
Tutorial
Code

The idea comes from the power level settings of some fantasy works. In many fantasy works every character has a power level, and the levels differ wildly (for example, Tier 10 is an ordinary human, while Tier 9 is a superhuman). In this setting I created this problem, so that you can see how a battle between two groups should happen in such a fantasy world, and what the best arrangement is if a group wants to defeat another group.

2287E2 - Marisa Kirisame and the Game (Hard Version)

Codex did not pass this problem during testing, which surprised me a lot.

Before reading, please go through the hints of 2287E1 - Marisa Kirisame and the Game (Easy Version), but no need read its tutorial, because what follows is completely different.

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Code

This problem was originally conceived as a two-attribute version (attack power and defense power), but I only know an $$$O(2^n)$$$ solution for it.

Разбор задач Codeforces Round 1136 (Div. 1)
Разбор задач Codeforces Round 1136 (Div. 2)
  • Проголосовать: нравится
  • -26
  • Проголосовать: не нравится

»
71 минуту назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).

»
70 минут назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

great A

»
69 минут назад, скрыть # |
 
Проголосовать: нравится -19 Проголосовать: не нравится

I wonder why Um_nik didn't fucking slime you out for such terrible problemsetting

»
67 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

WHY DP IN PROBLEM B

»
64 минуты назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Why $$$n \leq 10^5$$$ on multiple problems if the intended time complexity is $$$O(n)$$$ or $$$O(n \log n)$$$?

»
64 минуты назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Isnt B1 just greedy? DP is a lil bit overkill

  • »
    »
    63 минуты назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    What kind of greedy solution do you have?

    • »
      »
      »
      47 минут назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      Im not very good at explaining stuff so im not sure if i can help you understand my approach

      I simply iterate through the string S

      At the current character Si

      -if Si = '+', then i'd want to duplicate a stone with power 2, if there is no stone with power 2 then i will just increase a random power 1 stone by 1, making it a power 2 stone

      -if Si = '-', then ill check if there exist more than one power 2 stones (because id still have atleast one power 2 stone left), and decrease that stone's power by 1, because deleting a power 1 stone makes the answer lower, if there is one (or none) power 2 stone then ill delete a power 1 stone instead, because i need a power 2 stone to duplicate more stones, and if there is no power 1 stone, then ill simply decrease the only power 2 stone left by one

      If at any step there is no stones left, ill stop

      Every step ill update the answer = max(answer, current stones)

    • »
      »
      »
      46 минут назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      We will apply all of the operations as we traverse through $$$s$$$. When we encounter a $$$+$$$, it is obviously better to use it on a $$$2$$$ rather than on a $$$1$$$ whenever possible. One useful observation is that we only really need one $$$2$$$ so that we extract the most benefit from $$$+$$$. Then the casework on '-' follows:

      1. If we have more than one $$$2$$$, then we can turn one of them into $$$1$$$ without any loss
      2. If not, then we have at most one $$$2$$$. This is to be proven, but it is always optimal to sacrifice a $$$1$$$ instead of losing that $$$2$$$, thus we should apply this $$$-$$$ to $$$1$$$ if possible.
      3. Otherwise, we only have a single $$$2$$$ left, and we can only apply this $$$-$$$ to it.
  • »
    »
    58 минут назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Of course, Greedy is possible, but initially I thought it might be too difficult, so I lowered the data range.

»
64 минуты назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Is it just me or this contest is kind of weird

»
60 минут назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

The time complexity of div1C's 5e4 square is absolutely absurd. I tried for an hour and a half to remove the O(logm), hoping to find special properties through mod2, but it completely failed. Why isn't this problem given a reasonable data range, such as 1e4/1s or 2e4/4s.

»
58 минут назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

What were the problemsetters thinking?

»
55 минут назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +2 Проголосовать: не нравится

You are not allowed to view the requested page. https://codeforces.me/contest/2288/submission/399348749

PS Why was my rating recalculated? Previously, if the first test case was not passed and no other attempts at a solution were made a participant’s status was set to "non-competitive."

»
52 минуты назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Wth is wrong with this B2 it's not wrth being B

»
37 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My solution for Div.1 E1 should be able to solve E2 in $$$O(n+m)$$$ time beyond sort without using data structures(only need two-pointers, which should be better than std in complexity beyond sort), but the sample for E1 was too weak that it took me about $$$20$$$ minutes for debugging, which means there wasn't enough time for me to solve E2 :(

»
35 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).

»
27 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Am I the only who thought we need to minimise the sum of all passengers time in D2D metro problem? Also is there any solution for my version of the problem in 2s time limit?

»
23 минуты назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Div2 A has $$$O(1)$$$ solution.

Let's say you do $$$a$$$ charges first then $$$b$$$ attacks. The total damage is:

$$$\begin{align*} a + (a-1) + (a-2) + \cdots + (a - (b - 1)) = b(a - b) + \frac{b(b+1)}{2}. \end{align*}$$$

The damage needs to be equal to or greater than $$$x$$$, so we have:

$$$\begin{align*} & b(a - b) + \frac{b(b+1)}{2} \ge x \\ \iff & a \ge \frac{x}{b} + \frac{b-1}{2}. \end{align*}$$$

This means that, if you decide to make $$$b$$$ attacks, the minimum number of charges required is $$$\displaystyle a = \left\lceil \frac{x}{b} + \frac{b-1}{2} \right\rceil$$$.

Then, the total number of moves is:

$$$\begin{align*} (a - 1) + b &= \left\lceil \frac{x}{b} + \frac{b-1}{2} \right\rceil - 1 + b \\ &= \left\lceil \frac{x}{b} + \frac{b-1}{2} - 1 + b\right\rceil. \end{align*}$$$

If you differentiate the function within the ceil bracket, you'll see that the function becomes minimum when $$$\displaystyle b = \sqrt{\frac{2x}{3}}$$$. Therefore you pick several integer values around $$$\displaystyle \sqrt{\frac{2x}{3}}$$$ as $$$b$$$ and the minimum value of $$$\displaystyle \left\lceil \frac{x}{b} + \frac{b-1}{2} - 1 + b\right\rceil$$$ among those $$$b$$$'s will be the answer.

»
18 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does the editorial imply there is a solution without reducing to XORs for D1C? (sorry it doesn't let me see their official solution. I thought using sums was way too slow since without optimizations, my XOR solution passes in 1.1s which is a bit much. (with pragmas it's 3x faster, but that is not the point here.)

»
15 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I wasn't even able to solve A

»
7 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

i am unable to see the code

»
5 минут назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by LNight121 (previous revision, new revision, compare).