Code ends before it actually should, I'm using std::time()

September 23, 2022

I’m writing a code that tries to paint all dots in graph correctly by randomly giving colors (according to some simple algorithm) while I still have time left. Correctly means that no two dots with same color are adjacent. Also every dot must have color distinct from the initial.

I noticed that in a simple test it gives wrong answer when I set time limit <=3 sec, but it doesn’t work 3 seconds, it almost instantly throws "Impossible", here is part of the code (start, end and tl are global):

    std::string new_paint;
    bool success = false;
    while (!success && end - start < tl) {
        std::time(&end);
        new_paint = TryPaint(edges, paint, success, v);
    }
    if (success) {
        for (int i = 1; i < new_paint.size(); ++i) {
            std::cout << new_paint[i];
        }
    } else {
        std::cout << "Impossible";
    }

Test is:

It means "3 dots with 3 edges, initial color RGB, edges between 1 2, 1 3 and 2 3"

Also I noticed that when i try to cout end - start it gives 6 in this test. I can’t understand what is wrong can smn help?

Im using CLion, Cmake looks like this:

cmake_minimum_required(VERSION 3.21)
project(untitled1)

set(CMAKE_CXX_STANDARD 14)

add_executable(untitled1 main.cpp)

Here is full version of code:

#include <chrono>
#include <iostream>
#include <vector>
#include <set>
#include <random>
#include <algorithm>

time_t start, end;
const int tl = 20;

void check(std::vector<bool>& color, const std::string& paint, int n) {
    if (paint[n] == 'R') {
        color[0] = false;
    } else if (paint[n] == 'G') {
        color[1] = false;
    } else {
        color[2] = false;
    }
}

std::string available_color(std::vector<bool>& color) {
    std::string s;
    if (color[0]) {
        s += 'R';
    }
    if (color[1]) {
        s += 'G';
    }
    if (color[2]) {
        s += 'B';
    }
    return s;
}

std::string TryPaint(std::vector<std::set<int>>& edges, std::string paint, bool& success, int v) {
    std::vector<bool> was(v + 1);
    int count = 0;
    std::vector<int> deck;
    for (int i = 0; i < v; ++i) {
        deck.push_back(i + 1);
    }
    std::random_shuffle(deck.begin(), deck.end());

    while (count != v) {
        auto now = deck[count];
        std::vector<bool> color = {true, true, true};
        check(color, paint, now);
//        std::cout << now << '\n';

        for (const auto& i : edges[now]) {
            std::time(&end);
            if (end - start >= tl) {
                success = false;
                return "";
            }
            if (was[i]) {
                check(color, paint, i);
            }
        }

        std::string choice = available_color(color);
//        std::cout << choice << '\n';

        if (choice.empty()) {
            success = false;
            return "";
        } else {
            ++count;
            was[now] = true;
            char new_color = choice[0];
            paint[now] = new_color;
        }
    }
    success = true;
    return paint;
}

int main(){
    std::time(&start);
    std::time(&end);
    int v, e;
    std::cin >> v >> e;
    std::string paint;
    std::cin >> paint;
    paint = '#' + paint;
    std::vector<std::set<int>> edges(v + 1);
    for (int i = 0; i < e; ++i) {
        int a, b;
        std::cin >> a >> b;
        edges[a].insert(b);
        edges[b].insert(a);
    }
    std::string new_paint;
    bool success = false;
    while (!success && end - start < tl) {
        std::time(&end);
        new_paint = TryPaint(edges, paint, success, v);
//        std::cout << "-------------------------------------------------\n";
    }
    if (success) {
        for (int i = 1; i < new_paint.size(); ++i) {
            std::cout << new_paint[i];
        }
    } else {
        std::cout << "Impossible";
    }
    std::cout << '\n';
    return 0;
}

>Solution :

Use difftime() to calculate the number of seconds between two time_t variables. The time_t is opaque and can contain different values on different systems according to the doc.