I am being disconnected (as logout) several times. Is it happening for you too ? (Not just on my personal computer)

Hello Codeforces community!!

I'll be straight in this topic. I'm trying to solve the problem Nurikabe. But receiving TLE. If helps, the code.

I'm using a bruteforce solution, first of all, I am generating all fixed Polyominoes from size 1 to 9. So, now for each given grid, I do the following things:

• 1) Storing all interesting points (points with numbers on the grid) in a vector<pair<int, int> > p.
• 2) Now, I bruteforce with backtracking:
• 2.1) If(all interesting points already have a polyminoes assiated) check if the actual grid is valid (according to statement) with a DFS // O(n*m)
• 2.2) Te next step, I'll try to explain with a example:

supposing the bellow grid and a polyomino ###:

.....
..3..
.....

There are three possible ways to place this polyomino:

..... ..... .....
.###. ..### ###..
..... ..... .....

My algorithm follows the above example, for each polyomino[i] (with size equals to interesting point[i]), I try to place the polyomino fixing a cell.

• 2.3) I check if is valid to use this polimino. //O(polyomino size)
• 2.4) If is valid, add the polyomino on the grid //O(polyomino size)
• 2.5) Try the next interesting point
• 2.6) Remove the polymino from the grid. //O(polyomino size)

Does someone know some prunning to do in this backtracking to avoid TLE or is it a wrong approach ? Any help will be very apreciated, thank you.

Hello community. I'll show the following statement:

Given N segments [Li, Ri] and Q queries Xi. Each query will ask if the Xi is inside some segment.

0 ≤ Li, Ri ≤ 10⁹

Will at most 10⁵ segments and at most 10⁵ queries.

I have solved this problem sorting the segments, sorting the queries, and finally T(N+Q) processing. I am thinking now, if is it possible to be solved faster?.. But nothing comes to me.

Do you know something faster ?

Hello guys. I'm trying to solve the problem Circuits from spoj. After think a lot, I found a greedy solution to solve this problem, follow

'Supposing all components have no cycles yet'
1) Separate all components
2) Get the component with less vertices and the component with most vertices.
3) Merge this two componentes this way:
A = first component
B = second component
From A, get the two vertices (may be the same vertex) that have the greater distante.
From B, the same thing.
4) Create a link (connect the vertices from A and B) between this four vertices:
graph[A[0]].push_back(B[0]);
graph[B[0]].push_back(A[0]);
graph[A[1]].push_back(B[1]);
graph[B[1]].push_back(A[1]);
5) Find the formed cycle (and all vertices on the cycle)
6) For each node in the cycle:
If the node have all the neighbors in the cycle, I just remove it.
7) Generate again the componentes, and the process repeats until I find nodes without a cycle.

I guess this algorithm above work fine (at least I tested in several cases). But it is very complicated.

Does anyone agree with this solution or I can do something easier ? Sorry for the long text and my poor english.

I was trying to solve the following problem:Death Row

I spent the whole morning trying to solve it, but just wrong answer.. I just realized that the minimum time that he and his family still living is when Yama at every visit, kills M people and (N-M) >= 2, and when is remaining just N = 2 people, Yama need to visit more two times. I guess it is right, but I'm receiving wrong answer..

Can someone help me ? Thanks in advance.

Hello, I'm trying to understand the following formula: F(n) = F(n-1) + 2F(n-2).

The original problem is:

Given three vertex A,B,C and a number of moves L, the edges are:
A to B
A to C
B to A
B to C
C to A
and C to B.
What the number of ways to go from A and get back to A, using L moves ?

I'm trying to figure out, why the above formula works for this problem, can you help me ? Thank you. Thank you.

Hello, I'm trying to solve a problem from SPOJ involving combinatorics (counting), but I cannot find a final answer... http://www.spoj.com/problems/MARBLES/

I've found some things that I guess will be useful to solve this task: You have to use at least one ball in each color, so, N-K (I will call it "X") balls left.

