moscow01's blog

gp of yuquan
By moscow01, history, 3 years ago, In English

What's the intended time complexity for E? Can it be solve in O(nk)?

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

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

What is test 7 in problem M?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    We had WA7. Our problem was too many executions on test a...aSb (98 A's)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We only executes 198 instructions on aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaSb, but still can't pass test 7.

      Is it correct that iterating through the instruction set (i.e. execution step 2) doesn't counted as instruction executed?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        As far as I undersatnd the whole loop is counted as one executed instruction (i.e find first instruction that matches and run it)

        → Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

For E we have a $$$O(nk \log n)$$$ D&C solution. We thought the TL is a bit too strict for it, but it passed in 1.237s anyway...

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Btw why did you solve so long problem H? :)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      We played the contest in the Pre-Finals camp, and we just didn't open problem H before ~ 3:00. Kind of weird that during the Pre-Finals camp, no one submitted H before us, so we thought I and K are easier :(

      → Reply
»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

This contest is prepared by Zhejiang University, a selection from the 19th Zhejiang Provincial Collegiate Programming Contest and 2022 Zhejiang University of Technology Programming Contest. The problem setter might upload all of these contests into Gym recently. And they also prepare the editorial for pre-final camp, which will also be uploaded.

I also received some questions (or even complaint?) about this contest. But note that I didn't even send an announcement this time since I know nothing about this contest...

→ Reply