ASYA2 - Editorial

editorial
,
1

PROBLEM LINK :

Contest

Practice

Author : Asim Krishna Prasad

Tester : Sarvesh Mahajan

DIFFICULTY :

CAKEWALK

PREREQUISITES :

Bitwise operations

PROBLEM :

Given two sets of strings A and B, you have to find how many such pairs (Ai, Bj) exist such that concatenation of the two strings contains all the letters of English alphabet.

EXPLANATION :

First there are a few observations :

  • We don't need the whole string for computation. We just need to know if a particular alphabet is present in a particular string or not.
  • Since we can loop over A x B, we only need a fast method to represent and concatenate two representations of strings

To solve this problem we can use bits to map if a particular alphabet is present in a string or not. So,

  • A string will be represented as an integer value which has bits set corresponding to each distinct alphabet present in the string. Example : for string A : 1, for string AC : 5 = (101)2.
  • Now concatenation of two strings would be equivalent to taking bitwise-or of the corresponding integers. That is, if either one of the strings has a bit set, it would be set in the concatenated string.

To make the integer corresponding to a string :

int inLimit = strlen(str1);
int num = 0;

fl(j,0,inLimit)
{
    int ele = int(str1[j]-'A');
    num |= (1 << ele);
}

Now the answer is the number of pairs (Ai Bj) such that bitwise-or of them has 26 set bits from beginning or bitwise-or has value equal to ( (1 << 26) - 1).

SOLUTION :

Setter’s solution

2

I think it the TL was a little strict and could be relaxed. I had a lot of trouble getting it AC even with expected approach.

3

@nibnalin Can you please link me your code which gave TLE?

1 Like
4

@pakhandi Sure, https://www.codechef.com/viewsolution/11623052

This gets TLE even though I have used scanf+printf. Adding few constant time optimisations made the same accepted: https://www.codechef.com/viewsolution/11623490

5

You are using strlen() in the loop… which makes your solution a little slower…

6

@pakhandi, yeah, probably, but compilers usually optimise that if we use -O2 flag(CC does). The AC submission also used strlen and compiler optimised versions are expected to be the same afaik.

7

Hey, I really don’t know if compiler optimizes this. I tried running your code and it runs forever on my system too. Since you are using strlen() call for every iteration, this makes your loop of order of n^2 which effectively makes that complete loop : n1 * strlen(S1) * strlen(S1)
While in the AC code you have saved the strlen() result in a variable and used it which makes it : n1 * strlen(S1)

8

Are you sure you used optimisation flags? I tried to look up the machine code, it seems optimised with -O2 flag on my machine(G++ 4.9)

9

Yep, it looks like -O2 is supposed to optimise it https://godbolt.org/g/DGeWpD

Anyway, thanks for your help. I suppose there is some reason due to which it isn’t optimising the way it should. I
ll be more careful next time :smiley: