LNight121's blog

By LNight121, history, 70 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
  • -12
  • Vote: I do not like it

»
45 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).

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

great A

»
44 minutes ago, hide # |
 
Vote: I like it -15 Vote: I do not like it

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

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

WHY DP IN PROBLEM B

»
39 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)$$$?

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

Isnt B1 just greedy? DP is a lil bit overkill

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

    What kind of greedy solution do you have?

    • »
      »
      »
      22 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)

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

        dang that's a weird greedy, I gave up on greedy after trying the first ones that comes to mind lol

  • »
    »
    33 minutes 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.

»
38 minutes ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

Is it just me or this contest is kind of weird

»
35 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.

  • »
    »
    30 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.

    • »
      »
      »
      17 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.

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

What were the problemsetters thinking?

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

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

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

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

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 :(

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

    Well, to me it seems like you have some weird code (writing multiple lines into one). Not saying you cheated, just saying you had some weird code.

»
9 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).

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

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?