rudra101's blog

By rudra101, history, 4 years ago, In English,

I recently read this Quora post about Bogosort which tries to sort a list using the following algorithm:

  1. Put the elements of the list in a random order.
  2. If the list is sorted, finish. Otherwise go to Step 1.

It has an average running time equal to O((n+1)!). And, it may run forever.

Can someone share more algorithms which became famous due to their dumbness?

Read more »

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

By rudra101, 6 years ago, In English,

Hi there! I have a doubt. It will be nice if you help me.

When I open some older problems in the problemset, I see a blue section on right, titled "Attention". Here is what, that's written on it:

"**Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, than value 800 ms will be displayed and used to determine the verdict.** "

As I am new to programming and related stuffs, I couldn't understand what is meant by 'package' or how it can affect the execution time of programs written in various languages. Also, I don't know how solutions are judged by a tester.

Waiting for answers ! :)

Read more »

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

By rudra101, 6 years ago, In English,

This problem (270B - Multithreading) is a bit tricky to understand. Here's what's happening. Suppose there are 5 threads. There position were 1,2,3,4,5 before refreshing. Suppose the thread '2' just had a new message, so, after refresh it will move to the top of the list. So, the new position of threads will be 2,1,3,4,5. After that if thread 3 had a new message, then the resulting position of threads after refresh will be 3,2,1,4,5. Thus, if we analyze closely, we have to a find the number of elements which are not in strictly decreasing order (as traversed from the end of the array)! I implemented it using std::stack and it got accepted, clocking at 62 ms.

Read more »

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