Parvej's blog

By Parvej, history, 13 months ago, In English

Hello. I googled the following problem but didn't find any related article.

problem: You are given a N*M size grid of integers. Initially, you are at the leftmost top cell (1,1). You can either go right or down. There are (N+M-2) C N-1 paths in the grid. What is the Longest Increasing Subsequence's length of all the paths.

let A,
{1 2 4 3 }
{2 1 3 4 }
{1 2 4 5 }

You can go take A[1][1],A[1][2],A[2][3],A[2][4],A[3][4] from the path (1,1) -> (1,2) -> (2,2) -> (2,3) -> (2,4) -> (3,4) .

so the answer is 5.

1<=N,M<=1e3

A[i][j]<=1e9;

NB: Can we print the path under the given constraints?

Full text and comments »

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

By Parvej, history, 22 months ago, In English

Today I was solving this problem.

I made two similar submissions.

Sub1 used class ( TLE ).

Sub2 exact same code without class ( AC ).

I can't understand why making the functions and variables as class's member consuming so much time?

I have googled but didn't find anything written about it.

Full text and comments »

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

By Parvej, history, 2 years ago, In English

While solving this problem 1359C - Смешиваем воду . I observed a strange thing.

The same code is giving different outputs on different compilers. WA- 146913145 AC- 146915566

I found the test case for which the compilers gave different outputs.

Test Case

for this test case, c++17(64bit) is giving 499979 as output. but c++17 is giving 499981 as output which is as same as correct output.

I want to say that my outputs are compared to the outputs of the authors' solution which was run on c++17. But my solutions should be compared to the outputs which were run on c++17(64bit).

Full text and comments »

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

By Parvej, history, 2 years ago, In English

I got a runtime error on the last Atcoder Regular Contest.

The problem is this .

My RE solution here .

Runtime Error Part
RE test case

I always wrote (char) ('a'+k)to get the kth letter from the alphabet and didn't get Runtime Error on any platform.

Why am I getting RE this time?

Full text and comments »

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

By Parvej, history, 3 years ago, In English

We know that a tree has either 1 or 2 centroids. I can find one centroid using simple dfs.

But, if a tree has 2 centroids, Is there a way to efficiently find the other one?

In case you don't know about centroids of a tree. See here

Full text and comments »

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

By Parvej, history, 3 years ago, In English

How can I find all the simple cycles in an undirected graph?

126615260_419079712777006_8560932289449234104_n.png In the picture, there are 3 simple cycle:

  1. 1-2-3

  2. 1-2-4-5

  3. 1-3-2-4-5

How can I print all of them?

Full text and comments »

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

By Parvej, history, 4 years ago, In English

In this problem 1008C - Reorder the Array

I used upper_bound(multiset.begin(),multiset.end(),x) and got TLE.

TLE Sub: 77006832

But when I used multiset.upper_bound(x), I got accepted!

AC Sub:77081261

Can anyone explain to me why inbuilt upper_bound() is slower than the member upper_bound() function of std::multiset?

Full text and comments »

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