LNight121's blog

By LNight121, history, 58 minutes ago, In English

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.

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
33 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
32 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

great A

»
32 minutes ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

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

»
30 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

WHY DP IN PROBLEM B

»
27 minutes ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

»
27 minutes ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Isnt B1 just greedy? DP is a lil bit overkill

  • »
    »
    26 minutes ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    What kind of greedy solution do you have?

    • »
      »
      »
      10 minutes ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      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)

    • »
      »
      »
      9 minutes ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.
  • »
    »
    21 minute(s) ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

»
26 minutes ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Is it just me or this contest is kind of weird

»
23 minutes ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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.

  • »
    »
    18 minutes ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Maybe you can test it on your own PC first? In my PC, 1e5/3s is completely fine. The solution to this problem runs unbelievably fast. Of course. I admit that 5e4/3s is too confusing.

    • »
      »
      »
      5 minutes ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      It doesn't seem like the correct time complexity, 5e4 seems to indicate that you need to find a way to remove this log in order to pass.

»
20 minutes ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

What were the problemsetters thinking?

»
17 minutes ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

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

»
14 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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