tom's blog

By tom, 21 month(s) ago, In English,

Hello everyone,

I'm looking for interesting links to optimization problems (for which you need to write heuristic solution) and (**important!**) you need to send file with answers only (no need to send code). I would like to try out different libraries with no compile errors.

Thanks!

Read more »

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

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

Hello,

I'd like to share a problem with you that me and my friends cannot solve. Statement is really short and simple:

Given a sequence of n integers find number of balanced intervals in it. Interval is balanced if all occurring elements have the same number of occurrences, e.g. 1, 2, 2, 1 or 4, 5, 2, 2, 4, 2, 5, 5, 4 or 100, 100

Thanks!

Read more »

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

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

You are given two strings — text t and pattern p. You need to find index i such that t[i...i + p.size() - 1] and p have the largest "match value". Match value of two strings of equal length a and b is total number of such j that a[j] = b[j].

Can you do this faster than O(n2) (tricks with bitsets do not count)?

Read more »

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

By tom, history, 3 years ago, In English,

Hello everyone,

I would like to quickly compute maximum sum subarray with queries (change ith element to x). Can we do it faster than O(log(n)) per query?

Read more »

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

By tom, history, 3 years ago, In English,

Hello Codeforces community,

Here is a problem: http://www.spoj.com/problems/SOLVING/

How would you solve it? I don't want to skew your view, so I just leave the question without mentioning my (apparently too slow) solution.

Thanks, tom

Read more »

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

By tom, history, 3 years ago, In English,

Hello everyone!

I've been thinking about solution to the following problem for few days and didn't come up with any reasonable idea. Could you help me out?

You're given array of n elements and q queries. Every query is one of two type:

1) Reverse interval [l, r], e.g. for array 1 2 3 4 5 6 and query [2, 5] we end up with 1 5 4 3 2 6.

2) Ask for sum on interval [l, r].

Thanks and have a nice Sunday.

Read more »

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

By tom, history, 3 years ago, In English,

I'm wondering why nobody posts this topic earlier...

Let's predict final four of EURO 2016 in France! I hope there are many football fans amongst Codeforces community.

My bet:

  • France

  • Italy

  • Germany

  • One of dark horses: Belgium, Croatia, Poland

What's yours?

Read more »

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

By tom, history, 4 years ago, In English,

Hello everyone,

I was trying to format text (use bold, italic, strikethrough) or put image in it, but I don't know how. The ways I use in blogs do not work.

Can you help me?

Read more »

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

By tom, history, 4 years ago, In English,
int highest(long long n) {
    int r = 0;
    while(n) {
        r++;
        n >>= 1;
    }
    return r-1;
}

int dfs(long long n) {
    if(n == 0) return 0;
    int h = highest(n);
    long long n1 = n-(1LL<<h);
    long long n2 = (1LL<<(h+1))-n;
    int res = 1+dfs(n1);
    if(n2 < n) res = min(res, 1+dfs(n2));
    return res;
}

What is complexity of dfs(n) and why?

Read more »

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

By tom, history, 4 years ago, In English,

Hello everyone,

I have 2 contests in my group. In first one, users can see tests for all problems (My submission > Submission ID > Under the code) and in the second one, they cannot. I can't see any difference between these two contests. How to make all tests visible to the members?

Thanks

Read more »

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

By tom, history, 4 years ago, In English,

Hello everyone,

I'm setting up training contest for my students. It will last for about one month. The only problem is registration time. It starts few hours before contest. I'm afraid it will close when contest starts. I want registration to be open during the contest. How can I change it?

Thanks

Read more »

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

By tom, history, 4 years ago, In English,

Hello

Having n points in the plane with the property that any 3 of them are collinear, how can I add point to it and maintain this property?

Read more »

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

By tom, history, 4 years ago, In English,

Hello everyone,

Problem statement:

We have n > 2 pairs:  < line, side > , side . How can we check fast if they make non-empty polygon (or point)?

Cheers

Read more »

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

By tom, history, 4 years ago, In English,

Hello everybody,

