_Muhammad's blog

By _Muhammad, history, 3 months ago, In English,

Assalamualikum!

For finding eular cycle we need to erase edges from graph. But I don't know how to erase edges in O(1) for undirected graph. I can only erase edges in O(log(n)) using C++ set for adjacency list instead of vector.

But I need to erase edges in O(1) so that my eular cycle finding algorithm will run in O(N) instead of O(Nlog(N)). Please tell me how to do it.

Thanks In Advance.

Read more »

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

By _Muhammad, history, 5 months ago, In English,

For 1149D - Abandoning Roads I implemented this code using a priority queue. This is tutorials logic. And took 639ms.

But when I implemented same logic using a single normal queue it took 280ms. ( My code ).

Can any one tell me why without priority queue Dijkstra working much faster. Please help me to understand the complexity for 2nd code ( without priority queue ) . I understood the complexity of the 1st code ( with priority queue ).

Read more »

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

By _Muhammad, history, 8 months ago, In English,

What is stack technique in dynamic programming and how can I apply it to solve 1131G - Most Dangerous Shark. I can implement the dynamic programming solution of that problem which is mentioned in the editorial( and I know there is a typo ) but it will get TLE. And I don't know about stack technique to take minimum of dp state in a range. So someone please explain it or give me some useful links.

Thanks in advanced :)

Read more »

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

By _Muhammad, history, 9 months ago, In English,

In this problem I am trying to find maximum X1 + X2. Lets X is the Xor of all given numbers. I assumed each number as a vector and then found the basis.Let see an example :

5 = 1 0 1

6 = 1 1 0

7 = 1 1 1

After using Gaussian elimination the basis are :

1 0 0

0 1 0

0 0 1

And then I iterated from most significant bit and If there is 0 in i -th bit of X then I tried to put 1 in X1. If it is not possible then I skipped that bit and went to next bit. But this process is not giving me maximum X1+X2. Here is the Implementation. Please can anyone tell me what is wrong here.Is my logic is wrong?? Or the Implementation is not prefect?

Please help me.I am stucked here.

Read more »

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

By _Muhammad, history, 9 months ago, In English,

I have learnt Gaussian algorithm recently. I am stacked in 251D - Two Sets.

I have read the editorial of this problem. I can find the max value of X1+X2. But in case of tie. I am not getting how to check is it good to give 0 in i-th bit of X1 when i-th bit of X is 1 and also not understanding how give 0 in i-th bit. I have saw some Ac code but I am not getting what they have done. So please can any one tell me how can I do it.

Thanks in advance. :)

Read more »

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

By _Muhammad, history, 9 months ago, In English,

After applying Gaussian algorithm on a array how could I restore those numbers of which XOR is maximum?

Let a[3] = {11, 5, 9} If I apply Gaussian algorithm we will find maximum xor is 14.And used numbers are 11, 5.How to restore this 11, 5?

Read more »

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

By _Muhammad, history, 10 months ago, In English,

I can convert some simple recurrence relation to a mathematical formula.

Example: F(n) = n + F(n-1), if n > 0 and F(0) = 0; This recurrence relation can be converted into the formula: F(n) = (n*(n+1))/2

But for many other recurrence relations I am unable to do so.
Example: Lets consider the fibonacci sequence. F(n) = F(n-1) + F(n-2), if n > 1 and F(0) = 0, F(1) = 1; I tried hard to convert this recurrence relation to a formula, but failed.

So, my question is it actually possible to convert every recurrence relation to a O(1) formula? If not, then how do I determine that the recurrence relation does not have an implicit formula? If yes, then is there any rule of thumb for converting?

Read more »

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

By _Muhammad, history, 10 months ago, In English,

In Sha ALLAH ( If ALLAH wants ) I am going to give contest on ladder problems and timus.If anyone interested can join me.I will give 5 hour contest where there will be 3 questions from ladder and 2 from timus. Sometimes there will be 1 question from lightoj.

From timus I will sort questions by author and choose problems from 1411 till end.And from ladder I will choose questions from 17 — 1800 <= Codeforces Rating <= 1899 ladder to end.

