pilliamw's blog

Why so tight constraints for A?
By pilliamw, history, 9 months ago, In English

90% of Python solutions to A will get hacked or fail systests, since using the obvious ans += s[i] in a loop or similar will immediately balloon into O(n^2). My question is, why would one even need to consider this for a Div2A? It's not like it even adds to the complexity of the problem — the difficulty and algorithm would be the same for $$$|s| \lt 10^3$$$ or something. At the very least, have a pretest that's the trivial print(1) print('A'*200000) generator I wrote in 30 seconds, instead of leaving that to the hacking phase.

(To be fair, I'm pretty salty right now because I dropped from 2000 to 8000 after hacking my A. But I still think this is a pretty serious problem, especially for an educational round where problems have equal weighting... unless the goal was to educate me to not use Python ever again :/)

Update: Yep, I know that Python string concatenation is rather expensive now, you don't have to keep commenting that (although I appreciate everyone who responded :D). I guess the Educational Round succeeded in being educational! I still think that there should have been a strict $$$2*10^5$$$ pretest, but whatever, I'll take the L here. Now time to get back to Expert...

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
9 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Can't you just reverse sort?

→ Reply
  • »
    »
    9 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    thats what i did

    → Reply
    • »
      »
      »
      9 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it 
      #never using python again
t = int(input())
for _ in range(t):
    s = input()
    f = 0
    n = 0
    t = 0
    res = ""
    for c in s:
        if c == "F":
            f+=1
        elif c == "N":
            n+=1
        elif c == "T":
            t+=1
        else:
            res += c
    res += "T"*t
    res += "N"*n
    res += "F"*f #bruh
    print(res)

      is this reverse sort?

      → Reply
»
9 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

I'll be a bore but this can educate some people that python strings are immutable and are not based on vectors, so str += char is a heavy operation

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

so what is testcase which is hacking all python submissions

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Just print all the T's first and then the other letters :)

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

It is more of like lack of knowledge of Python. I too have encountered similar problem in my old days. Just use ''.join(arr) to join a list of strings it takes O(n) time. You can check it here.

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

    Fair enough, I used C++ for every other problem (string problems are easier in Python for me)

    → Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

is 'T' * cnt hackable?

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

use lists instead of strings

→ Reply
»
9 months ago, hide # |
 
Vote: I like it -17 Vote: I do not like it

use c++ instead of python

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Well, I think its pretty educational to know that strings are immutable in python. Furthermore, it seems like you did a lot more work for a problem that was just reverse sorting the string.

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

    It's been a day and I think I'll take the L on this one lol. Still sucks that there wasn't at least a $$$2*10^5$$$ test case in pretests, but whatever. Time to get back to expert...

    → Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I basically just randomly sort and reverse and got AC:/

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I also tried to hack but there was no option for room and so that's why I leave it btw if for eg I do hack someones submission then I got extra + rating or wt? (cuz haven't done bfr so asking)

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

    Hacking in the open hacking phase (which is available in Edu and Div3/4 rounds) does not award any points or ratings.

    → Reply
»
9 months ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

Round is educational, and it educated you not to use += for strings

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Try Python 3.13

→ Reply