Ordinary Numbers approach

help
1

I was unable to solve this question and i want to know what i missed

Given a binary string Q of length <=10^5, find total no of pairs which satisfy following conditions i+j <= X (where X is less than Q) i xor j = X return the answer in Modulo 10^9+7

Time Limit:- 2s

My approach :- Converted the input to decimal and iterated over lower half of the DP array to find such pairs. Each match increased the count by +2 as i was accounting for both of the possible pairs.

Outcome : TLE on private test cases

2

Is it from an ongoing contest?

1 Like
3

Yes it was from hackwithinfy contest. Held few months ago. They didn’t submitted a solution nor anyone discussed this so I’m asking it here

4

The difficulty of this problem is considerably high. I don’t think people who are smart enough to solve this problem will work for 8 LPA :grimacing:

Anyways, @cubefreak777 may help.

1 Like
5

Yup by the time I realised its difficulty. It was too late to pull up so i kept trying.
I hope @cubefreak777 aka L2 might be able to give some good insight on it

6

Is this the same problem that we discussed a while back @suman_18733097 or am I missing some detail?

1 Like
7

Yeah, it’s the same problem. My bad. @alphanik Hope your problem is solved now.

1 Like
8

It’s similar but not identical. This problem requires I XOR J <= I+J
Thanks though

9

Note that for any 2 numbers say X \text{and} \ Y, the following inequality holds,

X\oplus Y \le X+Y

And your problem states that

X +Y \le X\oplus Y

Both these inequalities can be satisfied simultaneously only if,

X+Y=X\oplus Y

Hence your problems essentially boils down to the problem discussed in the thread linked above.

3 Likes
10

Yup now when i checked my solution. This is what i used though i didn’t remeber why.
PS:- Community here is really nice. I posted this question on codeforces and got half hearted response.
Thankyou @suman_18733097,cubefreak777

2 Likes