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

Автор FreeJinG, история, 4 года назад, По-английски

Merry (Early) Christmas Codeforces community!

We are excited to invite you to TOKI Regular Open Contest #17!

Key details:

Finally, we would like to thank:

Please register to the contest, and we hope you will enjoy the contest!

UPD: The contest is over :)

Congratulations to our top 10:

  1. tourist
  2. maroonrk
  3. kotatsugame
  4. Tiramister
  5. antontrygubO_o
  6. tute7627
  7. nuip
  8. penguinman
  9. saketh, pwild
  10. neal

Congratulations to our first solvers:

You can access the editorial here (English version available on page 7)

The problems can be upsolved here

Thank you for participating and we hope to see you on the next TROC!

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

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

Prabowo and his owo children 0w0

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

As neither a tester nor a participant, I hope everyone enjoys the contest.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

Jokes aside, looking forward for this contest!

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

Wait, there's a TROC 16?

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

UwU

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

Friendly reminder that the contest will start in 3 hours :))

Good luck to all participants!

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

The Contest will start in 20 minutes. Good Luck and Have Fun!

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

After 35 minutes of the contest... I just want to say GG :v...

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

Can you move Constraints section right after Description/Input Specification in problem page?

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

How to solve D, didn't get from the editorials?

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

    Let the indices $$$j$$$ such that $$$A_i = j$$$ be called special indices.

    Let's iterate from the back (from $$$N$$$ to $$$1$$$).

    Let $$$i$$$ denote the current iterated index, if $$$i$$$ is a special index, then there would only be one way of placing an element in that index, the maximum value that hasn't been used, or the minimum value that hasn't been used by the previous iteration.

    For example:

    Say that indices $$$3$$$ and $$$5$$$ are special indices.

    When iterating on the index $$$5$$$, you can only place $$$5$$$ or $$$1$$$ depending $$$T_5$$$ (but it doesn't actually matter, since you still end up with one possibility anyway).

    When iterating on the index $$$4$$$, since placing any elements that hasn't been used doesn't violate any conditions, we can consider $$$4$$$ ways of placing an element.

    When iterating on the index $$$3$$$, you can only place the highest / lowest unused element, since not placing the highest / lowest unused element would lead to a violation of the conditions, i.e. $$$max(P_1, P_2, \dots, P_3)$$$ or $$$min(P_1, P_2, \dots, P_3)$$$ wouldn't be equal to $$$P_3$$$.

    And so on...

    Making the final answer: $$$4 \times 2 \times 1 = 8$$$.

    In short, when $$$i$$$ is a special index, there could only be one element that satisfy the conditions, and in contrast, there could be $$$i$$$ elements that could satisfy the conditions when $$$i$$$ is not a special index.