# RRCODE - Editorial

Practice

Contest

Author: Roman Rubanenko
Tester/Editorialist: Utkarsh Lath

Cakewalk

# Pre-requisites:

understanding of bitwise operators

# Problem:

Given a list of numbers A, and integers K, Ans, and function op, predict the outcome of following function

``````
int F(K, Ans, op, A[N])
for i=1 to K
for j=1..N
Ans = (Ans op A[j])
return Ans

``````

op can be either XOR, AND, or OR.

# Explanation:

Lets first try to see what is the complexity of the above function. The outer loop runs K times and inner loop runs N times, giving O(NK)**. Since K ≤ 109, N ≤ 1000, doing it naively can take upto 1012 instructions, which will time out.

If we think about it, the final answer can be written down as:

Ans op A[1] op A[2] opop A[N] op A[1] op A[2] opop A[N] … K times …

Using associativity of The operators, if M is the result of applying all operators once, then

M = A[1] op A[2] opop A[N]
Ans = Ans op M op M op …K times… op M

However,

M AND M = M
M OR M = M
M XOR M = 0

Therefore, K can be totally eliminated from our complexity, because

• If op is either AND or OR, then for K > 0,

M op M op …K times… op M = M

• If op is XOR, then

M op M op …K times… op M = M if K is odd, 0 otherwise.

The final solution would be

``````
int FFast(K, Ans, op, A[N])
if (op is XOR)
K = K%2
else
K = min(K, 1)
return F(K, Ans, op, A)

``````

# Solutions:

6 Likes

### Frustrated for not handling k==0 !!

1 Like

Of course, you meant `K = min(K, 1)` in the else part of `FFast`, right?

4 Likes

Hey folks, if anyone here can check my code, link1 or link2, I was finding a corner case almost 3 hours but I am not successful if that, if any of you have solved solved the problem please check

Simple thinking Very nice

1 Like

use operator=raw_input().strip()
caused me a lot of WA too …

didn’t handle the case when k==0 …

1 Like

Hi utkarsh/anyone else, after scanning the inputs, when I write the following piece of code, it gives TLE … Do you ave any idea why is it happening so…

``````	if (strcmp(op,"AND")==0){
for (j=0; j<n; j++){
ans &= a[j];
}
}
else if (strcmp(op,"OR")==0){
for (j=0; j<n; j++){
ans |= a[j];
}
}
else{
if (k%2 == 1)
for (j=0; j<n; j++){
ans = ans ^a[j];
}

}
printf("%d\n",ans );``````

What the hack, they said no white spaces around AND, OR, XOR. If this is so @admin must see into this, because either you must not say that in the Problem Statement or Must have it implemented too. It has wasted a lot of time of everyone here having WA, when even our solutions was correct.

@sayantancs there might be some whitespace in your op , try taking care of that

What’s wrong with this code for handling XOR operation.

``````if(type[0] == 'X'){
for(i = 0;i<n;i++)
ans = (ans ^ a[i]);

if(!k%2)
for(i = 0;i<n;i++)
ans = (ans ^ a[i]);

}``````

@sayan_paul Here is the input statement of the problem

Input

The first line of input contains an integer T - the number of test cases in file. Description of each test case consists of three lines. The first one contains three integers N, K and initial Answer. Array A is given in the second line and Operator is situated on the third one. Operators are given as strings, of capital letters. It is guaranteed that there will be no whitespaces before or after Operator.

clearly specifying no whitespaces in the input

!k%2 might get interpreted as (!k)%2.

1 Like

what’s wrong with my codes??

``````
for i in range(int(raw_input())):
n, k, ans = map(int, raw_input().split(' '))
a = map(int, raw_input().split(' '))
s = raw_input()
if k:
if s == "XOR":
for l in range(1, n):
a[0] ^= a[l]
if k % 2:
ans ^= a[0]
elif s == "AND":
for l in range(1, n):
a[0] &= a[l]
ans &= a[0]
elif s == "OR":
for l in range(1, n):
a[0] |= a[l]
ans |= a[0]
print ans
``````

@sayantancs you get TLE not bcz of this. When you get k==0 then you simply continues the loop without reading the array elements and operator.

1 Like

@stefanpochmann yes, that’s the culprit. Thanks

Getting WA !!

@devanshug i know its written in the problem statement but many people have got WA because is this(including me) , sorry i didn’t see it was for TLE in code not wa in this case. .

@devanshug,@r3gz3n although mentioned in the problem statement , many people wth correct salgo have got WA because they didn’t take care of whitespace at end of line.

@r3gz3n try strip() function after the operator.

@all getting WA try taking care of whitespace after operator , if it helps …

2 Likes

Try s = raw_input().strip(), that’s what my solution needed. If that doesn’t help, also try split() instead of split(’ '), don’t know why you’re doing that anyway.

1 Like
//