Yeah, in languages like python and ruby the problem involves is mainly algorithmic, it is never or barely language problem, while in langs like C and even haskell, the problem, atleast to me, is distributed into language problem and algorithmic problem, the harder part in this scenario is these two problems are not readily available to hand, one have to literally change the form of the algorithm to make the problem feasible to solve.

@JohnRennie Hi

@JohnRennie Please ping me when you are here

@Dante hi :-)

@AjayMishra the thing that old time C hackers like about C is that it's so fast. It is about as close as you can get to programming in assembler in a high level language. There's a good reason why operating systems like Linux are written in C.

@JohnRennie Hey!

@Dante hi

codechef.com/DEC19B/problems/BINXOR

codeshare.io/2Kqdro

I really don't understand where I'm going wrong

I'm getting correct outputs for manual input

PS: Above links will be deleted in 30 secs

Please copy'em

Did you?

I've got them

There's an error on line 50:

    SUM==4;

I'm guessing that should be:

    SUM=4;

Ah yes, corrected that.

Passed through the first subtask

The remaining ones give WA

Btw, could you please delete the links above?

I'm unable to do it now

I can't delete them. I can only move them to the Trash room, and they can still be seen in that room. I'll do that if you want, but you don't know who will see them in the Trash room. I've leave them here where at least only a few people will see them.

Which I will delete in a minute

I hope you had copied that

Yes, I grabbed a copy of it to compile locally.

okay, cool

Btw, don't use codechef's problem page to compile it. Not sure, but I think codechef has a plagiarism tracker, we both might loose ratings/points

OK

Isn't your code suppose to be reading two binary strings A and B?

It is reading the strings charaterwise in the function execute

Your code could do with a few comments. Reading it is like wandering in a maze of twisty passages ...

As a general rule when writing a program start at the top and write that, then work down. So write the main function first and put in dummy functions where necessary.

Yeah, true, gimme a moment to add a few comments

Actually I might be tempted to keep the input as an array of characters to make it easier to rearrange them.

@JohnRennie I'm not arranging the strings characters directly, that would not be efficient

It would make permuting the characters of the string efficient

I'm finding maximum number of 1s possible in the answer denoted by MAX and similarly MIN and then finding out C(N,MIN)+C(N,MIN+2)…..C(N,MAX)

What is your algorithm for calculating the number of distinct values for the XOR?

I can find the number of 1s possible in the answer strings after doing all sorts of shuffling. As I observed, the number of 1s in the answer string differed as MIN,MIN+2,...MAX

For every case, arranging those 1s in N different places in a different way gives me a different number

chat.stackexchange.com/transcript/message/52918144#52918144 To calculate this, I took help of the formulae given by Ajay Mishra yesterday

Take an example of the two strings 100 and 110. I've just worked through this manually and I get four possible XORs 001, 010, 100 and 111.

Can you walk me through how your method works?

Yes, here, MIN=1, MAX=3, right?

100 XOR 011 has only one 1 in the answer string

How do you compute MIN and MAX?

100 XOR 110 has 3

@JohnRennie Just write them in lexographic order!

Other way round: 100 XOR 011 = 111

@JohnRennie Yeah, that's MAX=3

To get MIN, write both strings in lexographic order and XOR them

In this case it's obvious that the maximum number of 1s is 3. But I don't see what the general case is. Suppose A has a 1s and B has b 1s. What is the maximum number of 1s?

To get MAX, write the second string in opposite of lexographic order and XOR them again

Ah, OK ...

Yes, I see. You are maximising and minimising the number of collisions between equal values.

yes

Then to calculate the combination without using time consuming factorials, I used the formulae in the in the pic I sent above

And then for each number of 1s n it's just C(n,N). Add all the Cs up to get the total.

Yeah

But wait.

Consider my example 100 and 110. MAX=3 and MIN=1, but there is no XOR that has two 1s in it.

The possible XORs are 001, 010, 100 and 111.

There isn't, that's why the sequence is MIN,MIN+2,MIN+4.....MAX

Ah, OK.

Your code seems to work for my test case of 100 and 110:

