×

BIPIN3 - editorial

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

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

10.0k266990
accept rate: 18%

19.8k350498541

 0 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. answered 11 Apr '16, 18:46 3●1●2 accept rate: 0%

include<studio.h>

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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