Hafiz_'s blog

By Hafiz_, history, 8 days ago, In English

Problem: https://codeforces.com/contest/978/problem/F

Solution 1(TLE): https://codeforces.com/contest/978/submission/98839909

Solution 2(AC): https://codeforces.com/contest/978/submission/98859922

Here, in solution 1, I used 3 unordered map and getting TLE but when I used 2 unordered map on solution 2 it gets AC. Why this happened while unordered map searches, inserts, and deletes elements in O(1)?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Hafiz_, history, 2 months ago, In English

Problem statement: A little girl whose name is Anne Spetring likes to play the following game. She draws a circle on paper. Then she draws another one and connects it to the first cicrle by a line. Then she draws another and connects it to one of the first two circles by a line. She continues this way until she has n circles drawn and each one connected to one of the previously drawn circles. Her circles never intersect and lines never cross. Finally, she numbers the circles from 1 to n in some random order.

How many different pictures can she draw that contain exactly n circles? Two pictures are different if one of them has a line connecting circle number i to circle number j, and the other picture does not.

INPUT: The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing n (0 < n ≤ 100).

OUTPUT: For each test case, output one line containing ‘Case #x:’ followed by X, where X is the remainder after dividing the answer by 2000000011.

My logic: example: n=3, then 1-2-3, 1-3-2, 2-1-3 ('-' means line connecting circles) these 3 different pictures can be drawn. According to my observation, for n=4, it will be 12 different pictures. This way I find that answer will be (n!/2)%2000000011;

I want to know, why my logic is not correct(got WA), what is the formula to solve this problem and why it will work?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Hafiz_, history, 5 months ago, In English

Today I puzzled to find out the value of log2((2^59)-1). Here, (2^59)-1 = 576460752303423487. We know that the value of log2(4)=2, log2(3)=1.58496 and log2(576460752303423488)=59 but why log2(576460752303423487)=59 when log2(x)=y and x=2^y. This happens not only for (2^59)-1 but also for other values.

(I searched about it on google but couldn't find out the reason behind this.) Sorry for poor English:)

Read more »

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

By Hafiz_, history, 7 months ago, In English

Problem link : lightoj 1028

My solution : link

AC solution : link

Here my approach was to find number of divisors by doing prime factorization. I used sieve.. algo to find prime up to 10^6 and this ac solution approach also almost same as my solution but my solution gets TLE.

Time limits for the question : 2s

My solution takes 2.286s and the ac solution above takes only 0.359s.

My question is, how this big change happened?(though both solutions are almost same.)

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it