# ACM ICPC Team

# ACM ICPC Team

phishman3579 + 15 comments Of all the warm-up questions, this should be ranked the hardest but it's currently ranked easy.

deeteecee + 0 comments lol that plus the first test sample i download is long as hell

abhivendrasingh + 4 comments Just Bunch of for and if loops are used. It's easy though.

punk06 + 1 comment Correct! it took me 15-20 mins just to understand to question.. then just 5 mins to code.. CHEERS!

shepherd_of_fire + 0 comments did u pass all the test cases?

aayushARM + 0 comments [deleted]aayushARM + 2 comments [deleted]somananda + 3 comments my one passes all in <=0.11s :p

https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/14289621

alexcsantos + 2 comments Not the most beautiful code ever, but under 0.07s :P https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/14623101

clydexu + 2 comments So much fun here!! Then 0.01s is comming, waiting for all 0s https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/15276552

pratikpugalia + 3 comments kamilbelter + 1 comment Nice. Have you noticed advantage of using "ios_base::sync_with_stdio(0)"?

qwei55 + 1 comment could you explain me about this line "ios_base::sync_with_stdio(0)"...

wizwarrior + 0 comments visit this , and read answers.

it's used to lower the execution time in C++ because cin/cout are slower than scanf/printf and by using this statement we can make cin/cout faster than scanf/printf.

Raslanove + 0 comments All zeroes, and not using bitsets :)

https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/21597378

ritchie_einstein + 0 comments

mayurnagdev123 + 1 comment Please can you tell me how you found out that it took you 0.07 sec to pass all test cases?

josef_klotzner + 0 comments call your script with 'time': (linux or iOS)

example for python:

time python3 ./acmTeam.py

if you have this line as first line of your script:

#!/usr/bin/python3

you can simply call it:

time ./acmTeam.py

bankarpranit26 + 1 comment How do you know the execution time ? Can you help ?

josef_klotzner + 0 comments call your script with 'time': (linux or iOS)

example for python:

time python3 ./acmTeam.py

if you have this line as first line of your script:

#!/usr/bin/python3

you can simply call it:

time ./acmTeam.py

pooyax14 + 0 comments Your submissions page is accessible only to your account. It would have helped to paste your

`code`

here if you want to share.

sumanthmw20 + 0 comments

ayushpandeyapr + 0 comments can you please explain what the question is actually asking ?

ThymeCypher + 3 comments I've read it over and over, and while I'm thinking the solution is dirt simple, the wording is horrible. After about 5 times, I still don't understand it fully.

anandneeru2 + 0 comments yup

feanor924 + 0 comments Same here.

adityagupta6149 + 0 comments Exactly

kavitakitu + 1 comment can u plz tell me why team (1,5) is not true for knowing max topics as they also know all 5 topics....

rgrahulrrr + 0 comments there is no 5, only 4 person.

namang8 + 0 comments probably easier to understand although takes 0.07s https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/35844687 nt is no. of teams knowing the max. no of topics and maxt is the maximum topics a team can know....

Rys23 + 0 comments it's not hard to find a solution that passes all the tests... it's just most likely a pretty slow solution

wanghaitang_ufl + 1 comment I was kind misled by others because they mentioned bitset. And Yes, i tried to do the binary calcuation for bitseted strings. As a result, I spent too much time. However, it can be calculated simply by comparing to the number of 1s. Here is my result in c++ https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/47932867

meethinsu414 + 0 comments pls uplaod the code. the link is not working.

esrujan + 0 comments I thought it was not hard. I have expected the test cases will be too big that my program runs out of time for few of them. But I am wondering if they actually removed/reduced the test cases to make it easy>>>

anandshukla1511 + 0 comments well its quiete easy buddy

buzz_95 + 0 comments No It Wasn't!

aniketnath283 + 0 comments here is the solution https://www.hackerrank.com/challenges/acm-icpc-team/forum/comments/473517

Arviy + 6 comments def acmTeam(topics): comb = combinations(topics,2) m = 0 count = 0 for i in comb: n = str(bin(((int(i[0],2) | int(i[1],2)))))[2:].count('1') if n > m: m = n count = 1 elif n == m: count += 1 return (m, count)