I need to distribute this X balls in the K colors, so I began to think: "I can use from 0 up to X balls in each color".

I'm trying hard to find out the answer, maybe am I thinking in a wrong way ?! Can you give to me some tips how to solve ?

Hello friends, I am trying to solve this task from topcoder: Link to PowerSupply

I have read the editorial but I cannot undertand how to choice the best parallel line to one of the two diagonals. The vertical and horizontal lines I know how to get the answer, but how can I find the 'best parallel line' to one of the diagonals ?

I'm very confused, can you explain with some details please ?

Ps: I know how to find the distance from a point to a line.

Thanks.

The following formula: F(n) = F(n-2) + F(n-1) + 1 give to me how many calls I need to generate the N-th term of Fibonacci. But I don't know how to handle the constant value + 1 to find the recurrence matrix.

I'm bit lost, and I found the following (but wrong) recurrence:

F(0) = 1, F(1) = 1

[F(0), F(1)] * [[0,2], [1, 1]]^(n-1) = [F(n), F(n+1)]

Can someone help me to understand ? Thank you.

Hello everyone.

I have a graph in the shape of a tree, in which I need to know the following:

• 1) L = Lowest common ancestor between vertex A and B.
• 2) The edge of lower cost between A and L, and lower cost edge between B and L.

I can not think of an efficient way to make the item 2), anybody could give me a light?

My naive ideia is to every query check all vertex between A ~ L and B ~ L, but it is slow.

If you need code, I can show my code here. Thank you.

Hello, i'm traying a long time to get path of a recursion using DP for the Equipment replacement problem.

N = years to produce M = maximum years machine life P = cost of a new machine V = price to sell the machine on year 'i' CM = price to keep machine on year 'i'

int func(int machine_age, int years_working){
    if(years_working == N){
        return 0;
    }else{
        if(dp[machine_age][years_working] != -1){
            return dp[machine_age][years_working];
        }else{
            if(machine_age > M){
                dp[machine_age][years_working] = P — V[machine_age] + CM[0] + func(1, years_working+1);
                path[years_working] = 1;
            }else{
                int try_keep = CM[machine_age] + func(machine_age+1, years_working+1);
                int try_replace = P — V[machine_age] + CM[0] + func(1, years_working+1);
                if(try_replace <= try_keep){
                    path[years_working] = 1;
                }else{
                    path[years_working] = 0;
                }
                dp[machine_age][years_working] = min(try_keep, try_replace);
            }
        }
        return dp[machine_age][years_working];
    }
}

I'm using a strategy based on: if(keep){ save with 0} else{save with 1}

Can someone help-me to get the path of better decisions to minimize costs of production ?

Thanks a lot.

Hi, more one time I need your help. Look the first example, I don't know how the answer is 656100, My best result is 682600 calculation using paper and pen.

I wanna help to UNDERSTAND the problem, my guess appear be wrong.

Paul works for a large company called Abacus Computers and Maintenance (ACM). Your job is to provide computer maintenance customer of the ACM, located in various parts of the country. For this reason, Paul is usually a good number of hours per week in airplanes. Obviously, Paul always carries his laptop, so that even when you're traveling by plane can perform many tasks related to their work.

Because laptop batteries do not usually last long, Paul has been studying ways to increase the lifetime of the battery during flight. He found that modern processors can operate at different frequency levels, offering a compromise between performance and power consumption. The initial idea was Paul just set your laptop on the lower frequency. However, he noted that it was not very useful, since the tasks performed very slowly on the laptop, and there was no time to perform all the tasks, so that the remaining battery power would be useless.

Paul noted, however, that the influence of frequency on the performance level varies from application to application, depending on whether they are limited by memory, CPU or I / O. Additionally, as modern processors allow the frequency level is changed by software, Paul plans to use this mechanism to increase the usage time of battery your laptop, so still maintaining a reasonable performance. To take into account both the energy and performance, Paul decided to use a well-known metric called Power × Time (EDP -> Energy × Delay Product).

