How to reduce time limit on this?

[Ey80oG1T]

I have this code:

#include <iostream>
using namespace std;

int main()
{
  int minutes;
  cin >> minutes;

  int start = 1200;
  int digits = 3;

  int counter = 0;
  int increment = 0;
  bool variate = false; // switches it up between AM and PM

  while (increment < minutes)
  {
    if (digits == 3)
    {
      if (((start - 1200) % 10) - ((start - 1200) / 10) == (((start - 1200) / 10) - 2) == 1)
        counter += 1;
    }
    else if (digits == 2)
    {
      if (((start / 100) - (start % 100) / 10) == ((start % 100) / 10) - (start % 10))
        counter += 1;
    }

    start += 1;

    if (start == 1260 && variate == false)
    {
      start = 100;
      digits -= 1;
      variate = true;
    }
    if (start == 1260 && variate == true)
    {
      start = 1200;
      digits += 1;
      variate = false;
    }

    increment += 1;
  }

  if (counter == 2)
  {
    counter -= 1;
  }
  cout << counter;
}

It basically checks weather or not a certain time is an arithmetic sequence. So for example, 12:34 is an arithmetic sequence since all the numbers go up by one. 6:42 is another one, since all the numbers go down by 2.

But whenever I run it, it takes too long. Any suggestions on how to reduce the time limit?

[Duthomhas]

You are doing a whole lot of unnecessary processing, such as checking for AM and PM, etc.

Digit characters have consecutive, increasing values. Hence, '0' + 1 is '1', '1' + 1 is '2', etc. This makes it very easy to simply walk through your string. Ignore anything that isn’t a digit and if you find a difference between two successive digits that is not the same as the difference between the first two digits, then you have a non-arithmetic sequence.

Unless the problem explicitly requires it, you don’t even have to bother checking if the string is a valid time.

Good luck!

[ne555]

> But whenever I run it, it takes too long
¿what input? ¿how big is `minutes'?
that loop shouldn't be noticeable.


¿what are you doing in line 20?

[againtry]

Well, all I can say is it runs faster than my version of this program. Lines 41 and 26 are master strokes that I hadn't foreseen in my solution and substantially cut processing time :)

[jonnin]

curious..
is 12:13 (12 +1 ) a sequence?
is 12:48 (2^n) a sequence?
is military time allowed?

as far as taking too long, stop using brute force... decide what is allowed to be a sequence under your rules, and then generate the valid terms for each possible sequence. eg if +1 for each number is the sequence, just generate 01:23 02:34 03:45 .... you dont need to iterate 100 times to find that 0124 0125 0126... are no good! then do +2, +3 ... and -1, -2, -3... and so on. You can thread out each one, doing 4-8 or so at a time in parallel on a half decent machine.

[lastchance]

https://wcipeg.com/problem/ccc17j4

[Duthomhas]

@jonnin
OP explained it well with the original post... And generating every possible solution will definitely exceed the time limit...

[jonnin]

All I see in the OP is flat + and flat - which there are, 10, 12? possible sequences? That shouldn't take long at all. If its more than this, agreed, its too many and takes too long.
if you are only checking 1 time, generating them isnt any good... but most of these problems give you like 100k in a file, so if you pregen them all and check back, its often faster than one at a time. ?? It depends on whether this is a competition, and when people start saying takes too long, that is where my mind goes...?

[Duthomhas]

Good thoughts...

[dutch]

It's easy to enumerate the possibilities.
There's only 31 of them from 12:00 to 11:59.

#include <iostream>

// Up to (but not including) this value of minutes there are 'i' arithmetic
// sequences, where 'i' is the index at that point in the array.
// The newly-added sequence is shown in the comment.
// E.g., up to (but not including) 201 minutes there are 11 sequences.
// The 'UpTo' minutes are just the minute-counts of the next sequence,
// e.g., 201 comes from 3:21, i.e., 3 * 60 + 21.
const int UpTo[] {
     34, // none
     71, // 12:34
     83, //  1:11
     95, //  1:23
    107, //  1:35
    119, //  1:47
    130, //  1:59
    142, //  2:10
    154, //  2:22
    166, //  2:34
    178, //  2:46
    201, //  2:58
    213, //  3:21
    225, //  3:33
    237, //  3:45
    260, //  3:57
    272, //  4:20
    284, //  4:32
    296, //  4:44
    331, //  4:56
    343, //  5:31
    355, //  5:43
    390, //  5:55
    402, //  6:30
    414, //  6:42
    461, //  6:54
    473, //  7:41
    520, //  7:53
    532, //  8:40
    591, //  8:52
    671, //  9:51
    720  // 11:11
};

const int Size = sizeof UpTo / sizeof *UpTo;

// For every WrapAround minutes, there are Size - 1 sequences.
const int WrapAround = 60 * 12;

int main() {
    int minutes{0};
    std::cin >> minutes;
    int n = minutes / WrapAround * (Size - 1);
    int remainder = minutes % WrapAround;
    for (int i = 0; i < Size; ++i)
        if (remainder < UpTo[i]) {
            n += i;
            break;
        }
    std::cout << n << '\n';
}

[jonnin]

exactly.... that is where I was going, except I marked all the times directly instead of your slick conversion to a number, eg bool[1260] (every time to 12:59) set false then true out the ones the loop finds, then look up after the one time up front work. But again, its assuming you have a jillion of them to do, not just one..

[dutch]

assuming you have a jillion of them to do, not just one

Mine solves the problem that lastchance linked to, where the input is a single number (up to a billion) and you need to spit out the number of arithmetic sequences that occur in that many minutes, starting at 12:00.