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

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

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

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

Hint 1
Tutorial

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

2288C - Reimu Hakurei and the Youkai

Hint 1
Hint 2
Tutorial

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

Hint 1
Hint 2
Tutorial

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

Hint 1
Hint 2
Tutorial

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

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

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)
  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

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

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

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

great A

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

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

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

WHY DP IN PROBLEM B

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

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

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

Isnt B1 just greedy? DP is a lil bit overkill

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

    What kind of greedy solution do you have?

    • »
      »
      »
      5 минут назад, скрыть # ^ |
      ← 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)

    • »
      »
      »
      4 минуты назад, скрыть # ^ |
       
      Проголосовать: нравится 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.
  • »
    »
    16 минут назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

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

Is it just me or this contest is kind of weird

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

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.

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

What were the problemsetters thinking?

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

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."

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

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