Paul has a list of programs that should be executed sequentially, and all information on the time and energy needed to run each program at each frequency level, as well as information on how much energy is expended to change the processor frequency. However, to test his new idea, Paul still has a problem: like most system administrators, he does not like to program. He is asking for your help, since you're a great friend and an expert in algorithms and programming, to determine the level of frequency in which each of its programs should be implemented in order to minimize the total EDP.

Input: The entry contains a number of test cases. The first line of a test case contains four integers F, P, E, and A, respectively identifying the number of frequency levels supported by the processor of the laptop of Paul (1 = F = 20), the number of programs to be executed sequentially (1 = P = 5000), the necessary energy in Joules, to switch between any two levels of frequency (1 = E = 100) and time (in ms) to switch between any two levels of frequency (1 = A = 100). The frequency levels are identified by integers from 1 to F, and programs are identified by integers from 1 to P.

The F x P next lines describles the programs, with F lines for each program (the first F lines correspond to the first program, next F lines correspond to the program 2, and so on). The Fi line correspond to the program p with two numbers Ep,f e Ap,f, representing respectively the amount of energy (in Joules) and time (in ms) to run the program p on the frequency level f (1 = Ep,f = 1000 e 1 = Ap,f = 1000). At the beginning of each test case the processor is at 1 of frequency. The end of the input is indicated by F = P = E = A = 0.

Output: For each test case entry, its program to produce a line in the output containing the minimum EDP to sequentially execute the series of programs from 1 to P (in the order they appear on input).

Sample input:
2 3 10 10
50 120
100 90
500 600
600 500
400 1000
500 700
3 3 2 5
7 10
8 5
15 4
12 4
11 5
12 4
7 10
8 5
15 4
0 0 0 0

Sample output:
656100
145

Look my code to test the first example using the frequency 2 in both programs (max frequency):

ll f, p, e, a, tmpE, tmpJ;

struct Task{
    ll energy, time;

    Task(ll _energy, ll _time){
        energy = _energy;
        time = _time;
    }
};

ll f, p, e, a, tmpE, tmpJ;

int main(void) {
    freopen("in.in", "r", stdin);
    ios::sync_with_stdio(0);
    while((cin >> f >> p >> e >> a) && (f + p + e + a)){
        vector<Task> tasks[p + 1];
        for(int i = 0; i < p; i++){
            for(int j = 0; j < f; j++){
                cin >> tmpE >> tmpJ;
                tasks[i].push_back(Task(tmpE, tmpJ));
            }
        }
        ll ret = 0;
        for(int i = 0; i < p; i++){
            for(int j = 0; j < f; j++){
                Task tmp = tasks[i][j];
                ret += (tmp.time * (tmp.energy / f));
            }
        }
        cout << ret << "\n";
        break;
    }
    return 0;
}

Thanks so much.

I'm reading about bipartite graphs, but I can't implement It....
I now:
G[V,E]
For each V[white], their friends must to be V[black], and Each friend V[black] must to have friends V[white].

Can you help-me sending some articles about this ?

P.S.: The article would have to be in english please.

I'm reading about it to solve: http://br.spoj.pl/problems/MESA/

Translated to english by google translate:
http://translate.google.com/translate?hl=pt-BR&sl=pt&tl=en&u=http%3A%2F%2Fbr.spoj.pl%2Fproblems%2FMESA%2F

Hello everyone.

Problem: Researchers from the Department of Operations Research at the University of British Columbia were contracted to a strange tarefa.Vários African countries decided to officially join and use the means of transport which became known worldwide in the Tarzan films: the vine. There are millions of vines in Africa and it is surprising speed and efficiency with which a person can move around in the jungle using this means of transportation. Only a small problema.Os came vines are dominated by three major tribes: the makelelês the malouhdás and abedis. Tribes demand to be paid by vines used in the transportation system. As they do not know the meaning of words like cartel, each one made ​​his price, and diverged considerably. While the 1235 makelelês require bongos by creeper used, require malouhdás abedis 8977 and 10 923 (Jane is still alive, and helped broker the negotiations for this tribe). The researchers were hired to pick the vines that make up the first system cipoviário the world. The contractors have built millions of "points liana" the African jungle and want the vines are chosen such that it is possible to go from any point to any other contractors using the vines (you may have to change sometimes vine, as did Tarzan). You should say what the cost of a system that meets these requirements and be as cheap as possible. You can assume that there are enough vines in the jungle so that whenever there is a system that meets the requirements cipoviário.

