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

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

4 Likes
3

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

4

Simple thinking :slight_smile: Very nice

1 Like
5

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

1 Like
6

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

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

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
9

Please Help me out too !

Code zlkvOh - Online C Compiler & Debugging Tool - Ideone.com

Getting WA !!

10

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

after seeing this editorial, i feel stupid. good question setter. thumps up for u

1 Like
12

Such problems are so necessary to remind us that cases determination is an important part however easy the problem be … good thinking …

13

Can someone tell me the problem in this solution:
http://www.codechef.com/viewsolution/2727952
Been stuck for too long.
Tried removing one getchar() but that didn’t work either.

14

Frustrated for not handling k==0 !!

1 Like
15

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

16

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.

17

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

18

@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

19

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

1 Like
20

@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