Amey_25 + 0 comments Converting the string into integer - base 2 is the crux of the problem.! Thanks buddy.!!

boiko_ivan + 1 comment So if there are 500 topics, chances you'll get an integer = 2^500. Does Python fit these size integers?

mpohily + 0 comments Yes:

pow(2, 500) 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376

joelvarma + 1 comment Python 3:

You need not use combinations, just a well written loop and if condition are just enough

def acmTeam(topic): lid=sum=0 # lowerindex of topics list uid=1 # upperindex of the topics list fin=[] while lid!=len(topic)-2: if uid > len(topic)-1: lid+=1 uid=lid+1 res=bin(int(topic[lid],2) | int(topic[uid],2)) temp_count=res.count(str(1)) uid+=1 if temp_count >= sum: sum = temp_count fin.append(sum) return (sum,fin.count(sum))

ghassan_karwchan + 0 comments did your code pass all test cases? I have some similar code loop inside loop and it is timing out

dsouzasunny33 + 0 comments [deleted]ankitrohilla1 + 1 comment I am not able to understand.

n = str(bin(((int(i[0],2) | int(i[1],2)))))[2:].count('1')

Please explain

h15303238378 + 0 comments I also can't understand this '((()))', but I found it can be omitted.

I finished this problem by the sentence:

count = str(bin(int(i[0], 2) | int(i[1], 2))).count('1')

just omit the '((()))'.

mayankinc + 0 comments [deleted]

Lay_Jain + 0 comments How do you guys find out the running time?

Kanahaiya + 0 comments ## ACM ICPC Team HackerRank Solution | Algorithms | Implementation

Source code:

`// 1st approach static int[] acmTeam(String[] topic) { int n = topic.length; BigInteger[] bi = new BigInteger[n]; for (int i = 0; i < n; i++) bi[i] = new BigInteger(topic[i], 2); int maxTopic = 0; int teamCount = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { BigInteger iuj = bi[i].or(bi[j]); int bitCount = iuj.bitCount(); if (bitCount > maxTopic) { maxTopic = bitCount; teamCount = 1; } else if (bitCount == maxTopic) { teamCount++; } } } int result[] = { maxTopic, teamCount }; return result; }`

Click here for video explanation

Would really appreciate your feedback like, dislike , comment etc. on my video.

Chessray + 6 comments Thanks for finally (after 17 years of working with Java) giving me a reason for using the java.util.BitSet class: https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/11388115

Mingling94 + 2 comments Oh gosh, I didn't think of setting the bits in BitSet one by one, instead I made longs of size 63 (LOL) to store the parsed sections of the string. Your code is much more elegant

I'm curious, how long have you been in industry if you've got 17 years of Java experience?

https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/11455472

Chessray + 0 comments This time represents the start of my studies. I've been a full time professional now for 11 years. Seen a lot, suffered a lot, still there. ;)