Input: The input consists of several instances. The first line of each instance contains two integers n (1 <= n <= 1000) in (1 <= m <= 2000000), where n is the number of "points liana" is in the number of vines. Each of the following m lines contains three integers u, vec indicating that there is a vine that will point to the point u and v with cost c, where 1 <= u, v <= n and c = 1235 or 8977 or 10923.

Output: For each instance, you have to print some identificator instance k, where k is the number of the actual instance. Next line print the cost of the system who reach the descripted requisits.

Input:
3 3
1 2 10923
1 3 1235
2 3 1235
3 2
1 2 1235
2 3 10923

Output:
Instance 1
2470

Instance 2
12158

I need to solve using a Minimum Spanning Tree, which connect all points with minimum cost.

Code below:

#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <vector>

#define INF 9999999999
#define ll long long int

using namespace std;

struct UnionFind {
    ll N, *id, *size;
    UnionFind(ll n) {
        this->N = n;
        id = new ll[n];
        size = new ll[n];
        for(ll i = 0; i < n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    ll root(ll i) {
        while(i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }

    bool find(ll p, ll q) {
        return (root(p) == root(q));
    }

    void unite(ll p, ll q) {
        ll i = root(p);
        ll j = root(q);
        if(i != j) {
            if(size[i] < size[j]) {
                id[i] = j;
                size[j] += size[i];
            } else {
                id[j] = i;
                size[i] += size[j];
            }
        }
    }
};

struct edge {
    ll x, y, weight;

    edge(ll _x, ll _y, ll _weight) {
        x = _x;
        y = _y;
        weight = _weight;
    }

    edge(){};
};

ll n, m, xx, yy, weight, instance = 1;
edge low[2000001], mid[2000001], high[2000001];

int main(void) {
    freopen("in.in.c", "r", stdin);
    while(~scanf("%d%d", &n, &m)) {
        int idxLow = 0, idxMid = 0, idxHigh = 0;
        ll dist = 0;
        printf("Instancia %d\n", instance++);
        UnionFind uf(n + 1);
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &xx, &yy, &weight);
            if(weight == 1235) {
                low[idxLow++] = edge(xx, yy, weight);
            } else if(weight == 8977) {
                mid[idxMid++] = edge(xx, yy, weight);
            } else {
                high[idxHigh++] = edge(xx, yy, weight);
            }
        }
        for(int i = 0; i < idxLow; i++) {
            edge tmp = low[i];
            int x = tmp.x;
            int y = tmp.y;
            ll weigh = tmp.weight;
            if(!uf.find(x, y)) {
                uf.unite(x, y);
                dist += weigh;
            }
        }
        for(int i = 0; i < idxMid; i++) {
            edge tmp = mid[i];
            int x = tmp.x;
            int y = tmp.y;
            ll weigh = tmp.weight;
            if(!uf.find(x, y)) {
                uf.unite(x, y);
                dist += weigh;
            }
        }
        for(int i = 0; i < idxHigh; i++) {
            edge tmp = high[i];
            int x = tmp.x;
            int y = tmp.y;
            ll weigh = tmp.weight;
            if(!uf.find(x, y)) {
                uf.unite(x, y);
                dist += weigh;
            }
        }
        printf("%d\n\n", dist);
    }
    return 0;
}

Accepted.
1) Create three arrays, one for the loweest values, one for mid values and otther for high values. (it simulate the sort)
2) Put each "edge" in your respective array.
3) Use Krukson algorithm to solve. (Minimum Spanning Tree)