I don't know solution

Вобщем безнадега какая-то

Edited by author 25.04.2007 01:26

How it can be solved with disjoint sets? Anybody help me please.
This is my mail: quvondiq.otajonov.tuit@gmail.com.
I'll wait for answer! Thanks for advance!!!

Let a[1], ... , a[n] be the sequence written by the friend and pref[i] be the xor of the prefix a[1...i]. Then a question (l, r, t) (which means the parity of the number of ones on the segment from l to r is t) can be represented as (pref[r] xor pref[l - 1] = t). Let's build a graph with two vertices for each prefix (thus, there will be 2 * (n + 1) vertices). Using compression, we actually need only at most 2 * m vertices (where m is the number of questions). Let the vertices corresponding to the prefix i be f0(i) and f1(i). Now, let's add all edges f0(i) ~ f1(i). For a question (pref[r] xor pref[l - 1] = t) if t = 1, we add two edges f0(l - 1) ~ f0(r) and f1(l - 1) ~ f1(r), else if t = 0, we add edges f0(l - 1) ~ f1(r) and f1(l - 1) ~ f0(r). To check whether a sequence of questions from 1 to x is achievable we just need to check whether our current graph is bipartite. This can be done by simply doing dfs after each question.

Is there any way I can see the output of my program? The message "Runtime error" is very uninformative, besides, on my computer, my program performs a variety of tests without any errors.

//main logic

#include <stdio.h>
#include <map>
#include <iostream>
using namespace std;

map<int, bool>  exist;
map<int, bool>  odd;
map<int, int>  prev;

bool add(int a, int b,  bool c){//b>=a;
    if (!exist[b]){
      exist[b] = true;
      odd[b] = c;
      prev[b] = a;
      return true;
    };
    int  i = prev[b];
    if(i==a) return (odd[b]==c);
    if(i<a) return add(i,a-1, (c!=odd[b]));
    return add(a,i-1, (c!=odd[b]));
};

Извините, что по-русски, надеюсь, администраторы знают этот язык.

В условии сказано, что длина последовательности задается в первой строке каждого теста.
В примерах на форуме длина общая для всех, в каждом тесте задается только количество вопросов.
Моя AC-программа действует по форуму: читает длину один раз, а потом только количество вопросов для каждого теста.

Хорошо бы привести текст задачи в соответствие с реальностью.
Совсем хорошо было бы дать в примере два теста, чтобы сделать структуру входных данных действительно ясной.

100000000
10
1 5 even
6 10 even
11 18 even
19 25 even
1 8 even
16 25 even
16 40 even
9 40 odd
1000 5000 odd
1000 6000 odd
-1

answer: 7

10
6
1 2 even
1 1 even
3 4 odd
5 6 even
1 6 even
7 10 odd

i think the answer of this data should be 1,but my program answer is 4 but it return an accepted!

Online tests surely contain several tests in one file, so:

1. Be sure clean your dictionaries before every test.
2. Be sure read ALL lines of current test, even you got correct answer before all input was used.

This two issues were the reason of my WA1. After fixing them I got "Accepted".

Use the following test to validate mentioned above points:

100
5
5 6 odd
7 8 odd
1 6 even
1 4 odd
7 8 even
3
3
1 1 odd
3 3 odd
1 3 odd
5
4
1 2 even
4 5 even
1 5 odd
3 3 even
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
20
8
1 9 odd
10 17 odd
18 26 odd
4 5 odd
27 40 even
21 40 odd
1 20 odd
10 20 odd
200
8
1 9 odd
10 17 odd
18 26 odd
4 5 odd
27 40 even
21 40 odd
1 20 odd
10 20 odd
-1
Answer:
4
3
3
3
2
6

Please Add it in tests!

20
10
1 1 even
4 4 even
2 2 odd
5 5 odd
1 3 even
3 5 odd
8 8 even
9 9 even
10 10 even
8 10 even
-1

Correct answer is: 5
My AC prog give 10, but correct answer is 5

It looks as first input number (sequence length) isn't needed for solution.

Why always Memory limit exceeded???
It is so wired.
package com.island.timus.ahundrend;

import java.util.Scanner;

