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:
3 3
RGB
1 2
2 3
1 3
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;
}