Spatzist + 0 comments I did it this way as well (63-bit longs), although I knew about BitSet. I thought using a standard 2D array of longs would be faster than an ArrayList of BitSets, and after trying both implementations I found it was - but only for the smaller test cases. It was pretty much equal for the longer ones at 0.25-0.30s (I'm guessing this is what people refer to as the JVM "warming up").

For anyone wondering which to use: save yourself the trouble of reinventing the wheel, and stick to BitSets.

Spatzist + 0 comments This felt like such a C++ oriented problem, given that the best way to do things was with bitwise operations. I'm impressed Java has as much functionality for bit-level operations as it does - you don't even need to use BitSet, although it certainly makes the code a lot neater.

machenbach + 1 comment Here's a little easier way to initialize the BitSets:

`skills = new BitSet[peeps]; for (int p = 0; p < peeps; p++) { BigInteger b = new BigInteger(br.readLine(), 2); skills[p] = BitSet.valueOf(b.toByteArray()); }`

SafwanA + 0 comments What if BigInteger and BitSet have been removed during interview? What will be the best approach then?

xXGoziXx + 1 comment Bitset? What's that? https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/16141334

swpalmer + 0 comments your j loop should start at k+1 so you don't have to hack the team count in half

zhadyrassyn + 0 comments What an elegant code!

douglasdejesus92 + 2 comments Is brute force really the only way? I would be very interested to hear any ideas on how this could be improved.

darkstego + 0 comments Doesn't really appear to be a way other than brute force, given all the answers I am seeing. I was thinking of making a dictionary to map a topic to a list of people, to reduce the number of comparisons needed to find the max team for each person. But that seemed like a ton of complexity, and I am not even convinced it would be faster.

FilipF + 0 comments Late reply, but here's some thoughts of mine: You can sort the people list by the number of true bits (cardinality), which would add a one time

`O(log(n))`

cost, especially if you count the 1's while you're reading in the input anyhow. Then the pairings can be tested starting from the "most knowledgeable" end, and hope you get a large combined cardinality early on. That lets you`break`

out of the inner loop when the people you're testing can't possibly improve on the max, and`break`

out of the outer loop when people's cardinality is less than half of the max found so far.Downside is that while that will hopefully speed things up, you're only reducing the complexity by a constant scaler, and

`O(n^2/x)`

is still`O(n^2)`

. In the worst case, everyone has the same number of true bits, no pair has zero overlapping knowledge, and so the shortcuts will never help you. :-/Another example: this is a challenge where the sub-problems are all independent, and so it's ripe for parallelization. Ideally that divides the run time directly in proportion to the number of cores. But again, that would still be big oh en squared, and outside the format of these challenges.

I toyed with the idea of indexing the people by where their knowledge is concentrated. Basically, break the bit list into chunks, and for each chunk count the number of true bits, and then record that information. Maybe a minimum threshold to be included in a set of people that are strong in that chunk? Or in a map with lists of people by chunk cardinality. Anyhow, then for each candidate you could identify their weakest chunk, and start with the people strongest there. The point would be to finish early by finding an unbeatable combination quickly. But you'd have no promises of improved running time. Like hashing algorithms, however you divide up the knowledge space, there's a worst case where the knowledge is spread out such to make those divisions useless.

Apology for the wall of text! And thank you for letting me ramble.

Rys23 + 2 comments My C solution

int main(){ int n, m; scanf("%d %d",&n,&m); char *topic[n]; for(int topic_i = 0; topic_i < n; topic_i++){ topic[topic_i] = (char *)malloc(1024 * sizeof(char)); scanf("%s",topic[topic_i]); } int known, max_known = 0, know_all = 0; for(int i = 0; i < n-1; i++) { for(int j = i+1; j < n; j++) { known = 0; for(int k = 0; k < m; k++) { if(topic[i][k] == '1' || topic[j][k] == '1') known++; if(max_known < known) { max_known = known; know_all = 0; } if(known == max_known) know_all++; } } } printf("%d\n%d\n", max_known, know_all); return 0; }

Ch_PavanSai + 2 comments why did you use 1024 in malloc?

arabkumar1000 + 0 comments Not necessary

Rys23 + 0 comments that was a default template for this problem I gues

ahmtmlh + 0 comments [deleted]

gummeah + 10 comments Hello my dear friends. How can I improve speed of my python code, which seems to do right calculations but it takes too long?

`totallist = [int(i) for i in input().split()] maxtopics = 0 guyslist = [] smarteams = 0 for n in range(0, totallist[0]): guyslist += [str(input())] for i in range(0, totallist[0]-1): for j in range (i+1, totallist[0]): knowntopics = 0 for q in range (0, totallist[1]): if int(guyslist[i][q]) or int(guyslist[j][q]): knowntopics += 1 if knowntopics > maxtopics: maxtopics = knowntopics smarteams = 1 elif knowntopics == maxtopics: smarteams += 1 print (maxtopics) print (smarteams)`

gummeah + 0 comments [deleted]gummeah + 3 comments I did speed it up a little bit, but still too slow:

`totallist = [int(i) for i in input().split()] maxtopics = 0 guyslist = [] smarteams = 0 for n in range(0, totallist[0]): line = list(str(input())) guyslist += [line] guyslist = [[int(y) for y in x] for x in guyslist] for i in range(0, totallist[0]-1): for j in range (i+1, totallist[0]): knowntopics = 0 for q in range (0, totallist[1]): if (guyslist[i][q]) or (guyslist[j][q]): knowntopics += 1 if knowntopics > maxtopics: maxtopics = knowntopics smarteams = 1 elif knowntopics == maxtopics: smarteams += 1 print (maxtopics) print (smarteams)`

benrcass + 1 comment You look really close, you just need a little more speed. With these Python challenges, I've found that using a built-in function is always faster than anything I can hand code. A couple of notes:

line 6: Use raw_input because it returns a string already, no need to cast

line 6-8: You can get rid of lines 6 and 7 by replacing line 8's "in guyslist" with "list(raw_input())"

line 12: Using map() instead of another for loop will help a lot. E.g. "knowntopics = sum(map(max,guyslist[i],guyslist[j]))"

Happy coding!

gummeah + 2 comments Thanks for help. map() helped a little bit, but didnt solve the problem. Cases 3-7 terminate with timeout.

Didnt get about 6-8 lines. I need to convert list elements to integers to do OR instead of comparing strings, cause it seems faster that way. Btw, Im using python3, and as far as I know raw_input() was renamed to input and running input() instead of str(input()) doesnt change anything. And yes, my code is more like "academic" now, so separation of actions makes me understand better what I do.

srajkovic + 3 comments Just a note, in my implementation I discovered that checking string equality is almost an order of magnitude faster than

`if int()`

. See below, on Python 2 (though I did my submission on Python 3 and it passed with string equality and not with`int()`

)`python -mtimeit -s'xs="10110110101010101"' 'popcount = sum([1 for x in xs if int(x)])'`

100000 loops, best of 3: 15.5 usec per loopvs.

`python -mtimeit -s'xs="10110110101010101"' 'popcount = sum([1 for x in xs if x =='1'])' 100000 loops, best of 3: 1.99 usec per loop`

JJFord3 + 1 comment That one tip took my python code from too slow to fast enough to pass. Learned something new about converting types. Thanks!

Devicharith + 0 comments can you please show your code

holamson + 0 comments Thank you for this!

alperenbag + 0 comments It's really interesting that it works. Thank you :)

benrcass + 1 comment I didn't know about raw_input in Python 3. Thanks for the heads up. Testing locally,

`list(input())`

seems to do the same thing as`list(str(input()))`

.So, I want to take a look at this:

`5: for n in range(0, totallist[0]): 6: line = list(str(input())) 7: guyslist += [line] 8: guyslist = [[int(y) for y in x] for x in guyslist]`

Line 8 shouldn't be inside your loop at all. It's looping through your 2d list, and converting everything to ints. You only need to do that after the loop, not during every iteration. E.g.:

`>>>print(guyslist) [['0', '1'], ['1', '0'], ['1', '1']] >>>guyslist = [[int(y) for y in x] for x in guyslist] >>>print(guyslist) [[0, 1], [1, 0], [1, 1]]`

So, you could compact that block down to:

`5: for n in range(totallist[0]): 6: guyslist += [list(input())] 7: guyslist = [[int(y) for y in x] for x in guyslist]`

Finally, as srajkovic notes, string compares are faster than str to int conversion plus int compares. So, you can drop the

`guyslist = [[int(y) for y in x] for x in guyslist]`

line entirely and just make`if (guyslist[i][q]) or (guyslist[j][q]):`

use string comparisions.amruthpolavarapu + 1 comment Did this help you @gummeah. My code is similar to you. I am not able to pass the test cases due to timeout

drachu + 0 comments There is way to many for-loops. There is a hint:

`a = 1 b = 3 c = a | b # gives 3 as well, it's binary operation`

How many topics is covered in C?

`print bin(c).count('1') # equals two`

Also there is 4 loops in this solution, it can be achieved with one or two.

tpb261 + 0 comments a few functions is all the hint you will need, or, maybe 2: int() and bin() and string.count()

chuppi_angadi + 0 comments def acmTeam(topic): res=[] for i in range(len(topic)-1): a = int(topic[i],2) for j in range(i+1,len(topic)): b = int(topic[j],2) x=bin(a|b) x=str(x) res.append(x.count('1')) return [max(res),res.count(max(res))]

valq7711 + 7 comments Your code look like C++, but not Pythonic. Power of Python - built-in batterys!

Use`int(bin_string, 2)`

to convert string of binary representation:`int('101', 2)=5`

It allow use bitwise OR (very fast).

For counting '1' in OR-result just do it:

`bin(or_rslt).count('1')`

In sum, it turns to something like this:

`Pairs_max_top_lst=`

`[bin(guys_lst[i] | guys_lst[j]).count('1')`

`for i in xrange(N_guys-1)`

`for j in xrange(i+1,N_guys) ]`

`max_top=max(pairs_max_top) max_team_num=pairs_max_top.count(max_top)`

gummeah + 2 comments Thanks for reply!

Just to make it clear. Did I understand right, that we first need to convert strings(elements of list, for example) of type string to integer type and then bin(i | j).count('1') will compare that integers bit by bit like they were in binary format, so we actually get how many '1' one(i) or another(j) integer has in 'uniq' bit position?

I hope that you can understand what I just said :D

okyantoro + 0 comments built-in function is really amazing :D

roryneil + 0 comments Thank you so much for your help. I'm mainly a PHP and C# developer, and doing this to learn Python 3. This just added new tools for my toolbox, and brought my code from 15+ lines to 3!

conkosidowski + 1 comment Yes! This is so fast! This has been very useful.

- Store every line as the decimal conversion of the string interpreted as a binary number
- Perform a bitwise OR operation on all sets of two lines and count the amount of "1"s
- If a given line is greater than the max, set the max and maxCount to 1
- If a given line is equal to the max, set the maxCount += 1

Thank you for the mention of the second parameter in the int function. I was struggling to figure out how to interpret a string as a binary number.

ghosh_saikat4000 + 1 comment But, M can be as large as 500 !

conkosidowski + 0 comments Had to look it up http://deeplearning.net/software/theano/tutorial/python-memory-management.html. I don't think python has any problem representing such large numbers.

abhilash_ponnac1 + 0 comments Thsi one change of bit magic made all the time difference. I was about to write my own int[] to hold the bits implementation. This saved me all the trouble. valq7711 you are a genius!!

armoner24 + 0 comments Thanks dude, just made my day. It worked like a charm.

Kostyantin_Kon + 0 comments I updated your code to current state of affairs (Python 3, current task formulation with variables n adn m, fixed minor errors):

`N_guys = n guys_lst = topic pairs_max_top = [bin(int(guys_lst[i],2) | int(guys_lst[j],2)).count('1') for i in range(N_guys-1) for j in range(i+1,N_guys) ] max_top=max(pairs_max_top) max_team_num=pairs_max_top.count(max_top) return [max_top,max_team_num]`

michalzalecki + 2 comments Give bitwise OR a try. It did the job for me, slowest test is #4 with 2.16s and I did it in Ruby, not is some ultra-performance lang.

mgrebenets + 2 comments How can you make bitwise OR work?

Some of test cases have 300 digit input, that's an integer that is 2^299, that's way more than 64 bit architecture integer can represent (2^63).

When you convert a 300 characters string of "0"s and "1"s into an integer, it must get truncated. I just used bitwise OR with Haskell and got all answers wrong except the 1st test case.

I'm pretty sure it should be converted to array, not integer, or probably a dynamic bitset, if you implement it yourself or there's such thing in standard library.michalzalecki + 1 comment I have function to "merge" skills and return count of 1's.

`def mergeSkills(a, b)`

`(a | b).to_s(2).count("1")`

`end`

I'm converting to binary on read.

mgrebenets + 1 comment I see. So by "binray" you mean some Python's version of (dynamic) BitSet then?

I tried using Haskell's BitSet.Dynamic but had import errors, even when using qualified imports. Looks like this package is not available for hacker rank assignment.

I ended up optimizing the code by switching from lists to arrays once again.michalzalecki + 1 comment I meant, integer form binary (given as String), sorry. In Ruby (which I'm using for this task) I have two handy methods:

String#to_i which takes base of numeral system as argument and converts String to Integer

Integer#to_s which also takes base of numeral system as argument but converts Integer to String.

And converting on read simply looks like this:

`students << gets.chomp.to_i(2)`

. It's getting a string from STDIN, removes new line (`\n`

) and`to_i(2)`

converts string to binary (i. e.`"101".to_i(2) #=> 5`

) in the end I'm pushing an integer to students array.I do converting on read because array of integers is smaller than array of string and I'm doing one convert on read instead two in

`mergeSkills`

method.mgrebenets + 1 comment OK, so Ruby must be doing magic behind the scenes. I just ran

`str.to_i(2)`

where str is a stirng with 500 0s and 1s and it converted it to an enormous integer.

`2953109070953703694574893395613555973861585638963464418084069329878799422075142253257662390793178049629115076758106380689593440952317566923506479727030`

.

Which is way over MAX INT for 64-bit architecture.

I might only assume that Haskell's direct conversion to Int doesn't work the same way as Ruby's`to_i`

method.edzvh + 0 comments Ruby and Python both allow for arbitrarily large ints which makes the problem much easier.

okyantoro + 1 comment I use C language, '0' and '1' are represented as character 1 byte each. in ascii table '0' = 48 = 0011000 and '1' = 49 = 00110001.

I use this trick, ((char1 | char 2) & 1). it will return 1 if at least one of the character is equal to '1', do it for every character in column. it really works :D.valq7711 + 2 comments Yes, it's trick ... but not nice trick at least for C-implementation! Because ('0'|'1') - single machine instruction, but (int64 | int64) - single machine instruction too! I.e. your algoritm is 64 times slower then it's possible;D. When I studied C (20 years ago), I disassembled my program and rated how nice it looks in assembler - it was very helpful

okyantoro + 0 comments here is my implementation https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/12700270. I just tried for hacker's rank testcase, does it have different behavior if I run it on different machine? :D

ghosh_saikat4000 + 0 comments How do you make it 64 times faster ? I didn't understand. Is it by writing if(char1 | char2 == '1')

SigmaSquared + 5 comments Tried it in python, got it in max 0.34s

`import itertools N,M = map(int,input().strip().split()) knowledge=[] for i in range(N): knowledge.append(int(input(),2)) mx = -float('inf') teams=0 for p1,p2 in itertools.combinations(range(N),2): combined_topics = bin(knowledge[p1]|knowledge[p2]).count('1') if (combined_topics==mx): teams+=1 elif (combined_topics>mx): mx = combined_topics teams=1 print(mx,teams,sep='\n')`

rishabh_ags + 0 comments Your code is Awesome!!

NAklecha + 0 comments I love itertools!!!

f20161841 + 0 comments what is combined_topics = bin(knowledge[p1]|knowledge[p2]).count('1')????

beckwithdylan + 0 comments [deleted]pouya_mn + 2 comments Just a litlle simpler to read and faster to run:

from collections import Counter from itertools import combinations def acmTeam(topic): c=Counter() #we could use dict, but Counter has a better name ;) for t in combinations(topic,2): c[bin(int(t[0],2) | int(t[1],2)).count('1')]+=1 winner=max(c.keys()) return winner,c[winner]

gwarks + 0 comments from itertools import combinations,izip def acmTeam(topic): x=[sum(a=='1' or b=='1' for a,b in izip(a,b)) for a,b in combinations(topic,2)] m=max(x) return m,sum(m==x for x in x)

justice_theledi + 0 comments Perfect Solution

kishancs46 + 1 comment I followed the same algo in java. Except the first input everything else is failing for me.

Loydik + 1 comment Java is just too slow of a programming language :D You should try another!

P.S. Joking ofc

CodingFrank + 0 comments I use C++, sometimes it's to long for my program. Who about python? And what language do you prefer?

klaxon + 0 comments + Have same solution. Looks like it's fine for the input size. But does anyone know if there is there better solution?

trebor13 + 0 comments I wrote a very similar program in Ruby and had the same issue. I ended up removing the inner loop, treating the (guyslist) array entries as bitmaps, doing an "or" on the two items, then counting the resultant "1"s (using a method). I'd expect you could do something similar in Python.

hmir99 + 2 comments I used almost the exact same code and also got timed out. I think the Hackerrank compilers are a bit buggy -- when I reimplemented this algorithm in Java, all the test cases passed in under a second:

`import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { //Get input Scanner s = new Scanner(System.in); String[] firstLine = s.nextLine().split(" "); int people = Integer.parseInt(firstLine[0]); int topics = Integer.parseInt(firstLine[1]); int[][] a = new int[people][topics]; for(int i = 0; i < people; i++){ int[] currentArray = new int[topics]; String currentTopicList = s.nextLine(); for(int j = 0; j < currentTopicList.length(); j++){ currentArray[j] = Integer.parseInt(currentTopicList.charAt(j) + ""); } a[i] = currentArray; } //Solve int highest = -1; int bestTeams = 0; for(int i = 0; i < a.length-1; i++){ for(int j = i+1; j < a.length; j++){ int knowledge = 0; for(int x = 0; x < topics; x++){ knowledge += (a[i][x] == 1 || a[j][x] == 1) ? 1 : 0; } if(knowledge > highest){ highest = knowledge; bestTeams = 1; } else if(knowledge == highest){ bestTeams += 1; } } } System.out.println(highest); System.out.println(bestTeams); } }`

vineetkaushik + 1 comment Passed under a second?? I have the same time complexity as you, maybe even less, but my code is getting timed out. I am using java too.

snkt_pat2 + 6 comments `#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n; int m; int max=0; cin >> n >> m; vector<string> topic(n); for(int topic_i = 0;topic_i < n;topic_i++) { cin >> topic[topic_i]; } int count = 0; for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { int topics = 0; for(int k=0;k<m;k++) { if( ((string)topic[i]).c_str()[k]=='1' || ((string)topic[j]).c_str()[k]=='1' ) topics++; } if(topics>max) { max=topics; count = 1; } else if(topics==max) count++; } } cout<<max<<endl<<count<<endl; return 0; }`

reeshabhChy + 4 comments Can you please help me with C# code. I am getting time out exception.

snkt_pat2 + 0 comments Sorry!

I have no experience in C#.

gomes_uma + 0 comments here is the c# solution but bit ugly https://www.hackerrank.com/challenges/acm-icpc-team/submissions/code/25533776

intechworx + 0 comments for (int topic_i = 0; topic_i < n; topic_i++) { topic[topic_i] = Console.ReadLine(); }

`int max = 0; List<int> matched = new List<int>(); for (int i = 0; i < n; i++) { int[] arr = Array.ConvertAll(topic[i].ToArray(), c => (int)Char.GetNumericValue(c)); for (int j = i + 1; j < n; j++) { int[] arr2 = Array.ConvertAll(topic[j].ToArray(), c => (int)Char.GetNumericValue(c)); int match = 0; for (int k = 0; k < arr.Length; k++) { if((arr[k] | arr2[k]) == 1) { match++; } } if(match > max) { max = match; } matched.Add(match); } } int max_ = matched.Max(); int cnt = matched.Where(x => x.Equals(max)).Count(); Console.WriteLine(max); Console.WriteLine(cnt); You can optimize for sure.`

lmccarthy + 0 comments If it's not too late.... I shamelessly stole adityangt's C++ and "sharpened" it. Worked first try. Here you go:

static int[] acmTeam(string[] topic) { int count = 1, max = int.MinValue; for(int i=0; i < topic.Length-1; i++){ for(int j = i+1; j < topic.Length; j++){ int temp = 0; for(int k = 0; k < topic[i].Length; k++) if(topic[i][k] == '1' || topic[j][k] == '1') temp++; if (temp > max){ max = temp; count = 1; } else if (temp == max) count++; } } int[] ar = {max, count}; return ar; }

Hari_Krishnan + 2 comments if( ((string)topic[i]).c_str()[k]=='1' || ((string)topic[j]).c_str()[k]=='1' ) Could you pls explain me what does it mean?

ranjan621 + 3 comments For simplicity we can use as a if( topic[i][k] =='1' || topic[j][k] == '1' )

naveenchopra933 + 0 comments how to use it in c language

bhavgothadiya + 0 comments Thank you brother.. it's Simpky code but Using c_str() it makes the complex Code

Power_star + 0 comments Yes it is better to use subscript than the function.If we use that function it's getting timed out

bhavgothadiya + 0 comments c_str() is Simple Function in Cpp As like in java Substr

tanuj_kapoor15 + 0 comments [deleted]positivedeist_07 + 0 comments This code gets timed out :|

bhavgothadiya + 0 comments c_str() means what???

bhavgothadiya + 0 comments Hello Brother, In your Code not all case passed Very Well Time Complexity Occur

jdfurlan + 0 comments Awesome algorithm. Really apprecaite it. I walked through it step by step and implemented. Really clever and tricky. Cudos to you!

dheerajChallenge Author + 1 comment Looks like you solved the challenge! congrats!

EliottG + 0 comments I had exactly the same problem; your biggest issues are

1) running int() twice for EVERY possible combination of strings (you should do that once per string, when you generate guyslist[]), and