Here's the problem: We have n < 100, 000 vertical segments with different x-coordinates. Is there any line that goes through each of it?

I've already known solution: We have to find 2 convex hulls: lower hull of upper points and upper hull of lower points and check if they intersect.

I'm getting WA on this problem. I know how to find convex hull, but I'm not sure to idea of checking intersection. Could you provide me how you would that?

Thanks

Read more »

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

By tom, history, 4 years ago, In English,

Hello,

I'm solving problem with 2-SAT algorithm and I need to be sure that some xi will be 1 (or 0). How can I make this happen with 2SAT algorithm? When I add "xi or xi", I put xi and not xi into one SCC and 2-SAT returns me that there is no solution. Is it possible?

Thanks

Read more »

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

By tom, 4 years ago, In English,
 
 
 
 
  • Vote: I like it
  • +170
  • Vote: I do not like it

By tom, 5 years ago, In English,

Hello everyone,

I've found couple of interesting data structures recently, e.g:

Palindromic tree — http://adilet.org/blog/25-09-14/ ,
http://codeforces.com/blog/entry/13959 (thanks to adamant)

and Wavelet Matrix — http://www.dcc.uchile.cl/~gnavarro/ps/spire12.4.pdf (anta used it in problem E in last round — http://codeforces.com/contest/543/submission/11036065 )

It made me wonder, how many great and useful, less known data structures are out there?

This is a question for you — do you know any?

Please share them with us.

Greetings

Read more »

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

By tom, 5 years ago, In English,

Problem for you for today's evening:

You are given DAG with N <  = 1000 vertexes and M <  = 10000 edges. Vertex 0 is starting vertex and vertex 1 is goal vertex. Set weights to edges from {1, 2} in that way that all paths from start to goal will have the same distance or print "NO" if it's not possible.

Read more »

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

By tom, 5 years ago, In English,

Hello everyone,

I started learning Python few days ago and I encountered issue during solving problem from Div2. Look at these submissions:

10232811

10232825

They second one differs with one line: sys.setrecursionlimit(10000)

Without it first submission gets RTE on test #19.

Is it my fault, bug in CF or something else?

Read more »

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

By tom, 5 years ago, In English,

Hello everyone,

Recently I've started to interest programs that play in various games. I'd like to create one, for example one that play checkers.

Do you know any books/tutorials/websites that could help me?

I'd like to discover for instance: recommended techniques how to code complex minmax algorithms, programs that can adjust to opponents' play, how to code managing differrent strategies for play and so on, so on.

Thanks in advance.

Read more »

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

By tom, 5 years ago, In English,

Hello,

I'm struggling with following problem: We have n < 37 cities and m < n * (n - 1) / 2 undirected roads between them. Every city has a treasure in it with g[i] gold. Our robbers wants to get from city 0 to city n - 1 and take as much gold as they can with them.

To do this, they can (or not) rob every city they visit. They're hurry, so they can visit only cities that land on the shortest path from city 0 to n - 1 (if there are more than one shortest path, they can choose freely).

But there is a catch — they also need to go back from city n - 1 to 0 (now, they can move as they want), but! they cannot visit any city they robbed twice (dwellers will wait for them).

How much gold can they rob on they way to city n - 1?

Read more »

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

By tom, 5 years ago, In English,

a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation..

Look at this example:







Any variable and its negation belong to the same strongly connected component, but it's not possible to satisfy these formulas.

What I'm doing wrong?

PS: With formula, I want to force x = 1

Read more »

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

By tom, 5 years ago, In English,

We have tree with n vertexes and we can cover this tree with k simple paths (paths can overlap). How many vertexes we can cover?

k <  = n <  = 106

Read more »

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

By tom, 5 years ago, In English,

Round 284 is going to take place on December 24th. It's Christmas Eve. Can you reschedule it to <= 23rd or >=27th December, please?

Read more »

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

By tom, 5 years ago, In English,

I'm reading following tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

Description of O(n4) algorithm doesn't seem to be clear for me. Why do we need add to edges (v, w) where ? Why n2 iterations is enough, since we add weight to 0-edges?

Read more »

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