Hi, codeforces,

Today we hosted our local contest and we'd like to host it online for people who couldn't attend. We already uploaded the problems to polygon and added them to a mashup contest, which I then add to a group and works fine, I don't know if it's the best way but it works.

But we would like very much if we could add ghosts participants of the original contest. We hosted it in DOMJudge and I have a scoreboard.tsv, but I don't know what format codeforces expects and can't find it anywhere. If I try with my .tsv I get "Invalid DAT-file syntax: Can't find divider character." If you could point me to what format this expects I would appreciate it :)

Thank you

I wanted to finally reach red (after being stuck at orange for some years now) and I asked myself what should I study. I thought I should review one of the most important things I learned, that helped me go from expert to master very quickly, but then I realized I've never seen people referencing that resource here in codeforces, which seems crazy to me.

The main ideas are presented in a paper titled Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi, which is available online for free.

I wanted to present this old paper to codeforces, urge you to read it if you haven't (it's just 5 pages long), and, if you have read it, ask you if you have benefited from these very useful techniques and concepts too (I'm sure you have, it's just that I'm perplexed I haven't seen it mentioned here before).

I'm confident that studying again these concepts will make reaching red easy (and make me a better programmer in general)

Hi codeforces :)

My name is Augusto and I've been doing competitive programming for some years now. Rapid City World Finals were my second ICPC WF, so my ICPC-contestant times are over :'( But I still have a long way to go to become a red coder! And also a lot of coaching to new contestants at my college :)

Meanwhile...

I know codeforces community is great and you can get help just by asking, but I wanted to try giving online competitive programming tutoring to people that feel like they need or that they'd like this kind of help. People here are great and as I said, you can always get help, easily, but usually it's not a very dedicated help (though there are amazing exceptions to this! (amazing codeforces community is amazing)) and maybe that's exactly what you feel you need, somebody that dedicates a couple of hours to help you :) Maybe talk about some algorithm you want to understand better, or about some problems you need help with, gaining intuition on some kind of problems, talk about my experience at the world finals or in codeforces contests (it isn't much but maybe it can help you), talk about what I think has helped me the most to improve my skills and about what you're doing to improve yourself... anything you want (except, probably, geometry D:). I actually have given a lot of lessons to friends at my college, just wanted to try it online now because:

• I want to improve my English. I think I'm not that bad explaining algorithms and problem solutions in my mother tongue (I'm not the best either :D), but I need practice doing it in English :)
• I would like to charge some payment (I know I wouldn't get rich or anything ;)). In my free time I give math (sometimes physics) lessons to high school students but I find this really boring and unrewarding :( mostly because the students aren't usually interested, they take the lessons because they have to pass some test or basically because their parents made them take it. I do it just because of the money and just to pay my very small expenses. If I could get some money out of these online lessons I could give fewer high school lessons (hence, I could be happier :)).

I know I'm nowhere near the best coder here, but still I think I could help a lot div2 people who's struggling to improve themselves, as I've done a lot with people at my college.

But before formally charging money I have to see how the lessons go. So, for now, I will just accept whatever you feel paying, even nothing (I would appreciate at least something, though, hahaha :'( due to my country's horrible economic situation, even a little money makes a big difference to me).

So what do you say? Are you interested? Send me a message with the topic or problems you want me to help you with and I'll prepare the lesson :) then we can agree on the time!

Any comment/idea/thought are more than welcome :)

I start a contest. My mind feels great, it feels sharp and quick (for my sharpness and quickness standards), after the contest I feel excelent about my performance and feel I did as well as I could.

Next contest, my mind... well... I might be drunk as well, I can't even read the statements, feel like I can't do easy stuff, think too many things that later find out to be obviously wrong...

Can you relate to this?

My point is that some days I just simply can not wake up my mind and it's really frustrating, even for days I just want to study or train.