2) running an extra for loop to count the individual bits (you should use bitwise OR operation, and then use str.count())

shamsheer1 + 0 comments For those not interested using a bitset they can try this instead..clears all test cases

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int topicsMax = -1; int teams = 0; int noTopics = 0; int count = 0; String topic[] = new String[n]; for(int topic_i=0; topic_i < n; topic_i++){ topic[topic_i] = in.next(); } for(int j = 0; j < n; j++) { for(int k = j + 1; k < n; k++) { count = 0; for(int i = 0; i < m; i++) { if((topic[k].charAt(i) != topic[j].charAt(i)) || (topic[k].charAt(i) == '1' && topic[j].charAt(i) == '1')) { count++; } } if(count > topicsMax) { topicsMax = count; teams = 1; } else if(count == topicsMax) { teams++; } } } System.out.println(topicsMax); System.out.println(teams); } }

artemdude + 1 comment javascript solution

var max = [0,0]; for(var i=0; i<n-1; i++){ for(var j=i+1; j<n; j++){ //check topics var sum = 0; for(var t=0; t<m; t++){ if(topic[i][t]|topic[j][t]){ sum++; } } if(sum > max[0]){ max[0] = sum; max[1] = 1; } else if(sum === max[0]){ max[1]++; } } } console.log(max[0]); console.log(max[1]);

babylee2002 + 0 comments where is n & m from?

gaggio23 + 1 comment I think the complexity of my alg was about O(2M*N^2), runs in 0,69s at most.

trendsetter37 + 1 comment What lang did you use?

gaggio23 + 0 comments I used C

anshu_mishra + 1 comment Sample java implementation using BigInteger :

`import java.math.BigInteger; import java.util.Scanner;`

public class Solution {

`public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numOfPeople = scanner.nextInt(); int numOfTopics = scanner.nextInt(); BigInteger[] familiarity = new BigInteger[numOfPeople]; int maxBitCount = 0; int maxScoreCount = 0; BigInteger score; for(int i=0; i<numOfPeople; i++) { familiarity[i] = scanner.nextBigInteger(2); } for(int i=0; i<familiarity.length-1; i++) { for(int j=i+1; j<=familiarity.length-1; j++) { score = familiarity[i].or(familiarity[j]); int bitCount = score.bitCount(); if(bitCount > maxBitCount) { maxBitCount = bitCount; maxScoreCount = 1; } else if(bitCount == maxBitCount) { maxScoreCount++; } } } System.out.println(maxBitCount); System.out.println(maxScoreCount); }`

`}`

smitparekh1995 + 0 comments Why did you use "2" in nextBigInteger(2). What is it use and how it works? I tried to read about it but I am not getting it. Please if someone can help me with this.

01argha + 2 comments Simple solution in Python3:

from itertools import combinations n,m=map(int,input().split()) strings=[] for i in range(n): strings.append(input()) combos=list(combinations(strings,2)) or_res=[] for i in combos: or_res.append(bin(int('0b' + i[0], 2) | int('0b' + i[1], 2)).count('1')) m=max(or_res) print(m) print(or_res.count(m))

Iqra77777saleem + 0 comments Not simple

ajsmith22 + 0 comments I used a very similar method for finding the number of topics a team knew, but a slightly more simplistic method for finding the maximum and number of team compositions for that number:

from itertools import combinations def acmTeam(topic): count = 0 max_ = 0 for c in combinations(topic, 2): sum_ = bin(int(c[0], 2)|int(c[1], 2)).count('1') if sum_ > max_: count = 1 max_ = sum_ elif sum_ == max_: count += 1 return (max_, count)

I think this method ends up being a bit more efficient, since you're generating a new list with the maximums, and then traversing that list twice to find the max, and then the count.

Sort 544 Discussions, By:

Please Login in order to post a comment