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

gp of yuquan
Автор moscow01, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

What is test 7 in problem M?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

        → Ответить
»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

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

→ Ответить