All the problems I will choose which I haven't solved yet.There will be 5 contest per week.

If anyone interested can join me.So that their will be competition and we won't waste time.And we will upsolve together and will discuss solutions also.

1st contest will held tomorrow : link .

My ladder id : shahriarcsecu333

My timus id : Muhammad Shahriar Alam

Read more »

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

By _Muhammad, history, 12 months ago, In English,

There is a long queue more then 1hour 30 minutes in codeforces status.Please fixed it.

Read more »

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

By _Muhammad, history, 15 months ago, In English,
bitset < n > b1, b2;
b1 |= b2;

Is the complexity of above code O(n)? Or it works in O(1).

Read more »

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

By _Muhammad, history, 18 months ago, In English,

My code getting TLE in sgu 112 problem. I am new to java programming so I am not understanding why my code is getting TLE. I also have submitted 3 code from github for this problem. They also got TLE. Now what should I do? Question link : http://codeforces.com/problemsets/acmsguru/problem/99999/112

My code :

//In the name of ALLAH

//package OverRiding;

import java.math.BigInteger;
import java.util.Scanner;

public class Example1 {

    public static void main(String[]args) {


        Scanner cin = new Scanner( System.in );

        BigInteger bigA = cin.nextBigInteger();
        BigInteger bigB = cin.nextBigInteger();
        BigInteger aPowb, bPowa;
        aPowb = bigA.pow ( bigB.intValue() );
        bPowa = bigB.pow ( bigA.intValue() );

        BigInteger ans = aPowb.subtract ( bPowa );
        System.out.println(ans);


    }
}

Read more »

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

By _Muhammad, history, 18 months ago, In English,

a2oj.com is not working. It's showing error. Can anyone tell me why?

Read more »

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

By _Muhammad, history, 22 months ago, In English,

Please give me some tutorial on dp where basic to advance topic has discussed with problem link.Problems will be more welcomed then theory.

Thanks in advance:)

Read more »

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

By _Muhammad, history, 23 months ago, In English,

I have solved 269 problems in codeforeces and 82 problems in light oj.But still I am Newbie.My rating in code chef is 1454 (attended 5 contest).But codeforece rating is getting down day by day.What should I do now?How to choose questions to improve my coding skill + rating?

Thanks in advance.

Read more »

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

By _Muhammad, history, 2 years ago, In English,

Topic : Bit mask.

Why getting wa in this test cases :

2

16 12

F853AD64B1EC7290

16 18

8192BEFA70CD3564

Correct Output :

Case 1: 5230697472000

Case 2: 3486618432000

My output :

Case 1: 2324797191360

Case 2: 1226335446000

Question : http://lightoj.com/volume_showproblem.php?problem=1021

My code: https://ideone.com/2XjGaV

Read more »

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

By _Muhammad, history, 2 years ago, In English,

Topic : LCS My code is getting TLE for this test case: 1 weuwmwxxeajlsalokh dmnmklyoltvdpjzbkqe

How to solve this problem?

Question: http://lightoj.com/volume_showproblem.php?problem=1110

My code: https://ideone.com/WrNYdg

Read more »

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

By _Muhammad, history, 2 years ago, In English,

What is upsolving realy means? Is it means solving all problem of that contest that I havn't solved.Or it means solving those problems that I can solve but didn't solved in the contest.

Read more »

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

By _Muhammad, history, 2 years ago, In English,

Is A2 oj really helpful to improve my rating in codeforces ? And when practicing in codeforces how to choose difficulty level of question as a newbie or pupil ? Note : I can solve div-2 A easily but div-2 B is hard to me and I can't solve div-2 C with out reading editorial (But I have to spend huge time to understand the editorial of C ). Thanks in advance. : )

Read more »

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

By _Muhammad, history, 2 years ago, In English,

How much time I should spend to solve a problem before reading the editorial.Please give me a perfect advice so that I can save myself from wasting time.

Read more »

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

By _Muhammad, history, 2 years ago, In English,

If I don't understand the tutorial, is it wise to see some red coder's code or the code given in tutorial to under stand the tutorial perfectly.

Some time codes seems to me more easier to understand than tutorials. Please help. :)

Read more »

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