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

Автор xenon_shivam, история, 5 лет назад, По-английски

Hello Codeforces community,
The time has finally come to showcase your potential and wit. Coders club of JGEC brings you AARAMBH 2020 on 23rd of January 2020 to make you think out of the box.

I would like to invite you to participate in AARAMBH 2020 . It’s the fourth version of this short contest, that runs for 2:30 hours! . It is the annual coding contest of Jalpaiguri Government Engineering College (JGEC) which is organized essentially for the starters so that they get a real taste of competitive programming in the early days of their college.

It will basically be a Division-3 type contest consist of 7 questions of various difficulties. The contest is based on ACM-ICPC style and we have reduced the time penalty to 10 minutes instead of the standard 20 minutes.

Contest Details:

The contest starts on 23 January at 19:30 IST .

Contest Link : AARAMBH 2020

Prizes : There are Laddus and Cash prizes for Global top performers and JGEC top performers. Please check the contest page for details.

Problem setters : — imranasuman, mukul166 and myself.
Testersubash23, animesh_194.

Also visit — Invitation

For any query [mail at] — [email protected]

Get your gears up and compete for glory in the decade’s first coding extravaganza with awesome prizes waiting for you.

Hope to see you participating!!
Good luck and wish you all Happy Coding : )

Editorials
XYBACT
TWKNGS
CRICBZ
STRTLN
XORSGT

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

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

Auto comment: topic has been updated by xenon_shivam (previous revision, new revision, compare).

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

Auto comment: topic has been updated by xenon_shivam (previous revision, new revision, compare).

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

Auto comment: topic has been updated by xenon_shivam (previous revision, new revision, compare).

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

How to solve the second last problem Two Kings and Their Estate?

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

    We will post the editorials with all the details on the discuss forum of codechef.

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

    Check for each node whether it can be used as the starting node.
    To check for a node $$$u$$$ whether it is a winning node, consider its neighbors whose values are strictly less than its value. Recursively check for such neighbors $$$v$$$, if any $$$v$$$ is a losing node, then $$$u$$$ is a winning node. Otherwise $$$u$$$ is a losing node.

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

      That's exactly what I did. Can you catch the bug here

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

      Proof? Why are you checking only nodes with value strictly less?

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

        Let's consider you move from $$$u$$$ to $$$v$$$ and $$$val_u \le val_v$$$. The opponent can reverse your move by moving back from $$$v$$$ to $$$u$$$. If you keep repeating such moves, you lose. At some point, you'll need to move to some node with lower value to have a chance at winning.
        So, winning move may only exist when you move from a higher value node to a lower value node, and we need to check only for such nodes.

        This solution works in $$$O(N)$$$, though the constraints may allow $$$O(N^2)$$$ to pass. Maybe the expected solution is different.

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

How to solve the question Odd Topic ? Any hints ?

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

    Try to keep arrays of parity on prefix for each integer between 0 and MaxA = 4000, Then optimise it with bitsets. Complexity is O((n + m + q) * MaxA /32).