Peregrine_Falcon's blog

By Peregrine_Falcon, history, 5 weeks ago, In English,

I just learned Ford-Fulkerson Algorithm for Maximum Flow Problem with BFS/DFS. I solved one problem from lightoj.com.

But I couldn't find any basic problem to practice the basic algorithm.

If someone can provide me some very basic problem, by practicing them I'll get used to the basic concept & coding also learn something I'll be really very grateful. I've some problems but those are not basic.

Thank You.

Read more »

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

By Peregrine_Falcon, history, 7 weeks ago, In English,

I was trying to solve this problem. With this code I got several WA & wasted hours of time by debugging it. But I've changed to this got AC! With no change of idea. All I changed was a line of code O_o.

it = lower_bound( v.begin() , v.end() , com [ i ].size() );

to

a = com [ i ].size();

it = lower_bound( v.begin() , v.end() , a );

Is there any problem with that?

Thank You.

Read more »

 
 
 
 

By Peregrine_Falcon, history, 7 months ago, In English,

In this problem I used set < pair < int , int > > st;

auto it = lower_bound( st.begin(), st.end(), make_pair( a + d + 1 , 0 ) )

But it costs me several TLE. But when I look over the tutorial solution, I saw this-

it = st.lower_bound( make_pair( a + d + 1 , 0 ) );

I used it, & got AC.

But I don't understand what's the difference? If anyone can please help. TLE Submission AC Submission Thank You O_o

Read more »

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

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

In G++17 7.3.0. I've tried to use struct in the following way. But it shows me compilation Error. I've tried in Custom test . In this AC Code I just added struct, but this shows me compilation error.But here with G++14, It's running very well.

Read more »

 
 
 
 

By Peregrine_Falcon, 10 months ago, In English,

Problem Link

My code link

My idea:

*I made a graph providing connection to every node to all other nodes.

*Distance = sqrt( (x1 — x2 )^2 + ( y1 — y2 )^2 )

*Ran MST( Minimum Spanning Tree ) & saved the summation of costs.

*Made a graph from the MST.

*Made a Sparse Table using the MST graph & also saved the weight of maximum weighted edge for the paths.

*Then I tried to make a magical road between every possible node & searched for possible maximum ( A/B ) value, for delete a edge, I took help of the LCA for finding the maximum weighted edge between the path of currently two working nodes.

***I've been trying this problem for several days, but can't find any problem. Please help If anyone have free time.

Thanks in advance.

UPDATE: Got Accepted. { The Mistake was in Minimum Spanning Tree. Thank you. }

Read more »

 
 
 
 

By Peregrine_Falcon, history, 13 months ago, In English,

Convert Infix to Postfix Notation

Initially we’ve a string S which represent the expression in infix format. Now we need a character stack.

*We’ll iterate through the string S, from left to right.

  • Whenever we encounter an operand we’ll print it.

  • If we encounter an ‘(‘ we’ll push it to the stack.

  • If we encounter an ‘)’ we’ll take the following actions:

    1. We’ll continue to pop top of the stack until we find the ’(‘
    2. Before we pop top of the stack, we’ll print every character of top of the stack except ‘)’.
  • If we encounter an operator, we’ll take the following actions:

    1. We’ll continue to pop top of the stack until we find that S[ i ] is greater than the top of the Stack (by the rules of precedence) Ex: if we found an Multiplication operator on S [ i ] We’ll continue searching for addition or subtraction operator on top of the stack. We’ll stop searching until it’s empty or we’ve found one. Before that we’ll pop top of the Stack. And before pop, we’ll print every operators.
  • When the traversal will finished, we’ll continue to pop top of the stack until it's empty, and before pop we’ll print every operators.

You can see my Code

Convert Infix to Prefix Notation

To convert an infix to Prefix, first we’ve to know how to convert Infix to postfix notation.

Initially we’ve a string S which represent the expression in infix format.

  • Reverse the string S. After reversing A+B*C will become C*B+A. Note while reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘.

  • Obtain the postfix expression of the modified string S. We’ve to handle the ‘(‘ as ‘)’ and ‘)’ as ‘(‘

  • Just reverse the postfix expression we’ve.

You can see my Code

If you want to know in details about Infix, Postfix and Prefix This Link maybe help you.

Here are some basic practice problems: WhatFix Notation Equation Convert the Expression

Thank you for reading. If there anything else, please let me know.

Read more »

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