Hello Codeforces community,

I am writing to you to seek help and guidance.

I'm running algorithm class in my former high school. We meet online, since I do not live at my hometown anymore. Every week me and/or my assistant (also, my former student) try to cover one new topic and explain related problems. We run the class entirely for free dedicating our free time and energy to it. We do not get any help from the school and teachers. Mainly it's because they do not have enough skills to teach CP. And they're simply too lazy to learn it.

I started the class, because I know how difficult is to achieve something in this field when you encounter CP late in college for the first time. I needed to work like mad to catch up, Even though made me fell inadequate many times I do not regret any minute spent on solving problems. I think it taught me analytical thinking, forced me to find a proof of the solution before implementing it (sometimes very painfully) and, in general, helped me to become a better programmer. Also, I landed my dream job by virtue of knowing algorithms well.

So I decided to share my gratefulness by helping other young people :)

Unfortunately, it's much easier said than done. We've been running the class for more than 3 years with small breaks. At the beginning, it was pure fun, but over time it gets more and more frustrating when you spend your time and energy and you get nothing in return. And I don't mean money here. What we strive for is to help these young guys to get to Polish OI finals. For now, with no luck.

I understand that some of the people are just not gifted enough to get there. Especially, given polish OI is considered as one of the most difficult in the world. However, I would like to focus more on what we can do, not on the things we cannot change. I see the following problems and questions:

• It's difficult to advance to finals without systematic training at school and constant pressure from teachers and peers. We do not have any ways to put the pressure on them. We're not there (I live abroad). We do not grade them. Even if we did, the grades would be meaningless.

• If you don't advance to finals, you get nothing at high school. It's all or nothing game. So you need make a decision what to sacrifice (unless you're a genius kid). How to convince them to let go (within reason) other classes?

• We do not get any help from teachers. Even parents do not know what we're doing. Perhaps this is the main point we're doing badly. Should we strive for more publicity?

We decided to ask you, guys, because well... you are really good in this matter, :) You've all made the way from total beginners to advanced competitive programmers. And some of you are experienced with well organised, efficient algorithm classes at your schools. Sharing your experience would be of great help to us. In particular, we would like to ask you:

• How did you manage to solve many problems and, at the same time, learn stuff for other classes? Did your school help you focus solely on preparation for OI?

• What motivated you the most (other peers, prizes, OI camps, feeling doing something special)?

• How did meetings look like? How often did you meet?

• How the collaboration between students was formed and fostered?

... Or perhaps you run your own class and you can tell us more how you do it. How do you spark students' interest? What resources do you use? Do you have strict teaching plan?

Please share your thoughts with us. Any help would be greatly appreciated!

Best of luck,

Tomasz

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!

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!

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(n²) (tricks with bitsets do not count)?

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?

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

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.

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?

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?

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?

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

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

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?

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

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

Hello,

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

Thanks

Problem A:
https://youtu.be/xIvFJYo9928?t=1h57m56s

Problem B:
https://youtu.be/xIvFJYo9928?t=5h43m9s

Problem C:
https://youtu.be/xIvFJYo9928?t=2h35m50s

Problem D:
https://youtu.be/xIvFJYo9928?t=2h58m55s

Problem E:
https://youtu.be/xIvFJYo9928?t=3h12m36s

Problem F:
https://youtu.be/xIvFJYo9928?t=4h1m56s

Problem G:
https://youtu.be/xIvFJYo9928?t=5h34m30s

Problem H:
https://youtu.be/xIvFJYo9928?t=4h17m29s

Problem I:
https://youtu.be/xIvFJYo9928?t=3h30m17s

Problem J:
https://youtu.be/xIvFJYo9928?t=4h31m59s

Problem K:
https://youtu.be/xIvFJYo9928?t=5h16m49s

Problem L:
https://youtu.be/xIvFJYo9928?t=3h41m51s

Problem M:
https://youtu.be/xIvFJYo9928?t=4h49m29s

--- Thanks to: SuprDewd ---

More solution sketches: http://www.csc.kth.se/~austrin/icpc/finals2015solutions.pdf
6-Hour Live Coding with SnapDragon where he goes through the WF problems: https://www.youtube.com/watch?v=fFs8-cTq83k

Hello everyone,

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

Palindromic tree — http://adilet.org/blog/25-09-14/ ,
http://codeforces.me/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.me/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

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.

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?

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.

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?

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

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 <  = 10⁶

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