ghoshsai5000's blog

By ghoshsai5000, 13 months ago, In English
  • This is to announce a contest on DMOJ
  • Contest Link
  • The contest can be taken at any $$$3$$$ hour window of your choice starting from 00:30 IST 1st November, 2019 over $$$2$$$ days
  • The contest will be full-feedback
  • The contest will consist of $$$6$$$ problems
  • The problems are set by wleung_bvg, Zeyu and Pookmeister

UPDATE — Contest is live

Read more »

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

By ghoshsai5000, 13 months ago, In English

I have always been an admirer of the problems of Timus. However, it has always fallen back on my priority list due to the lack of contests. I was quite delighted to find out that Timus is finally conducting a contest again. I am announcing it here to increase awareness and so that it serves as a reminder.

Best of Luck and let us discuss problems here after the contest !

UPDATE — The Contest is tomorrow !

Read more »

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

By ghoshsai5000, 14 months ago, In English

I recently stumbled upon the website DMOJ by accident and I could hardly find any posts about the website and so decided to make this thread to give it some publicity to the DMOPC'19 October Contest which will be conducted tomorrow.

As far as I can tell, the problem writers are thebes, KevinWan and Linus123 (little_prince on DMOJ. Thanks to Kevin for informing me.)

Some facts about the contest

  • It is full feedback. There are no pretests or system tests.
  • There will be 6 questions plus an extra question for beginners
  • The duration of the contest is 3 hours and can be taken at any 3 hour slot over a period of 48 hours starting from 12th Oct 00:00 EDT

And yes, it is rated ;)

The contest will be conducted at

Let us discuss the questions here after the contest is over on 15th October.

Read more »

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

By ghoshsai5000, history, 3 years ago, In English

I found the question Cave Paintings quite interesting.

So, I wrote an editorial about it on Quora here.

Read more »

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

By ghoshsai5000, history, 3 years ago, In English

So, I adopted two different approaches to the problem T-Primes ...

In the first solution, I maintained a set of all squares of Primes ... So, the complexity should be O(D log log D + N log S),

Where D = 1e6, N is the number of queries and S is the size of the set ... Each query on a set takes O(log S) time at most because it is a balanced tree.

In the second solution, I only maintained a vector of primes and checked if a number is a square root and if the square root is prime.

Here the solution is O(D log log D + T), where T is the complexity of finding square root of T ... I am unable to analyse ...

I know finding N^2 is easier than finding root(N) ... Can someone explain why one solution is better than the other ?

Help in understanding the complexities of the solutions would be much appreciated !

Read more »

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

By ghoshsai5000, history, 3 years ago, In English

Here is the link for the problem with CodeChef problem Carvans.

Here's my solution. ... I am unable to find any bugs. Please help me debug it and tell me what is wrong with it.

#include <stdio.h>
#include <algorithm>

using namespace std;

void solve()
{
    int previous_car_speed = 1e9, current_car_speed, number_of_cars, current_car_max_speed;;
    scanf("%d", &number_of_cars);

   int no_of_cars_at_max_speed = 0;
    for(int i = 1; i <= number_of_cars; i++)
   {
        scanf("%d", &current_car_max_speed);

        current_car_speed = min(previous_car_speed, current_car_max_speed);

        no_of_cars_at_max_speed += (current_car_speed == current_car_max_speed);

        previous_car_speed = current_car_speed;
   }

   printf("%d\n", no_of_cars_at_max_speed);
}

 int main()
 {
    int no_of_test_cases;
    scanf("%d", &no_of_test_cases);

    while(no_of_test_cases--)
        solve();

    return 0;
}

Read more »

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

By ghoshsai5000, history, 4 years ago, In English

I have been trying to solve this Hacker Earth problem and it is reduced to finding the Fibonacci numbers. However, I am getting wrong answers for big values.

Here is my code. Can someone tell me what is wrong ?

Read more »

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

By ghoshsai5000, history, 4 years ago, In English

