Igor.Ivanich's blog

Stanford ICPC : Gaussing Game
By Igor.Ivanich, 14 years ago, In English

Hi everyone,

The problem which I've been stuck on is: http://cs.stanford.edu/group/acm/slpclive/problems/G.pdf

Can someone please give me some hints / idea how to solve this problem?

Cheers

Full text and comments »

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

USACO: Humble Numbers
By Igor.Ivanich, 15 years ago, In English

Hi everyone,

Well the problem which I'm going to discuss here is from USACO Chapter 3.

The problem description is given below:

For a given set of K prime numbers S = {p1, p2, ..., pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of `humble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a humble number.

Your job is to find the Nth humble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.

K and N, 1 <= K <=100 and 1 <= N <= 100,000.

 I'm getting TLE due to running O(N ^ 2 * K) algorithm (Simply I'm building the humble number sequence
starting at 1 then at each iteration find the minimum number which is bigger than the last found humble number).

Am i missing something? Or is there a better algorithm for solving this problem?


Thanks in advance.


Igor.

Full text and comments »

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

DP Problem
By Igor.Ivanich, 15 years ago, In English
Hi Everyone,

Please give me some hints about this problem:
http://online-judge.uva.es/p/v100/10032.html


I've been stuck on it for a week but getting TLE,
the DP state of my program is:

dp(total_weight, current_index, remaining person) = min(dp(tot_weight - v[i], current_index + 1, remaining person - 1), dp(tot_weight, current_index + 1, remaining));


As I said my solution gets TLE. because of huge size of my memoization array.


Thanks in Advance.


Full text and comments »

Tags dp, uva
  • Vote: I like it
  • +3
  • Vote: I do not like it

Find a Hamiltonian Cycle when each vertex of the graph has degree >= N / 2
By Igor.Ivanich, 15 years ago, In English


Hi everyone,

I'm new to Codeforces, Seems a very nice place for training.
BTW, I'm trying to solve this problem
http://acm.sgu.ru/problem.php?contest=0&problem=122
I've search for the Dirac's Theorm which states that there is a hamiltonian cycle.
But how should I build the path?


Cheers


Igor

Full text and comments »

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