public class T1003_Parity {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int length = in.nextInt();
        while (length != -1) {
            int[][] friendsAndEnemies = new int[2][length + 1];

            for (int j = 0; j < length + 1; j++) {
                friendsAndEnemies[0][j] = j;
                friendsAndEnemies[1][j] = -1;
            }

            int conditions = in.nextInt();
            int counter = 1;
            for (int i = counter; i <= conditions; i++, counter++) {
                Term.start = in.nextInt();
                Term.end = in.nextInt();
                Term.parity = in.nextLine();
                if (Term.start > length || Term.end > length) {
                    break;
                }
                if (Term.parity.trim().equals("even")) {
                    join(friendsAndEnemies[0], Term.start - 1, Term.end);
                } else {
                    int eneymyAncestor1 = findAncestor(friendsAndEnemies[0], Term.start - 1);
                    int eneymyAncestor2 = findAncestor(friendsAndEnemies[0], Term.end);
                    if (friendsAndEnemies[1][Term.start - 1] == -1 && friendsAndEnemies[1][Term.end] == -1) {
                        friendsAndEnemies[1][Term.start - 1] = eneymyAncestor2;
                        friendsAndEnemies[1][Term.end] = eneymyAncestor1;
                    } else if (friendsAndEnemies[1][Term.start - 1] != -1 && friendsAndEnemies[1][Term.end] == -1) {
                        join(friendsAndEnemies[0], friendsAndEnemies[1][Term.start - 1], Term.end);
                        friendsAndEnemies[1][Term.end] = eneymyAncestor1;
                    } else if (friendsAndEnemies[1][Term.start - 1] == -1 && friendsAndEnemies[1][Term.end] != -1) {
                        join(friendsAndEnemies[0], friendsAndEnemies[1][Term.end], Term.start - 1);
                        friendsAndEnemies[1][Term.start - 1] = eneymyAncestor2;
                    } else {
                        join(friendsAndEnemies[0], friendsAndEnemies[1][Term.end], Term.start - 1);
                        join(friendsAndEnemies[0], friendsAndEnemies[1][Term.start - 1], Term.end);
                    }
                }
                int pause = check(friendsAndEnemies);
                if (pause == friendsAndEnemies[0].length) {
                    continue;
                } else {
                    break;
                }
            }

            System.out.println(counter - 1);
            for (int i = counter + 1; i <= conditions; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                String z = in.nextLine();
            }
            length = in.nextInt();
        }
    }

    private static int findAncestor(int[] friends, int value) {
        int r = value;
        while (r != friends[r]) {
            r = friends[r];
        }
        return r;
    }

    private static void join(int[] pre, int x, int y) {
        int ancestorX = findAncestor(pre, x);
        int ancestorY = findAncestor(pre, y);
        int r = y;
        if (ancestorX != ancestorY) {
            while (r != pre[r]) {
                int temp = pre[r];
                pre[r] = ancestorX;
                r = temp;
            }
            pre[ancestorY] = ancestorX;
        }
    }

    private static int check(int[][] friendsAndEnemies) {
        int i = 1;
        for (; i < friendsAndEnemies[0].length; i++) {
            int friendAncestor = findAncestor(friendsAndEnemies[0], friendsAndEnemies[0][i]);
            int enemyAncestor = -1;
            if (friendsAndEnemies[1][i] != -1) {
                enemyAncestor = findAncestor(friendsAndEnemies[0], friendsAndEnemies[1][i]);
            }
            if (friendAncestor == enemyAncestor) {
                break;
            } else {
                continue;
            }
        }
        return i;
    }

}

class Term {
    public static int start;
    public static int end;
    public static String parity;
}

Deleting this post... had to hack another solution. Still don't see what was wrong with the original approach... must have been some kind of parsing issue with the input.

Edited by author 08.02.2015 09:36

Please, who solved this problem with disjoint sets send me your solution to the e-mail which is in my profile.
I wrote the code and it gives right answers on many tests, but not passes here. I need to compare where an error is.

I don't understand why it show me a Runtime error (access violation) when it s compiling and it works perfectly in my computer ???

In some way,I got test1.
In the about 570th line,there is a mark"'".I don't know what is it for.I think it is by mistake.
It is same with some large test points.

Edited by author 05.04.2009 22:14

please tell me if the max length is 109. which type i could use?

The input is of multiple testcases, and each testcase starts with N, the length of the sequence, and K, the number of pairs of intervals. You only know when you stop after got N == -1.

Naive ideas will get TLE even for testcase #1, and you will see your code runs out of 2s limit when feeding a testcase with N=10^9 and K=5000, when all pairs are good and you should output 5000.