parity problem

if the pattern holds, you don't need to compute that, it just tells you the answer.
if you have 10 evens and 20 odds and insert an odd, if the pattern holds (and I don't know that it does, that is for you to look into, or another pattern, etc) and you insert an odd, 10es ^ o -> 10 new odds and 20os ^ o -> 20 new es. its counted for you, except you need to uncount any duplicates somehow. There has to be an efficient way to string all these ideas together... and this may not be the right answer, but this is how to look at the problem.

Last edited on

yes. you have to figure out a way to do it without brute force. if nothing I said helps, find your own pattern. xor has a LOT of neat properties. One of them is almost certain to solve this thing.

so if x can be 100k, the biggest y is 131071, right?

you can't count bits, and you can't hunt & peck for duplicates. so you have to eliminate those 2 things.

Last edited on

https://graphics.stanford.edu/~seander/bithacks.html#ParityMultiply
Is that the cheapest even/odd checker?
a byte-wise lookup table of it and then run across the bytes is more expensive I think, you have 4 bytes here, so 4 pointer offset grabs, 4 bit ops on the results of that, and a conditional around the mess. however, his lookup attempt is really slick:
https://graphics.stanford.edu/~seander/bithacks.html#ParityLookupTable

a lookup table (vector bool) should serve for dupes if I was right about the 131071. But some of these sites have a memory limit too.

I think you are right about having to do the xors.
so basically get x, see if it is even or odd, and xor it with each thing in S. without an if statement, use bools as 0/1 values, add to your total for e/o based off whether you already saw it using the lookup table, then set the lookup table to seen status (which I am thinking will be zero, not one, here, to make it easier?).
that looks like, without if statements,

for(all in s)
{
y = s.nextvalue(); //however you want to handle this. this is a critical step.
something = x^y;
e+= (int)(table[something]==true); //adds 0 or 1
o+= (int)(table[something]==false); //adds 0 or 1
table[something] = false; //or true, not 100% sure on the reverse logic being easier
}
don't forget insert x and update e and o

Last edited on

Are you saying that a naive brute force implementation like this doesn't work? Or are you actually counting bits over and over again to get E and O? This is just partial code, I haven't coded it. EDIT: Okay, now it compiles. But I haven't run it.

#include <iostream>
#include <set>

// Not the fastest, but could be fast enough.
bool is_odd(int n) {
    int c = 0;
    for ( ; n; ++c) n &= n - 1;
    return c % 2;
}

// If available:
//bool is_odd(int n) {
//    return __builtin__popcount(n) % 2;
//}

void adjust(int x, int& even, int& odd) {
    if (is_odd(x)) ++odd; else ++even;
}

void process() {
    std::set<int> set;
    int even = 0, odd = 0;
    int q;
    std::cin >> q;
    for (int i = 0; i < q; ++i) {
        int x;
        std::cin >> x;
        auto result = set.insert(x);
        if (result.second)
            adjust(x, even, odd);
        for (int m: set)
            if ((x ^ m) != 0) {
                auto result = set.insert(x ^ m);
                if (result.second)
                    adjust(x, even, odd);
            }
    }
    std::cout << even << ' ' << odd << '\n';
}

int main() {
    int t;
    std::cin >> t;
    while (t--) process();
}

Last edited on

This is a problem from an ongoing codechef contest. Seeking little help is fine but I don't think sharing codes is. Even if you get a great rating after this contest, u would still be a cheater.
While others are trying the whole day to figure out the solution, here u are!

@dutch I request u to delete your code, to stop more people from copying and cheating.

@aryaaa5, Maybe you should shut up.

I simply don't care.
The whole thing is pathetic.
You're like rats, infesting the site every few weeks.
Your competitions are a joke.

Read a book.
Write your own programs.
Study other well-documented projects.
Get a girlfriend.

Maybe I'll post complete solutions to the next couple of contests.
How about that?
Report away, buddy.

@dutch May be you should mind your language buddy. While I was 'requesting' you to not to share your code and help others cheat(knowingly or unknowingly), you are using this language?
And for your kind information, I was not the one who has reported your comment. I don't even know who did.
And I'm the one infesting the site?? It is people like you who share solutions and make people come here for help. Maybe if u don't share solutions, people stop coming here one day, right!?

Last edited on

I will post all of the solutions to the next "contest" you holier-than-thou little prick.
Happy?
And how is posting a mindless brute force "solution" being a "hero".
And how can someone "cheat" in something so utterly pointless?
You are a pathetic little loser.

Last edited on

Then stop ranting that people are infesting this site. If people like you stop helping, others would stop asking for help.
Also, the contest might be absolutely pointless for you, I do agree. But not necessarily for others right?
And before calling me a loser, look at yourself :) Other than abusing some random stranger who is still treating u with respect, what are u doing with ur life? Go get some help and stop spreading hatred. Respect and peace _/\_