So I'd like to know, do you have some warm-up exercises for your mind that you would like to share? Exercises or routines you do before training/studying/competing? Saying the alphabet backwards, trying to calculate Fibonacci mentally up to fib(100), I don't know, what do you do? :)

I would like to discuss last SRM problems here since I find much more comfortable CF than TopCoder forums (>.<) and it seems like they stopped publishing editorials here: Where they used to post editorials

I managed to get the first problem accepted, this was a problem with many many hacks, I think because it was kind of easy to go with a greedy approach.

My approach:

Div 1. Level 1

We're given an undirected multigraph with 50 vertices and M edges (1 ≤ M ≤ 20). We need to paint all vertices of the graph, one at a time, and after every time we paint a vertex we have to pay a fee equals the number of edges that have both ends already painted. We want to find the minimum total cost of doing so.

First we note that if we paint second vertex of edge e at time t (starting at t = 0 and increasing t after we paint a vetex) we will have to pay 50 - t in total because of this edge. So if a vertex v is the second vertex to be painted for k_v edges and we paint vertex v at time t_v, we will pay (50 - t_v) * k_v in total for this vertex. Then we see that if we're given the sequence k₀, k₁, ...k₄₉ we would like to paint the vertices in increasing order of k.

To find the solution we iterate over all possible ways of orientating the M edges. For a given orientation of the graph, if edge e = (v, u) is orientated u → v means that v will be painted after u, and vice versa otherwise, also for a vertex v, k_v is simply its in-degree. We calculate the cost induced by the given orientation by sorting the sequence of k's and summing up each k multiplied by 1+its index in the sorted sequence.

Is any orientation a valid one? No, it's easy to see that if an orientation has a cycle, it probably won't induce a valid order for painting the vertices, so we need to check if the orientation is acyclic. Also, the orientation could be acyclic but painting the vertices in increasing order of k won't respect the meaning of the orientation, and the cost calculated won't be the correct one, so we need to check this too, which seems more difficult. But actually we don't have to check anything :) In both cases we can prove that the cost calculated is sub-optimal, so we're happy.

Time complexity O(2^M * Nlog(N)) where N = 50, the number of vertices. (We could sort in O(N) but whatever :))

Hi,

I was doing some virtuals and found this problem 581F - Зубликанцы и мумократы

We need to color each vertex of a tree of either color 0 or color 1, such that # of leaves of color 0 equals # of leaves of color 1 (there is an even number of leaves) and we're asked to minimize the # of "bad edges". A bad edge is an edge that connects two vertexes of different colors.

For solving it I tried a dp, I first rooted the tree at a non-leaf vertex and try dp[c][u][cnt] = minimum number of bad edges that let us paint the sub tree of u such that u is colored c and there are cnt leaves of color 0. So answer to the problem will be min( dp[0][ROOT][(#leaves)/2], dp[1][ROOT][(#leaves)/2])

For each node u I calculate this dp by starting with an empty subtree and adding one child at a time, for each child v I iterate cnt over the new size of the subtree of u, and for each cnt I iterate cntv ( cntv = how many leaves is contributing v to this cnt).

Here's the code: 19434646

I got accepted with it but this kind of dps always confuses me, I don't know how to measure time complexity. To me it seems to be not very good, I would say its something like O(N^3) at least but it ran in 109 ms for N=5000. I've done other dps like this one before and I think I'm not measuring the time correctly (major reason why I tried sending this code hehe). Could someone give me a reasoning that would led to a better measure?

Thanks.

Hope I made myself clear.

Hey, I was upsolving some problems and one of them was this one: 599E - Sandy and Nuts

I liked the problem and after reading the editorial and some silly mistakes in the implementation I got accepted and feel that I learned something, but there's something I don't understand in the editorial, the time complexity.

I understand how to check the fulfillment of the conditions before a transition in O(N³) or O(N·Q) but I don't understand where does the O(3^N) come from.

Could anyone give me an explanation or at least some hints about the 3^N? ;)

Here's my solution btw 14830356

Thanks :)