I have tried to solve the problem of finding k-interesting pairs [here].(http://codeforces.com/contest/769/submission/26220768)

My solution is quadratic O(n^2). If it is run on the sequence of numbers given, then n = 10^5 at most. I have followed the trick of the editorial and built an array of the frequencies of each element. This happens in O(n) time, with n = 10^5, at most

And have then applied the quadratic time algorithm on the frequency array so now n = 10^4. However, this isn't enough to get past the time limit.

What are further optimizations I can perform ?

Edit — I have performed some optimizations and managed to get an acceptance. Please tell me how I can make this faster ? I am not able to understand the algorithm some other people who got faster solution used. Some stored only those values of x, for which Population Count[x] is k and then did something I am unable to understand. For example, programs like this one.

Here's my code. Please help me.

Also, one more question — The same program seems to be performing at 78 ms here and at 93 ms here. What is the reason for the difference ? This may help me understand and speeden things up.

Read more »

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

By ghoshsai5000, history, 4 years ago, In English

I have tried to solve The Table Tennis Question but I got the following mistake.

When k = 666666, a= 6666666, b= 666665

The answer is -1. But, I don't understand why the answer isn't 10. The given configuration is reachable if one player wins ten sets and scores 6666660 and then 6 more points while his opponent scores that many points. Why is the answer -1 in this case ?

Thanks.

Read more »

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

By ghoshsai5000, history, 4 years ago, In English

I am getting a runtime error for this program here. I have tried for many days but have been unable to detect the cause of the error. Please help me.

Read more »

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

By ghoshsai5000, history, 4 years ago, In English

I did my first dynamic programming problem successfully today here The editorial says that it can be solved int (log n) time with binary exponentiation of a 2x2 matrix. Can someone tell me how to convert a dynamic programming problem into a binary exponentiation problem ?

I don't want code. I want to practice the coding and implementation part myself. I want to know how to get the matrix from the recursive equations.

Let f(X, n) represent the number of paths ending in D with n moves left if the ant is at vertex X.

Then, f(D, 0) = 1, f(A/B/C, 0) = 0

Also, f(D, n) = 3f(A/B/C, n-1) f(A/B/C, n) = f(D, n-1) + 2f(A/B/C, n — 1)

How can I convert these equations into a matrix which needs to be exponentiated ?

Read more »

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

By ghoshsai5000, history, 4 years ago, In English

I have been solving this problem and here's my code and my test cases — http://codeforces.com/contest/717/submission/25885501

I got a Time Limit Exceeded. And I'm not sure if it's because of the logic (because the processing is O(n^2) ) or if it's because the input is taking a lot of time. Can someone suggest ways on speedening up the code so that I don't get a TLE ?

Thanks

Read more »

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

By ghoshsai5000, history, 4 years ago, In English

I was working on the problem Anton and Chess, and I have noticed that the entire output never gets read. Here is the code which deals with input — The input loop doesn't run as many times as it's supposed to and always takes one input less. This problem disappears if the character input line is removed.

#include <stdio.h>
#include <stdlib.h>

void get_piece_coordinates(char *, long *, long *, unsigned int);

int main()
{

        unsigned int no_of_black_pieces;
        long king_x_coordinate, king_y_coordinate;

         scanf("%u", &no_of_black_pieces);
         scanf("%lu %lu",&king_x_coordinate, &king_y_coordinate);

         long *x_coordinate = malloc(no_of_black_pieces*sizeof(long));
        long *y_coordinate= malloc(no_of_black_pieces*sizeof(long));
       char *piece= malloc(no_of_black_pieces *sizeof(char));

        get_piece_coordinates(piece, x_coordinate,y_coordinate,no_of_black_pieces);

       free(piece);
       free(x_coordinate);
       free(y_coordinate);
       return 0;
  }

  void get_piece_coordinates(char *piece, long *x_coordinate, long *y_coordinate, unsigned int no_of_black_pieces)
 {
      unsigned int i;

       for(i = 0; i < no_of_black_pieces ; i++)
      {

            scanf("%c",(piece + i));
             scanf("%lu %lu", (x_coordinate + i), (y_coordinate+ i));
       }
  }

Read more »

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