RRCODE - Editorial

Problem Link:

Practice

Contest

Author: Roman Rubanenko
Tester/Editorialist: Utkarsh Lath

Difficulty:

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] op … op A[N] op A[1] op A[2] op … op 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] op … op 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:

Setter’s solution
Tester’s Solution

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 :slight_smile: Very nice

1 Like

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

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

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

Please Help me out too !

Code http://ideone.com/zlkvOh

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