Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

xenon_shivam's blog

By xenon_shivam, history, 4 weeks ago, In English,

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] — Coders@jgec.ac.in

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        You use global adjacency list and don't clear it before each testcase.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh yes. A stupid mistake. Thanks

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

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +26 Vote: I do not like it

        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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the question Odd Topic ? Any hints ?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    Keep a frequency array. Update the array by frequency of array elements for l1 to r1, similarly for l2 to r2. Now frequency array is ready. Loop over it find how many are having odd frequency.

    Solution

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

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