Utkarsh.25dec's blog

Invitation to CodeChef October Starters 62 (Rated till 6-stars) — 26th October

By Utkarsh.25dec, 2 years ago, In English

We invite you to participate in CodeChef’s Starters 62, this Wednesday, 26th October, rated till 6-stars participants (ie. for users with rating < 2500).

Time: 8 PM — 11:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

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

Comments Comments (6)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note:there is an interactive problem in this round.

If you are unfamiliar with interaction problems,you can read the guide for interactive problems here.

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

Problem PYTHAGORAS

largest odd divisor of N does not exceed 10^5

I believe that this condition is not satisfied in some tests. Can anybody from admins check this?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It is satisfied. We have cross-checked at that time and also answered your query.

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

      Thanks again for that and for the quick response.

      → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can Any Body Explain the logic of Pythagoras Pair

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

    Sum of Squares theorem states that a number $$$N$$$ can always be represented as the sum of two squares as long as there is no prime $$$p$$$ in $$$N$$$'s factorization such that $$$p \equiv 3$$$ $$$(mod$$$ $$$4)$$$ and its exponent is odd.

    Because of the constraint on $$$N$$$, notice that it means that $$$N$$$ always takes the form of $$$x*y$$$, where $$$x$$$ is a power of $$$2$$$ and $$$y$$$ is less than or equal to $$$10^5$$$. Due to the Sum of Squares Theorem mentioned earlier, if $$$y$$$ is possible, then $$$x*y$$$ is possible, and if $$$y$$$ is not possible, then $$$x*y$$$ is also impossible. So it would be nice if we could find the answer for $$$y$$$, and translate that into an answer for $$$x*y$$$. Turns out that we can, since notice that every other power of 2 is a square. If we ensure that $$$x$$$ is a power of $$$4$$$(and thus, a perfect square), $$$y \leq 2*10^5$$$ will hold true.

    As such, we can precalculate the answer for everything from $$$1...2*10^5$$$, and when answering a query of $$$N$$$, we split $$$N$$$ into $$$x*y$$$. Our answer should then be $$$\sqrt{x}*(y_1,y_2)$$$, where $$$y_1$$$ and $$$y_2$$$ are the valid pair(if it exists) for $$$y$$$.

    → Reply