D:\rhs\c>dante
Enter the number of tests: 1
No. tests = 1
Enter the string length: 3
string length = 3
Enter the first string: 100
Enter the second string: 110
Computing XORs ...
4

@Dante What's the problem when you run it?

@JohnRennie one sec, codechef isn't responding

WTH

How can that happen, I just tried to login from Mozilla at the same time and my code has been deleted.

Shit, all my codes are deleted.

All i can see are templates ;_;

I've never used Codechef so I can't comment...

I have a local copy of your code if you need it.

Yes, please pass that one atleast

;_;

Give me a moment and I'll put it on my server ...

@Dante I'll post the link then delete it again. Ready?

Ready

@Dante got it?

Yes

@JohnRennie, Hi sir. Are you busy here?

Sorry for disturbing.

@M.GuruVishnu We're trying to debug some code ...

@JohnRennie Ok sir.

I'll post my doubts in Pr.So.St., kindly reply when you find time. Thank you sir.

@JohnRennie Gimme a minute till I undo the changes you hae done and put it in codechef again

I think it's a brave move to not keep local copies of your code ...

Lesson learnt (I completely lost one code which I hadn't submitted), this was the first time I ever coded on such websites.

@Dante my only changes are to add some printfs and delete some unnecessary scanf("\n") calls.

This works

Yes

D:\rhs\c>dante
Enter the number of tests: 1
No. tests = 1
Enter the string length: 3
string length = 3
Enter the first string: 000
Enter the second string: 000
Computing XORs ...
4

Oops! :-)

Output is 1, it still works

I got the output 4 ...

That might be because of the changes you made ig

I think always better to use \n in scanf when dealing with characters

Do you want me to post my code again?

That's odd. Although I've made a few changes they are only printfs and should change the logic. So why do I get a different answer?

But anyhow, if your code works what's the problem?

imgur.com/a/59Jwt9X

It isn't able to pass through subtask 2 and 3

Subtask 2 presumably tests it for some large value of N and it's failing that test?

yes

Constraints fo subtask 2 are given in the question

Can you post your code again. I'll try it without my changes. You can upload it to swarchive.ratsauce.co.uk/.uploads to avoid posting a link.

Oh, it failed for this input

imgur.com/sPL0UvL

That looks like an integer overflow to me.

Uploaded

not sure why that should happen....

I've used long long wherever required

also, after each step, I'm subtracting 100000007

There's some screwy about the input in your code. When I try it it just hangs after inputting the second number.

D:\rhs\c>dante
1
3
000
000
-- hangs here ---

Hold on, let's try codeshare, ready?

It's OK. I've got it working by changing the input:

    buf = malloc((N+1)*sizeof(char));

    gets(buf);
    for(int i=0;i<N;i++)
    {
        if(buf[i]=='0') Asum0++;
        else Asum1++;
    }

    gets(buf);
    for(int i=0;i<N;i++)
    {
        if(buf[i]=='0') Bsum0++;
        else Bsum1++;
    }

I uploaded a link in your archive

D:\rhs\c>dante
1
3
000
000
1

okay, cool

OK so you found it fails for a text case with N=100

yes

Which variable you think could be overflowing?

Have you got the input file you used for the 100 digit case?

imgur.com/a/eOxj6UG I think this is what is overflowing

100C50 can't be stored in long long

@JohnRennie I can copy paste the sring

For subtask 2 N can be up to 1000

You're going to struggle to calculate C for that many digits ...

Yeah, will have to find a better way to do this

A better way to apply modulo...

@Dante I'll have to leave that with you. I have no idea what algorithm would work for such large numbers.

Yeah okay..I'll try my best

I think there are few theorems on the modulo function which could be useful.

@JohnRennie Could you tell me the approximate intervals when you will be available again until 3 pm IST tomorrow?

I am around from 05:00 until 13:00 UK time every day, though Mondays are pretty busy for me for the first few hours. I m usually around between 16:00 and 18:00 UK time, but that's getting near the end of my day and I don't usually want to get involved in anything intense at that time.

So I'll be around this afternoon from about 21:30 IST and tomorrow morning from around 14:30 IST.

Or I'm around now for about another 90 minutes.

oh, okay

Hi

Anyone?