omggg's blog

By omggg, 4 years ago, In English

Problem 21D - Traveling Graph

How would we solve the problem if it was compulsory to visit some given edges at least once and optional to visit others ???

Any approach / solution / code is much appreciated.

Thanks a lot :)

Full text and comments »

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

By omggg, 4 years ago, In English

Given array and m. Find the index i such that A[i]%m is maximum. What is the best method to do that if I have incoming queries of m.

Any help is much appreciated, thanks :)

Full text and comments »

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

By omggg, 4 years ago, In English

Here is the reference problem

What If I have upto N numbers instead of 0 and 1 only and I want to group all of them separately?

Eg. [1,2,3,2,1,4,3] — > [1,1,3,3,2,2,4]

How to solve this for minimum swaps ?

Any help is much appreciated, THanks :)

Full text and comments »

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

By omggg, history, 4 years ago, In English

Dynamic Connectivity Contest

All accepted solutions are hidden. Why is that so?

Full text and comments »

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

By omggg, 4 years ago, In English

Take L to R on number line of positive integers (no array given), find the minimum number of numbers you need from this range to get their XOR = K, else print -1. L,R,K are given in queries.

Constraint : R-L <=10^6

Any approach is much appreciated :) THAnks alot

Full text and comments »

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

By omggg, history, 4 years ago, In English

Does Codeforces Online Judge allow us to use Boost Library for C++ ?

It would help and ease the issue of big integers...

Or what is the alternative for that ? Obviously I can handle using mod at times...but any other easy alternative?

Any suggestion is much appreciated :)

Thanks :)

Full text and comments »

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

By omggg, 4 years ago, In English

Ques : Find number of inversion counts in Range [L,R] for Q queries. ****

Array Size <=1000 ; Each integer from 1 to n occurs exactly once in this array.

Queries<= 100000

What is the best method you can suggest? Any help is much appreciated.

Thanks :)

Full text and comments »

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

By omggg, history, 5 years ago, In English

I know the B.S and basic implementation of Ternary Search. But i don't know where to apply T.S ? When B.S fails... how do think that T.S would work?

For Eg: Problem : 439D - Devu and his Brother , Submission(T.S) : 6814294

Any help is Much Appreciated.

Thanks:)

Full text and comments »

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

By omggg, 5 years ago, In English

I want to use hash table of key : vector and value : int How can i use that ? Map<vector< int >,int> uses extra logn factor which many a times doesn't suite me and gives TLE. I just want to store frequency of a kind of vector.

Any help is appreciated. Thanks.

Full text and comments »

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

By omggg, history, 5 years ago, In English

In many questions i feel if i am able to get primes upto 10^9, i can solve the problem but how do i do that?

I know Sieve upto 10^6. I know Segmented Sieve for U-L. But still i cant get primes upto 10^9. Please give me some idea. Any help will be much appreciated. Thanks a lot"

Full text and comments »

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

By omggg, 5 years ago, In English

For all those who want to start off with a topic and looking to get with some easy questions for the beginning, you can find them here.

Full text and comments »

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

By omggg, history, 5 years ago, In English

There's no tag for Trie Data Structure in problemset. Can you tell me a few questions on Trie please? Beginner to Intermediate level. Any help will be appreciated. Thanks in advance:)

Full text and comments »

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

By omggg, history, 5 years ago, In English

For questions like: (Rat in a maze) In 2-d matrix, given starting point and destination point.. with some points blocked or something, you have to calculate number of paths to reach destination ( given 4 types of moves)... Can I apply DP with it? Memorizing the state Dp[x][y], and using it if i visit that node again??

When i backtrack, how do i un-visit that node and alter DP table with that?

For Eg: 540C - Ice Cave or 374C - Inna and Dima

Any help will be much appreciated. Thanks a lot :)

Full text and comments »

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

By omggg, history, 5 years ago, In English

Question : https://codeforces.net/contest/1183/problem/E

I want to know how it can be done using 1.Graphs 2.Dynamic Programming

Also there is a harder version of the problem. [problem:https://codeforces.net/contest/1183/problem/H] What changes do i need to make for this in my approach?

P.S my rating is 1600. Any help is appreciated Thanks

Full text and comments »

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

By omggg, history, 5 years ago, In English

I am facing issues in questions in which Given is a tree with no fixed root, n<=1e5 . I can simply do the question if i traverse the tree for each node as root (n^2) but it gives TLE. I know i have to apply DP and rerooting concept.

Can anyone provide me a blog for this particular topic? Or some handful questions on that to learn with the topic? (my rating:1600)

Any help is appreciated. Thanks

Full text and comments »

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