ne555 (10692)

> Are you saying that a naive brute force implementation like this doesn't work?
that should probably exceed the time limit.
the size of the set increase rapidly, you may reach the maximum size of 131071 in a couple queries.
then every next query will traverse that set each time, you end up with a O(n^2) algorithm with n in the order of 1e5, too much.

one thing you may do is to avoid the operation if you know that no new value will be inserted
one check may be

1
2

auto result = set.insert(x);
if (not result.second) continue;

Last edited on

ooo I got reported too. /worry.

the size of the set increase rapidly, you may reach the maximum size of 131071 in a couple queries.

it less than doubles in size each time, or right at doubles?
add one. add another, and it adds the original again, total 3. add another, and the previous 3 are added as well, total 7 possible. and so on, but you start hitting duplicates, so while its technically 2n+1 every go the dupes cut it down at an increasing rate as it gets 'full'.

guessing 15, 20 to fill it on the average? I didnt bother to math at it, just 'at a look' guess.
I honestly don't know how to compute odds of filling in the last few entries when its nearly full. That could push it to 30-50 range or beyond.

Last edited on

ooo I got reported too

Of course you got reported! It's everybody's duty, all over the internet, to ensure the integrity of codechef competitions. THEY ARE CRUCIAL, PEOPLE!

Where will we find tomorrow's programmers if we don't test them with the worst possible problem descriptions and virtually meaningless examples? To this end, although the problems are written in English, they must be written by someone who's not exactly sure how English works.

As we all know, in real life the spec is often scribbled down on a piece of toilet paper, handed off to a programmer, and then the guy that scribbled it down shoots himself in the head. How many times have we seen this? In that situation you can't possibly ask for clarification. codechef has modelled this aspect of reality perfectly.

It's also very important that the people who score the highest are pretty much the worst programmers imaginable. The preferred language is "C with cout", and you can never have enough globals, gotos and macro functions. The code must be untrustworthy (was it well-tested?) and unmaintainable. We can, of course, be certain that codechef's test set is well-designed.

With the fate of tomorrow's programmers in codechef's hands, we can all sleep easy in our beds.

God bless you, codechef!

Last edited on

lol he even reported me counting the growth rate of the problem. Its not code chef, we have to pretend otherwise because the OP took the word chef out, right?

the OP took the word chef out

The "heroic" editing of the honest man.
Deleted a post, too.
What a little turd.

"Chef" is a known pedophile.
And afterwards, he cooks and eats them.
That's why they call him "Chef".

Last edited on

Ganado (6812)

lol

@nat104, why?

I'd rather you just report me. That way I don't have to do anything.

But what do you "have a doubt" about?
The scope is awesome. My knowledge, severely limited.

For example, if your doubt is about ancient roman aqueducts then, although I'm quite fascinated by the subject (public baths, anyone?), I really know very little, like pretty much nothing about it. They carry water, right?