ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1769. Old Ural Legend

TLE on test #6 (C++) how to improve algorithm?
Posted by Ernestas 25 Sep 2011 21:59
Can't get past test #6 (Time limit exceeded) and I have no idea how could I improve/change the algorithm, looking for suggestions ;P. Thanks. Here's the code (with comments ^^):

#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

int powering(int n){
    int r = 1;
    for (int i = 0; i<n; i++){ r = r*10;}
    return r;

int main(int argc, char *argv[])
    std::string inputNumber;
    std::cin >> inputNumber;
    int length = inputNumber.length();
    char digits[100001];
    int num[100001];

    for (int i=0; i<length; i++){ //reading input
            digits[i] = inputNumber[i]; num[i] = digits[i] - '0';}

    for (int i=0; i<length; i++) // starting cycle for all n
            int q = powering(i);
            int n = q;          // n = 10^i
            bool unique;
            for(int m = 0; m<(q*10); m++){ // running through every number in 10^i to 10^(i+1)-1

                unique = true;
                for(int j = 0; j<(length-i); j++) //with a given number, checking if it's in the string;
                        int temp = n;
                        for(int x = j+i; x>=j; x--){ // checking if the number is unique in given position // x = current digit, i = number of digits (zero based)
                                temp = temp - num[x];
                                if(temp == 0){unique = false; break;}
                                if(temp % 10 != 0){break;}else{temp = (int)(temp/10);}
                        if(unique == false){break;} // if given number is not unique, breaks the cycle
                if(unique == true){std::cout << n << endl; return 1; } // checks if the number checked was unique (add pause here if you want to test)
                if(n<((q*10)-1)){n++;}else{break;} // checks if 10^(i+1)-1 is reached, if not, then n++;
    return EXIT_SUCCESS;

Edited by author 25.09.2011 22:01

Edited by author 25.09.2011 22:01

Edited by author 25.09.2011 22:01