I_love_ProParThinkNot's blog

Invitation to NSU Cybernauts National Programming Contest 2019 (Replay)
By I_love_ProParThinkNot, 4 years ago, In English

Hello, Codeforces community.

It is my pleasure to invite you all to the replay contest of NSU Cybernauts National Programming Contest 2019,which was organized based on ACM ICPC rules and standard.

The contest will begin at 09:00 UTC on 14 November, 2019 and will run for 5 hours. There will be 12 problems of varying difficulty.

The contest platform is toph.co, you can register for the contest here.

The problems of the contest were authored and reviewed by AnikaTahsin, BishalG, BumbleBee, CLown1331, Evade_RAbid, fsshakkhor, ishtupeed, I_love_ProParThinkNot, I_See_You, jAckAL_1586, J-C, Joty, Knight_of_Thirteen, lnzva, mainstring, olee12, tahmedge and TarifEzaz.

We look forward to your participation and hope that you enjoy the problemset, best of luck in the contest.

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

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve this one ? https://toph.co/p/palindrome-query-i

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

    Segment tree and hashing.

    Imagine, the hash value $$$H$$$ of a string "PQRS" = $$$P*BASE^3 + Q*BASE^2 + R*BASE^1 + S*BASE^0$$$.

    Suppose, in a segment tree node, the left child contains a hash value $$$H_L$$$ representing the the string "PQ" and right child contains $$$H_R$$$ representing the string "RS".

    So, $$$H_L = P*BASE^1 + Q*BASE^0$$$ and $$$H_R = R*BASE^1 + S*BASE^0$$$.

    Suppose, in a segment tree node, the left child contains a hash value $$$H_L$$$ representing the the string "PQ" and right child contains $$$H_R$$$ representing the string "RS".

    So, $$$H_L = P*BASE^1 + Q*BASE^0$$$ and $$$H_R = R*BASE^1 + S*BASE^0$$$.

    To create the hash value $$$H_N$$$ of current node, we basically multiply $$$H_L$$$ by $$$BASE^2$$$ and and add it with $$$H_R$$$.

    So, we obtain $$$H_N = (P*BASE^1 + Q*BASE^0)*BASE^2 + R*BASE^1 + S*BASE^0$$$ $$$= P*BASE^3 + Q*BASE^2 + R*BASE^1 + S*BASE^0$$$ which represents the string "PQRS".

    Now what if the second character 'R' is removed from the string? Then, we need to keep another information in segment tree, the number of characters in the range of a node, let's denote it as $$$F_N$$$. We update the segment tree in the following way for removing 'Q'.

    • Go down to the leaf node representing 'R'
    • Make its hash value 0 and $$$F_N = 0$$$
    • While returning upwards in segment tree, for each node, calculate $$$F_N = F_L + F_R$$$.
    • To calculate the hash value, do $$$H_N = H_L*BASE^{F_R} + H_R$$$.

    So, in the node that used to represent the string "PQRS", after you remove "R", it will represent "PQR". Its left child will still represent "PQ" and have the hash value $$$H_L = P*BASE^1 + Q*BASE^0$$$. Its right child will contain "S" and have the hash value $$$H_R = S*BASE^0$$$. To obtain the hash value of this node representing "PQR", you calculate $$$H_N = H_L*BASE^{F_R} + H_R$$$ $$$= (P*BASE^1 + Q*BASE^0)*BASE^1 + S*BASE^0$$$ $$$= P*BASE^2 + Q*BASE^1 + S*BASE^0$$$ which represents the string "PQR".

    If you consider this the forward hash, you can calculate the backward hash in a similar manner but opposite to this and compare the forward hash and backward hash to find if a substring is palindromic.

    This is the basic gist, I will leave the rest of the details for your brainstorming.

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

How to solve Problem A? I guess we can't merge grundy values of two independent games given that the game we are playing follows the rules of misere nim.

→ Reply