### attempt's blog

By attempt, history, 4 months ago, ,

Note: I couldn't find exact terminology for this question. It is something like "Russian Peasant multiplication" for calculating exponent.

There's a well-known way of calculating $p^k$ as follow:

template<typename T> T pow(T p, int k) {
T t = 1;
while (k > 0) {
if (k % 2 == 1) t = t * p;
p = p * p;
k /= 2;
}
return t;
}


We can reduce one multiplication ($1 * p$) from above implementation with a variable named first_mul:

template<typename T> T pow(T p, int k) {
T t;
bool first_mul = false;
while (k > 0) {
if (k % 2 == 1) {
if (!first_mul) t = p, first_mul = true;
else t = t * p;
}
p = p * p;
k /= 2;
}
return t;
}


I found that when operator $*$ is very heavy, like matrix or polynomial multiplication, this trick reduces runtime a lot.

1. Is there a simple algorithm that is better than above algorithm for $k \leq 10^9, k \leq 10^{18}$, $k \leq 10^{100}$?
2. Is there any way to find the optimal number of multiplications in calculating $p^k$?

• +13

By attempt, history, 11 months ago, ,

There are $N$ questions, each of them has $k$ options. For each question, only one option is correct. Giving a black box that returns the number of correct answers of a submission. You try to submit until getting $N$ correct answers (There is a strategy having at most $1 + (k-1) \times N$ submissions).

I have 3 questions:

1. What's the official name for this kind of problem? I couldn't find any paper mentioning the problem.

2. What's the best strategy to get all $N$ correct answers? How many submissions required in the worst case?

3. We can submit at most $L$ submissions, what's the highest expected number of correct answers can we achieve?

• +66

By attempt, 7 years ago, ,

Hi all, I'm learning a very useful data struct int C++: set. I know set is a red-black tree so could we join two set into a new set with complexity O(log (number of elements)) in two set? And if we couldn't, what is the best algorithm to join two sets in C++? Thanks for helping.

• +5

By attempt, 7 years ago, ,

Hi all, I just see some solutions of round #200 div 1 D . Seem that all solutions use "range query" data struct. Some use Segment tree like con_nha_ngheo's solution . But some others use like KADR's solution. This tree i saw in codeforces and topcoder . I don't know what it is and how it work. Could anyone help me explain it or show me some notes about it?

• 0

By attempt, 7 years ago, ,

Hi everyone, I'm newbie to informatic and Codeforces. I have just finished my C++ class and now I am learning about algorithm. My teacher told that I should practice, practice and practice problems on some online judge webs but I feel tired. I'm just learning informatic 2 months and have no idea about algorithm. I always want to be a good algorithm programmer but I couldn't choose a effective method to learning it. Can anyone help me some way, learning algorithm before practice or practice then find algorithm compatible or another method? I'll very greatful for the help.