RRCODE - Editorial

editorial
, , ,
1

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
2

Frustrated for not handling k==0 !!

1 Like
3

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

4 Likes
4

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

5

Simple thinking :slight_smile: Very nice

1 Like
6

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

7

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

1 Like
8

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 );
9

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.

10

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

11

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]);
			
}
12

@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

13

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

1 Like
14

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
15

@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
16

@stefanpochmann yes, that’s the culprit. Thanks

17

Please Help me out too !

Code http://ideone.com/zlkvOh

Getting WA !!

18

@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. .

19

@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
20

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