You are not logged in. Please login at www.codechef.com to post your questions!

×

BIPIN3 - editorial

PROBLEM LINK:

Practice
Contest

Author: Bipin Baburaj
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica

DIFFICULTY:

SIMPLE

PREREQUISITES:

Fast modular exponentiation

PROBLEM:

A rooted tree with N nodes is considered. We need to assign a color from 1 to K to each node of the tree in such a way that every pair of nodes (A,B), where A is the parent of B, has different colors.

QUICK EXPLANATION:

The answer is $K*(K-1)^{N-1}$. Note that the actual tree is not given. This is because there is the same answer for every tree with N nodes (and for the given K).

EXPLANATION:

We can choose any of the K colors for the root of the tree. Then we can choose any color except the root's color for any of the root's children. Then, for every child of a child of the root we can choose any color except that of its parent, and so on. Thus, for each of the other N-1 nodes we have K-1 choices for its color. The overall answer is $K*(K-1)^{N-1}$.

For subtasks 1 and 2 one can compute the answer in O(N) time. For subtask 3 one needs to compute $(K-1)^{N-1}$ (modulo $10^9+7$) using fast modular exponentiation, in O(log(N)) time.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 02 Apr '16, 02:48

mugurelionut's gravatar image

7★mugurelionut
10.0k266990
accept rate: 18%

edited 11 Apr '16, 18:31

admin's gravatar image

0★admin ♦♦
19.8k350498541


I have two solutions for the same problem. I applied the exponentiation by squaring method but got a TLE for the use of fmod instead of %. Can anyone explain me why the use of fmod gives a wrong answer but the use of % gets me an AC? My custom _fmod function reads something like ::

    uint64_t _fmod(uint64_t x, uint64_t y)
    {
    #pragma STDC FENV_ACCESS ON
        uint64_t result = std::remainder(std::fabs(x), (y = std::fabs(y)));
        if (std::signbit(result)) result += y;
        return std::copysign(result, x);
    }

My accepted solution uses the % operator but I was hoping to get around the _fmod() function which is nothing but a variant of C++ fmod method.

link

answered 11 Apr '16, 18:46

durwasa_jec's gravatar image

2★durwasa_jec
312
accept rate: 0%

include<studio.h>

link

answered 06 Feb, 19:17

pothuhemanth's gravatar image

0★pothuhemanth
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,678
×1,173
×122
×24
×8

question asked: 02 Apr '16, 02:48

question was seen: 2,360 times

last updated: 06 Feb, 19:17