attempt's blog

By attempt, history, 4 months ago, In English,

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.

So I want to ask:
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$$$?

Read more »

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

By attempt, history, 11 months ago, In English,

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?

Read more »

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

By attempt, 7 years ago, In English,

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.

Read more »

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

By attempt, 7 years ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By attempt, 7 years ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it