2
\$\begingroup\$

I was solving a question on a coding website and this website has a limit for execution time of code. My code takes 1.01 sec but the limit is 1 sec. I am unable to find any changes in my code that can decrease the execution time. Here is the link for the question :- https://www.codechef.com/AUG21C/problems/CHFINVNT

Chef is trying to invent the light bulb that can run at room temperature without electricity. So he has \$N\$ gases numbered from \$0\$ to \$N−1\$ that he can use and he doesn't know which one of the \$N\$ gases will work but we do know it.

Now Chef has worked on multiple search algorithms to optimize search. For this project, he uses a modulo-based search algorithm that he invented himself. So first he chooses an integer K and selects all indices \$i\$ in increasing order such that \$i \bmod K = 0\$ and test the gases on such indices, then all indices \$i\$ in increasing order such that \$i \bmod K = 1\$, and test the gases on such indices, and so on.

Given \$N\$, the index of the gas \$p\$ that will work, and \$K\$, find after how much time will he be able to give Chefland a new invention assuming that testing 1 gas takes 1 day.

For example, consider \$N=5\$, \$p=2\$ and \$K=3\$.

  • On the 1st day, Chef tests gas numbered \$0\$ because \$0 \bmod 3 = 0\$.
  • On the 2nd day, Chef tests gas numbered \$3\$ because \$3 \bmod 3=0\$.
  • On the 3rd day, Chef tests gas numbered \$1\$ because \$1 \bmod 3=1\$.
  • On the 4th day, Chef tests gas numbered \$4\$ because \$4 \bmod 3=1\$.
  • On the 5th day, Chef tests gas numbered \$2\$ because \$2 \bmod 3=2\$.

So after 5 days, Chef will be able to give Chefland a new invention

How is my code slow (by .01 sec)?

#include <stdio.h>

int main(void) {
    int T;
    scanf("%d",&T);
    while(T--){
      int n,p,k;
      int j,remain,r=0,day=0;
      scanf("%d %d %d",&n,&p,&k);
       
       for(j=0;j<n;j++){
        remain = j%k;
          if(remain==r){
            day++;
            if(j==p) break;
          }
          if(j==n-1){
            j=0;
            r++;
          }
       }
        printf("%d\n",day);
    }
    return 0;
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Codechef likely stopped executing your code after the 1 second mark, meaning your code didn't actually take 1.01 seconds. You'll need to try a different algorithm. \$\endgroup\$
    – GeeTransit
    Aug 6 '21 at 18:19
  • \$\begingroup\$ You are right but I think my algo works well , it uses only one for statement and three necessary if(s) statements, can you provide a hint or something for another algo? \$\endgroup\$
    – Carbon
    Aug 6 '21 at 18:22
  • 1
    \$\begingroup\$ WIth your current algorithm, you loop through all numbers. With the bound of the questions, your code takes around about 10^5 * 10^9 operations. On average, a computer can do 10^9 operations a second. You'll still need to do 10^5 operations to loop through the input, but to bring down the 10^9 part, you'll need some math. \$\endgroup\$
    – GeeTransit
    Aug 6 '21 at 18:32
6
\$\begingroup\$

Throwing everything directly into main() makes it harder to test the program. Let's split into a unit-testable function and the challenge harness:

static int days(int n, int p, int k)
{
    int day = 0;
    int r = 0;
    for (int j = 0;  j < n;  ++j) {
        int remain = j % k;
        if (remain == r) {
            ++day;
            if (j == p) break;
        }
        if (j == n - 1) {
            j = 0;
            ++r;
        }
    }
    return day;
}
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int t;
    if (scanf("%d", &t) != 1) {
        return EXIT_FAILURE;
    }
    while (t--) {
        int n, p, k;
        if (scanf("%d %d %d", &n, &p, &k) != 3) {
            return EXIT_FAILURE;
        }
        printf("%d\n", days(n, p, k));
    }
}

Whilst editing here, I added the missing check that scanf() successfully converted the expected values.

Now we can add unit tests. Let's start with the example given in the question:

#ifdef TEST

#include <gtest/gtest.h>

TEST(days, question_example)
{
    EXPECT_EQ(days(5, 2, 3), 5);
}

#else

int main(void)
{
    ⋮
}

#endif

