rumman_sust's blog

By rumman_sust, history, 8 years ago, In English

Recently I've read about rotating calipers technique and it's applications from wikipedia. I wonder if there is any articles or blogs from where I can learn more about rotating calipers. I understand convexhull technique . I've searched at codeforces but couldn't find any valuable resources or blog posts. If you guys have any valuable resources on this topic please share. It'll be great if someone writes a blog about this topic at codeforces. Also we can discuss about problems related to rotating calipers here. Thanks for reading :)

UPD: I just solved Robert Hood from Kattis online judge. After spending almost a week I've understood the process of rotating calipers. It feels really great to learn a new problem solving technique. I recommend everyone to read this book and visit this site (provided by SuprDewd) for umderstanding rotating calipers technique. Here you can find a basic implementation of rotating calipers for finding diameter of a convex polygon. Also don't forget to look at SuprDewd's comment. Thank you all for helping and encouraging me all the time :)

Full text and comments »

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

By rumman_sust, history, 9 years ago, In English

Recently our team has practiced Tehran Regional contest 2014. We solved 7 problems. But I want to discuss some problems we couldn't solve. Problem E Antennas (Uva Live 7016) and Problem I Robot Race (Uva live 7020). You can discuss about those problems here if you want :)

Best regards.

Full text and comments »

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

By rumman_sust, history, 9 years ago, In English

I've found an interesting problem in hackerrank. But couldn't solve it. I've tried so many ways, but no one can pass the time limit. That's why I've decided to seek some help from you guys :) Here is the problem link. If anyone have an idea to solve it, please share your thoughts :)

UPD: Solved it with mo's algorithm + binary index tree. Thanks for the hint mkirsche :)

Full text and comments »

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

By rumman_sust, 10 years ago, In English

Recently in a national contest I've found an interesting problem. Given an array of N elements and Q queries with a range . You've to find how many numbers have the highest frequency in that range? That means if the maximum frequency is , then how many numbers have in that range?

Let's call the i'th element of the array is and for each query the range is .

I can't find any feasible solution. I think this problem can be solved using Square Root RMQ with complexity per query. But couldn't find a way. How to solve this type of problem with RMQ? Any idea or hints?

UPD: Mo's algorithm is really cool :D

Full text and comments »

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

By rumman_sust, 10 years ago, In English

If we want to know a variable's type id or compare two variables' type ids are same or not, here is a keyword "typeid" in C++.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int intvar;
    long long longlongvar;
    bool boolvar;

    cout<<"Type name of int: "<<typeid(int).name()<<"\n";
    cout<<"Type name of intvar: "<<typeid(intvar).name()<<"\n\n";
    cout<<"Type name of long long: "<<typeid(long long).name()<<"\n";
    cout<<"Type name of longlongvar: "<<typeid(longlongvar).name()<<"\n\n";
    cout<<"Type name of bool: "<<typeid(bool).name()<<"\n";
    cout<<"Type name of boolvar: "<<typeid(boolvar).name()<<"\n\n";

    return 0;
}

This code shows:

Type name of int: i
Type name of intvar: i

Type name of long long: x
Type name of longlongvar: x

Type name of bool: b
Type name of boolvar: b

"i" for integer, "x" for long long and "b" for bool.

Full text and comments »

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

By rumman_sust, 10 years ago, In English

How can I find the minimum cost max-flow in a graph where the capacity of an edge have a lower and upper bound (UPD: Edge have a capacity within a range [l,r])?

UPD: FLOW (not capacity) of an edge have a lower and upper bound

Full text and comments »

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

By rumman_sust, 10 years ago, In English

I recently heard about plug dp (I don't know what it means). When I tried to solve this problem, I read some Chinese blog where they mentioned plug dp. Can any one inform me about plug dp or how to solve this problem? Thanks in advance. :)

Full text and comments »

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

By rumman_sust, 11 years ago, In English

I want to know about monotonous queue. I google it, but found nothing(may be i'm not good at searching!). :( Can any one describe it or give me some idea and information about it? It will be really appreciable. Thanks in advance. :)

Full text and comments »

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

By rumman_sust, 11 years ago, In English

I am trying to solve this problem so many times but I can't figure out how to solve this within 2.00 second(Time limit). I really need help cause I am being frustrated about this problem.

Problem summary : Given an array find the smallest sub-array whose summation is greater or equal than X and output the length of the smallest sub-array.

1 <= Array size <= 500000, -10^9 <= A[i] <= 10^9 and -10^9 <= X <= 10^9.

Can any one give me some hints about how to solve this type of problem less than O(n^2) complexity and within 2.00 second(Time limit).

problem link

Thanks in advance. :)

Full text and comments »

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