I would like to know how this Solution for Biclique passed May cookoff

general
3

Haha this is awesome. So now that it’s come to this, I’d like to ask, “How far do you plan to fall Codechef? Any intentions of getting back up?”. Earlier I used to only do Codechef contests, and when my friend would tell me, “Hey, there’s a codeforces round today!” I’d tell them, “I only do Codechef”. But now, when sometimes I retrospect, I feel like I was such an idiot.

7 Likes
4

Haha, this one made my day…:joy::joy:

1 Like
5

This guy got +199…amazing

6

Of course he is a god , can you even fathom the logic used by god like coders ? !

7

wanna see some more magic??
copy paste the same solution and try to submit it :rofl::rofl:

5 Likes
8

Codechef is a great OJ . Same code different result :laughing::laughing::laughing:

3 Likes
9

My new strategy for Codechef Contests : - If not able to reach a solution for a problem, just write some buggy code and submit!
Who knows I might get AC!:rofl::rofl::rofl::rofl::rofl::rofl:

4 Likes
10

Hahaha that might happen… :stuck_out_tongue:
Only in short contests though :stuck_out_tongue_closed_eyes:

2 Likes
11

:thinking::thinking::thinking::thinking::thinking::thinking::thinking::thinking:
…
…

12

I wonder how this solution go ac. Isn’t it a O(n3) ???

13

Maybe loops breaks earlier

14

So jaa bhai… Muje gn bolke Codechef pe qns karraha hai…
Dhokha bhai…
Dhokha ho gya​:grin::grin::grin:

15

Aur sab badhiya bhai??

1 Like
16

Sab badhiya :slight_smile: …

1 Like
17

I don’t see this in worst case, coz ‘&’ is sure to take O(n) time.

1 Like
18

:joy::joy: kaha cc Kiya !!
…

1 Like
19

Gn bola aapne. Fir aap Codechef pe chLe gaye sone. Bohot badhiya😂

2 Likes
20

This is fine, I guess. See that bitset takes only 2000 bits. So Its faster than an integer array of same size. Almost all top ranked coders in the contest have used bitset with O(n^3) code. If you see in bytes, it’s just of 250 bytes. So a bitset of size 2000 is almost as much as an array of size 250. And bitwise AND of a bitset is really faster.

21

That’s strange !!! I thought stackoverflow gives the correct explaination. I still wonder,if the time complexity isn’t n^3, what is it then ?

update : I think something is fishy here. The size is small because bitset is built in such a way that its representation takes less memory than same sized boolean array, but that doesn’t shorten its length. i.e. it still needs O(n) iterations for logical & .

1 Like
22

If you read the answer carefully, whatever i said still holds.
The complexity is still O(n^3) but bitset uses compile time optimizations. So instead of doing n operations it does some n/64 operations for each bitwise operation like OR, XOR etc. Here value of n was 2000 only. So in that solution total number of operations performed would be (2000 \times 2001)/2 \times (2000/64) \approx 6.25 \times 10^7 that might be a reason. But still time complexity would be O(n^3) only.
And if you read some posts about bitset on codeforces, it is much more faster than expected.