FreeJinG's blog

By FreeJinG, history, 4 years ago, In English

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!

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

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Prabowo and his owo children 0w0

»
4 years ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

Jokes aside, looking forward for this contest!

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Wait, there's a TROC 16?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Wait, there's a TROC 15?

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

UwU

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

Good luck to all participants!

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

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

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 5   Vote: I like it +8 Vote: I do not like it

    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.