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.

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.

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

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

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

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

В условии сказано, что длина последовательности задается в первой строке каждого теста.
В примерах на форуме длина общая для всех, в каждом тесте задается только количество вопросов.
Моя 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

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

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

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.

#include <iostream>
#include <cstdio>
#include <deque>
#include <map>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
using namespace std;
const int maxn=20002;
int Hlen=6000;
int father[maxn];
int flag[maxn];
int getfather(int x)
{
    int tmp=father[x];
    if(x==father[x])
        return x;
        else
        {
            father[x]=getfather(father[x]);
            return father[x];
        }
}
void Union(int x,int y)
{
    int fx=getfather(x);
    int fy=getfather(y);
    if(fx!=fy)
      father[fy]=fx;
}
void init()
{
    for(int i=0;i<maxn;i++)
        father[i]=i;
}
int mp(int x)
{
    int ax=x%Hlen;
    if(flag[ax]!=-1&&flag[ax]!=x)
        ax=(ax+1)%Hlen;
    flag[ax]=x;
    return ax;
}
int main()
{
    int len,N,i;
    int level=10000;

    while(1)
    {
    scanf("%d",&len);
    if(len==-1)
        break;
    scanf("%d",&N);

    init();
    memset(flag,-1,sizeof (flag));
    for(i=0;i<N;i++)
    {
        int a,b;
        char str[10];
        scanf("%d%d%s",&a,&b,str);
        a=mp(a-1);
        b=mp(b);
        if(str[0]=='e')
        {
            if(getfather(a)==getfather(b+level))
                break;
            Union(a,b);
            Union(a+level,b+level);
        }
        else
        {
            if(getfather(a)==getfather(b))
                break;
            Union(a,b+level);
            Union(a+level,b);
        }
    }
    char str1[100];

    int m=i;
    for(i;i<N;i++)
        gets(str1);
    printf("%d\n",m);

    }
    system("pause");
    return 0;
}

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!

Hi all,

For the following input, the answer should be 202, I believe. Can someone please verify?

http://www.fi.muni.cz/ceoi1999/parity/PARITY.I8

If it should be 201, could you please explain why?

My program passed tests posted below but i got TLE in #1 test. I really don't know what is wrong with it. Could someone help me by telling me what is wrong or giving me some test? I would be very grateful.

TESTS:
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

ANSWERS:
4
3
3
3
2
6

MY CODE:
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        Main test = new Main();
        List<Integer> results = new ArrayList<Integer>();

        // LOADING DATA
        while (true) {
            int length = input.nextInt();
            input.nextLine();
            if (length == -1) {
                break;
            } else {
                int hintCounter = input.nextInt();
                input.nextLine();

                // IF THERE IS NO ANSWER - CONTINUE
                if (hintCounter == 0) {
                    results.add(0);
                    continue;
                }

                List<Row> testData = new ArrayList<Row>();

                // READ ANSWERS
                for (int i = 0; i < hintCounter; i++) {
                    int start = input.nextInt();
                    int end = input.nextInt();
                    String parity = input.nextLine().trim();
                    Row newRow = test.new Row(start, end, (parity.equals("odd")) ? true : false);
                    testData.add(newRow);
                }

                Database db = test.new Database(length);
                int correctHints = 0;

                // ADD ANSWERS TO DATABASE AND CHECK AUTHENTICITY
                for (int i = 0; i < testData.size(); i++) {
                    Row r = testData.get(i);
                    db.addElement(r.start, r.end, r.odd);
                    if (db.isConsistent()) {
                        correctHints++;
                    } else {
                        break;
                    }
                }

                results.add(correctHints);
            }
        }

        // PRINT RESULTS
        for (int i = 0; i < results.size(); i++) {
            System.out.println(results.get(i));
        }

    }

    private class Row {
        int start;
        int end;
        Boolean odd;

        public Row(int pStart, int pEnd, Boolean pOdd) {
            start = pStart;
            end = pEnd;
            odd = pOdd;
        }
    }

    private class Database {
        HashMap<Integer, HashMap<Integer, Boolean>> data;
        Boolean consistent;
        int maxLength;
        int maxX;
        int maxY;
        int minX;
        int minY;

        public Database(int pMaxLength) {
            data = new HashMap<Integer, HashMap<Integer, Boolean>>();
            consistent = true;
            maxX = 0;
            maxY = 0;
            minX = 2000000000;
            minY = 2000000000;
            maxLength = pMaxLength;
        }

        public Boolean isConsistent() {
            return consistent;
        }

        public void addElement(int x, int y, Boolean odd) {

            consistent = ((x < 1 || y > maxLength) ? false : true);

            if (consistent) {
                if (data.containsKey(x)) {
                    // X ALREADY EXISTS
                    if (data.get(x).containsKey(y)) {
                        // Y ALSO EXISTS
                        consistent = (data.get(x).get(y).equals(odd) ? true : false);
                        return;
                    } else {
                        // Y NOT EXISTS
                        maxY = (y > maxY ? y : maxY);
                        minY = (y < minY ? y : minY);
                        data.get(x).put(y, odd);
                    }
                } else {
                    // X NOT EXISTS
                    maxX = (x > maxX ? x : maxX);
                    minX = (x < minX ? x : minX);
                    data.put(x, new HashMap<Integer, Boolean>());
                    data.get(x).put(y, odd);
                }

                // UPDATING THE DATA
                updatePefixes(x, y, odd);
                updateSuffixes(x, y, odd);
            } else {
                // DO NOTHING
            }

        }

        public void updatePefixes(int x, int y, Boolean odd) {
            // UPDATING PREFIXES
            for (int i = minX; i < x; i++) {

                if (data.containsKey(i) && data.get(i).containsKey(x - 1)) {
                    Boolean leftOdd = data.get(i).get(x - 1) ^ odd;
                    addElement(i, y, leftOdd);

                    for (int j = y + 1; j <= maxY; j++) {
                        if (data.containsKey(y + 1) && data.get(y + 1).containsKey(j)) {
                            addElement(i, j, leftOdd ^ data.get(y + 1).get(j));
                        } else {
                            // DO NOTHING
                        }
                    }
                } else {
                    // DO NOTHING
                }
            }
        }

        public void updateSuffixes(int x, int y, Boolean odd) {
            // UPDATING SUFFIXES
            for (int i = y + 1; i <= maxY; i++) {
                if (data.containsKey(y + 1) && data.get(y + 1).containsKey(i)) {
                    addElement(x, i, odd ^ data.get(y + 1).get(i));
                } else {
                    // DO NOTHING
                }
            }
        }

    }
}

...

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!!!

if you are get wrong answer #1 or time limit #1 , probably your bug is that,you don't read input to end..I was get time limit #1..Because I didn't read input to end..when I find correct answer I break..then I found my bug and I read input to end..finally I got AC..If you don't read input to end , probably , your bug is that..you must read input to end..


Edited by author 17.06.2011 05:11

2, 2 even is impossible? there are those cases?

2, 3 even implies that the sequence of binary numbers is 11 between 2 and 3?

in a sequence of binary digits as 000, there is not an even number of 1's or an odd number of 1's. But it was always supposed to be even or odd ... But zero is not even or odd

???