We should add more tests as and when we think of them.


Let's look at the algorithm. We're looping j over ever integer, testing each one for divisibility by k. That's an expensive way to loop over all multiples of k; it's much more efficient to increment j by k each time, and not need any division:

static int days(int n, int p, int k)
{
    int day = 0;
    int r = 0;
    for (int j = 0;  r < n;  j += k) {
        if (j >= n) {
            j = ++r;
        }
        ++day;
        if (j == p) break;
    }
    return day;
}

Or more clearly, iterating over the possible remainders:

static int days(int n, int p, int k)
{
    int day = 0;
    for (int r = 0;  r < n;  ++r) {
        for (int j = r;  j < n;  j += k) {
            ++day;
            if (j == p) { return day; };
        }
    }
    /* shouldn't happen */
    return day;
}

That algorithm is still slow, since we're still looping and counting each day individually. We don't need to do that, since we should be able to calculate how many days it will take to reach p.

Let's look at the example again, and lay out the numbers as we'll visit them:

0 → 3 ⤶
1 → 4 ⤶
2

Or perhaps a larger example, (18, p, 4):

0 →  4 →  8 → 12 → 16 ⤶
1 →  5 →  9 → 13 → 17 ⤶
2 →  6 → 10 → 14 ⤶
3 →  7 → 11 → 15

We know that we will have to do p%k full runs over the N elements. Each of those runs will contribute N/k or N/k + 1 days to the total, depending on N%k. The final, partial, run will contribute p/k days:

static int days(int n, int p, int k)
{
    int full_runs = p % k;
    int long_full_runs = n % k;
    if (long_full_runs > full_runs) {
        long_full_runs = full_runs;
    }

    return 1
        + full_runs * (n / k)
        + long_full_runs
        + p / k;
}

That satisfies all the tests, including the (18, p, 4) set I added:

EXPECT_EQ(days(18, 0, 4), 1);
EXPECT_EQ(days(18, 4, 4), 2);
EXPECT_EQ(days(18, 16, 4), 5);
EXPECT_EQ(days(18, 1, 4), 6);
EXPECT_EQ(days(18, 17, 4), 10);
EXPECT_EQ(days(18, 2, 4), 11);
EXPECT_EQ(days(18, 14, 4), 14);
EXPECT_EQ(days(18, 3, 4), 15);

And now there's no loop, so this runs in constant time, i.e. it scales as O(1) rather than O(nk) as before.

\$\endgroup\$
3
\$\begingroup\$

This algorithm is \$\mathcal{O}(nk)\$ but could be \$\mathcal{O}(n)\$.

It is \$\mathcal{O}(nk)\$ because you reset j k times with j bounded by n. This makes it very much like having two for loops. Consider something like

int day = 0;
for (int r = 0; r < k; r++) {
    for (int j = 0; j < n; j += k) {
        day++;

        if (j == p) {
            printf("%d\n", day);
            r = k - 1;
            break;
        }
    }
}

The - 1 may not be necessary if k is not the maximum positive value for int.

That would actually be \$\mathcal{O}(n)\$, because the outer loop runs k times and the inner loop is \$\mathcal{O}(n/k)\$. In this case, using two loops can be faster than your single loop.

It's also possible that the intent is to do this in constant time: \$\mathcal{O}(1)\$. You should be able to calculate day from the remainders and quotients. Something like

day = (p % k) * (n / k);

That may not be complicated enough. Consider if it matters if \$p\bmod k \gt n \bmod k\$ and perhaps the result of p / k. But I'm relatively sure that this is calculable in some way. I.e. that there is some formula that will give day in terms of n, p, and k, which you know. The following may provide insight

printf("%d %d %d %d\n", day, (p % k) * (n / k), (p / k), ((p % k) > (n % k)));

You would replace the original printf with that one and see what it gives. Try various formulas until you find one that works.

Another option would be to try to replace the inner loop with a formula. That would be \$\mathcal{O}(k)\$ time.

int day = 0;
for (int r = 0; r < k; r++) {
    if (r == p % k) {
        day += p / k;
        printf("%d\n", day);
        break;
    }

    day += n / k;
}

None of these are tested. They are just things that come to mind as possibilities. I am most confident about the first one returning the same results as your original algorithm. But all of them should be faster for large k and n.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.