Hi. Remote team competitions/trainings became something we have to deal with nowadays and I think having a setup you feel comfortable with is something really valuable and nontrivial to achieve that you definitely should not neglect, effort put into this will quickly pay off. In our Polish Mafia team we already participated in many remote competitions and struggled with various technical problems and through trial and error we converged to a setup which I believe is close to ideal. Many of these pieces of advice are applicable to all kinds of remote collaboration, e.g. working on some university projects or research problems, however I felt the biggest need for it during these competitions since they are periods when I really need to be focused hard.

1) Communication
The most important part in remote collaboration is communication. I definitely recommend PUSH TO TALK (that is — an option where you talk if and only if you hold a specified key). Background noises of other people (any kind of keystrokes, noises from other people in their house, barking dogs etc.) are really distracting a lot and will be a real pain during these competitions, so all messengers that don't have Push To Talk option and send all background noises (e.g. Facebook Messenger or Google Hangouts) are definitely not an option. The only easily accessible messenger I know of having this option is Discord and it is the only one that I recommend, but if somebody knows and prefers some other ones they could be an option as well. I mention that in order for Push To Talk to work properly you need to have an app — Discord in browser will not suffice, because Push To Talk will not be system-wide then (you need to have browser window open for it to work and that would be really inconvenient). Apart from background noises, another really irritating sound is your own echo heard with a delay from other teammates. Without Push To Talk you need to have headphones so that other people don't hear their own echo, but with Push To Talk you do not even need headphones (and having headphones through whole duration of a 5 hour contest is rather inconvenient). Push To Talk key should be one that doesn't have any other meaningful function in your environment, e.g. space and enter will be terrible. I personally use Right Ctrl. One more advantage of Discord is that it lets you customize volume for each person, so if somebody is loud and somebody else is quiet because of some reasons, you can just adjust that easily.

2) Drawing
When meeting with your friends it is easy to discuss about some ideas when drawing in your notebook. Sadly, it is not possible remotely. In order to remedy this I recommend any online drawing board that you feel comfortable with, e.g. awwapp.com or idroo.com

3) Screen sharing
On typical contests it is often the case that one member is coding one problem and second member (or maybe even third one if it is close to the end) watches it carefully to immediately catch any bugs in a code that is just being written. In a remote world you need screen sharing for this, so you should use some messenger that has this option. Fortunately Discord has this functionality as well. One more thing worth noting is that person coding being watched by somebody else should probably switch to Voice Activity rather than Push To Talk.

4) Control sheet
That one is rather optional, but considered useful by some. You may prepare a sheet when you will have a state of each problem. In it you may have 3 tables (problems)x(members), where you denote 1) who has read what problems, 2) who was assigned which problems (if you assign them on the beginning of the contest), 3) who works on what. Rows corresponding to accepted problems should be deleted. Example of our sheet is here: https://docs.google.com/spreadsheets/d/1Yd2-QcMVuPsMzLPPEyZHnC2U1Zlan7X8lB636u7hJHs/edit#gid=0 (you may make a copy for yourself)

5) Printing out statements
Printing out statements is another totally optional thing of a personal preferrence. Since I am the guy that distributes problems in our team, I need to make a quick pass through them and distribute them on the beginning and I consider having them printed out convenient for this. Having printed out statements when solving is nice as well. But yeah, that is definitely not needed

Hi Codeforces, today I wanted to talk about difficulty of browsing/searching old blogs. As we all know, blogs are one of key features of Codeforces, that's why Codeforces has problems and community and others sites have just problems, but there is one thing about them that is annoying me since forever and nothing has been done here even though Codeforces experiences a lot of various improvements throughout the years. And that thing is that it is basically impossible to browse blogs that are no longer in "recent actions"! Sometimes I want to write some comment under the blog that was active yesterday, but nobody wrote there anything today and it got out of recent actions and I have no way to find it! Or example of another usecase: yesterday I virtually participated in WF18 and remembered that there were some discussions about problemset, about issues with precision, some rants on "physics problem" etc. and I would like to read that, but I couldn't really find these topics. Some cheaty ways of finding old blogs would be to remember username of author or somebody that posted a comment there and search in their blogs/comments, but I often don't remember that. Google can sometimes help, but sometimes can't.

What I would love to see would be the following:

1) List of all blogs sorted by time of last post, so that I can browse them in order of ongoing discussions and so that I can find some blog that I read yesterday since it was in recent actions, but today it isn't (I have no particular blog in mind, just explaining general usecase :P).

2) List of all blogs sorted by creating time, so that I can browse them based on remembering when it was created, which would be very useful when finding blogs about some particular competitions since blogs about them are created around the time when they happen.

Maybe after it is done, some other features can be added like for example filtering by color of author (either by current or by his color when he created blog) since that information is often easy to remember and can help searching blogs, but these are far less important than providing functionalities which I described before.

I really wish these could be implemented and I wish you a wonderful day!

Hi, I wanted to present to you guide on how you should set up TopCoder Arena in order to make competing in TC much more pleasant experience. Or at least guide how to do the same thing as I did which seem very comfortable to me compared to this big pain of competing in bare default Arena. In case you want to grab easy upvotes please leave here some joke about how I am jealous about Radewoosh getting insane boost in his contribution by writing his blogs, but the real reason is that I screwed my setup recently and needed to go through this painful and magical setup once again and it seems this information is very nontrivial and not available publicly in a known place (which I believe is one of reasons TopCoder is losing its popularity, but I hope thanks to this post I can give slight boost to it by settling up Arena problems once and for all for many people), so I wanted to share it with others. I want to express my sincere thanks to tomasz.kociumaka for guiding me by hand in this process (twice), because I would never be able to do this on my own. By the way, I use Linux, obviously. Probably many steps are also similar on Windows or Mac, but I'll leave any hypothetically needed changes up to you.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Plugins I use are CodeProcessor, FileEdit, moj and pq. Overall functionality they offer me is:

1) When I open a problem statement they create a new file corresponding to this task in a designated location.

2) This file contains template code I used, created class for me with already correctly declared method I need to fill in and namespace with samples which are then executed in main.

3) After I end coding I am able to compile my program locally (with my own debugging flags), run it and get automated feedback about its speed and correctness. This is done by moj plugin.

4) I have a simple way of adding my own sample testcases.

5) When I'm ready to submit I need to hit "Compile" button in arena and then "Submit".

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

So let's go to the point of how we should go about setting this up:

1) Go to this page https://www.mimuw.edu.pl/~wn341489/TCplugins.zip, download this zip and extract it in your fapfolder. I will denote path to this extracted folder as /path/TCplugins

2) Go to Arena, log in and go to Options->Editor->Add and fill this accordingly:

Name: CodeProcessor
EntryPoint: codeprocessor.EntryPoint
ClassPath: Add 4 paths here, to CodeProcessor.jar, FileEdit.jar, moj.jar and pq.jar (I've done this by multichoice with held Ctrl). After this it should look like /path/TCplugins/pq.jar:/path/TCplugins/moj.jar:/path/TCplugins/FileEdit.jar:/path/TCplugins/CodeProcessor.jar

save this and tick boxes next to newly added line (and maybe uncheck others if you have any ticks elsewhere)

3) Click on this newly added line and click "Configure". New big window will pop up. Fill Editor EntryPoint as fileedit.EntryPoint . Next to "CodeProcessor Scripts (...)" hit "Add" and add two entries "moj.moj" and "pq.MyPostProcessor".

4) Hit "Configure" next to Editor EntryPoint and specify path where your codes will be appearing (do not use "~" in your path, it doesn't work, you probably want to use something like /home/anon/something). Uncheck this very stupid option "Backup existing file then overwrite". Go to "Code template" and if you use C++ then modify your template to something like this (filling out parts within underscores): https://www.mimuw.edu.pl/~wn341489/TopCoderTemplate.txt (I wanted to paste it here, but my attempts to correctly display dollar sign were futile, if you know a good way to do this, please message me). If you happen to use hack like "#define int long long" then also put "#undef int" before line with method declaration and "#define int long long" after it.

5) Restart you Arena and you are ready to go! Go to some practice room and do Div2 250 to familiarize with workflow with all these newly added plugins.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

A few technical notes I would like to point out:

1) If I'm not mistaken on TopCoder your program is executed many times — once per every testcase. However locally your program is executed one time and it does many calls to specified method. It may seem like there is no difference, but there is a significant one — state of your global variables. You may leave your global variables in some random state and it will not affect execution of your program on testing servers, but it can affect behaviour of your program locally and you may get local WAs even though your program would be considered correct by TC. However I very rarely use global variables in TopCoder because only reason I can think of right now for using them is that when declared globally instead of putting them as attributes of my class, they are zeroed by default (which disappears if you want to be able to test your program locally, because you need to clean them anyway).

2) If you did some defines it may affect your remote compilation on server. Your code is somehow included in testing framework and this code TC adds to your code in order to grade your solution uses some variable names etc. too. It is unlikely that something like "#define SZ(x) (x).size()" will affect compilation on server, but "#define int long long" will very likely do so. That's why if you use some common expressions in defines, you better undef them (like "#undef int") at the end of your code, because otherwise you will get compilation errors when submitting even though your program compiles locally and it will be very confusing.

3) Apparently, informations about this setup are stored in ~/contestapplet.conf file. You can save a copy of it in some safe place (so that you can restore it whenever you do some mess or change your laptop) and be aware to not move this file around (that's how I screwed up my setup recently, because I cleaned my home directory of some weirdly looking files).

4) When testing locally, what is performed in order to check correctness of your code is to do some simple diff (it takes appropriate care when there are doubles in output, so don't worry about them). Be aware that problems with multiple allowed outputs exist and in such cases local testing tool will say that you FAILED, so in such cases you will need to validate your output by yourself (or use "Batch test"). But that is the same as in every other platform (unless we are provided some checker, but we are never provided, so yeah). Be aware that in such cases you should use option "Batch test" in arena which checks correctness of your output (but look at field "Correct example", not "Success")

5) Sometimes expected output is an empty vector. Code attached for testing on samples doesn't compile when expected output is an empty vector (in cpp), so you need to manually adjust that. For example by changing expected answer to {-1} and checking correctness by verifying that all your failed sample cases look like:
Received: { }
Expected: {-1}

http://thepolishbookstore.com/en/p/446812/looking-for-a-challenge-the-ultimate-problem-set-from-the-university-of-warsaw-programming-competition

I hope that I will never ever again get any private message requesting help in obtaining this book :P (which I got tons of). Inb4 I have nothing in common with this book, I am just passing info.

EDIT: Look below for monsoon's comment for stores with much better price.

Hi, I don't know about you, but I was convinced that TopCoder editorials were mostly abandoned long time ago, but I learnt from today's e-mail from TC (which I assume almost nobody fully reads) that in fact they are in a very good shape and we can find editorials to almost all recent competitions. I thought this is a valuable and nontrivial discovery, so I decided to share it with you. Here they are: https://www.topcoder.com/community/data-science/data-science-editorials/

Hey,
I just have one simple question that I think is not answered in any FAQ, rules etc. — can I safely virtually participate in some contest if there is another ongoing contest? I wanted to virtually participate in some contest, but I see that there is Div2 contest in less than 2 hours and I am afraid that at some point my submissions will stop being evaluated. It would be good to have a public answer to that and if somebody knows how it currently looks like then I would be glad to also know what happens in a case of gym contest during ongoing contest.

I see that in 2,5 hours there is a fun SRM, so I thought I would let you know cause I learned that coincidentally and I see no blog about it (but expect it to be probably significantly easier than Div 1 :( ). If I did everything correctly, here is its time: https://www.timeanddate.com/worldclock/fixedtime.html?msg=Fun+SRM+%28Pittsburgh%29&iso=20170908T19&ah=1&am=35 P.S. clist.by shows this: https://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO17%20Pittsburgh%20Event%20/%20Fun%20SRM&iso=20170908T1700&ah=6&am=0 which is 2 hours earlier, but Arena's schedule says what is in first link...

Hey, I recently managed to play with some small magnet balls and created a simple riddle:

https://www.dropbox.com/s/raleq3lsuhjr4pz/Riddle.mp4?dl=0

Question is: how many balls are there?

I didn't do anything sly, interior is filled as tight as it can be. Of course it is rather simple, but I find it entertaining. Please use 'hide' tags for answers.

UPD: Congratulations to lmn0x4F on being first one to give correct answer :)! If you want to read my explanation and additional comment then look at my answer to rng_58's comment.

Hello. I gathered some questions about older (2006-2008) problems. As commonly agreed, if you possibly plan to ever use these problemsets for training then please do not read this blog in order not to spoil valuable problemsets. But if you know these problems/solved them or whatever then maybe you can answer some of them.

Link to past problems is here: https://icpc.baylor.edu/worldfinals/problems

1. Problem C 2006 "Ars Longa"
   How to solve it? We have an idea how to determine which of these 2 conditions hold: 1) non-static, 2) unstable or stable, however we do not know how to distinguish unstable and stable. Since every rod affects two balls on its ends with opposite forces (parallel to rod) we can create a variable on coefficient how this rod affects balls and create equations for every coordinate of every not glued to floor ball stating that resulting force is 0 and use Gauss to check whether such system has solution. If it has then construction is static. It seems that in order to check stability we should try using force on every ball (in 3 different directions) and check whether system still has solution, but if we are not mistaken this reasoning fails for a case of a cube (with one side lying on floor) with 4 main diagonals. It is stable, but I think there are no good coefficients for rods if we want to neutralize horizontal force applied to one ball. Did we assume wrong physics model? Or did we simply make some silly mistake along the way?

2. Problem H 2006 "Pockets"
   I think this is algorithmically relatively simple problem, I coded it, but I keep getting WA/RTE and I came to the point when I suspect the test data is wrong. If I get RTE this is because of various asserts I put in my code. I deduced that my code thinks that resulting sheet has width 6 or 7 on test it fails on ejudge (thanks to asserts), but computing that width alone is relatively simple. I stress-tested my solution on many tests and that gave 0 errors, I have read that simple part many times and I see no errors. Is there anyone that got this problem accepted?

3. Problem H 2007 "Raising the roof"
   I don't how to solve it faster than O(T³) (with significant constant) what clearly would get TLE. Solution in such complexity is pretty straightforward algorithmically, so I won't go into details. I have an idea that might result in faster program, but I don't know if it really does. For every pair of triangles we might compute whether one of them covers another one and in such case create a directed edge between them. Such graph is acyclic, so we can process these triangles in topological order, starting from highest ones. When considering some fixed trinalge in order to compute its visible part it suffices to look at this triangle from above and substract regions that are covered by already processed triangles. When done naively that is too slow, but if we store sum of already processed triangles as some set of boundaries maybe that will speed it up. If it would be allowed to give us many thin triangles such boundary will be of quadratic size, so no improvement is done, but maybe since those triangles have small amount of different vertices (at most V<=300) it is possible to give better bound? Or maybe there is a different approach?

4. Problem C 2008 "Conveyor Belt"
   I coded simplest possible approach (backtrack considering all possibilities in every step) with some time-heuristics and got OK on my first submission. Then I removed all heuristics and it still gets OK. I can't bound running time by something better than O(n!) (n is up to 20), but I can't also construct a case when it needs a lot of work (worst I came up with was and I think higher constant may be achieved). Both proving better complexity bound than O(n!) and constructing cases worse than O(cⁿ) for some constant c both seem to be challenging problems. Is someone able of doing either of these? Or maybe there is a completely different approach in better complexity (I doubt that)? Or did judges simply pose a problem that they have some solution for that simply empirically runs fast enough on their test data?

Hello. It has proved to be not well known that there is currently going DCJ practice round! Everybody who is going to participate should take a part in it to familiarize with distributed environment! Here it is: https://codejam.withgoogle.com/codejam/contest/6264486/dashboard Info about it was written in a mail which looked like it doesn't contain any interesting info, so probably most users disregarded it and don't know about those rounds. Thanks to zholnin for letting me know!

I have observed that many topics definitely not violating rules are disappearing from Codeforces. Examples of that are:
1) yesterday's blog with discussion about programming environments and editors (I couldn't even read two replies to my comments which were posted after I fell asleep, because at morning topic was already not existing),
2) "copy" of http://codeforces.net/blog/entry/23612 which I found pretty funny,
3) topic with my comment with >800 upvotes ;__;.
These are just few of them which came to my mind, but that happens definitely too often. What is the reason behind it? Are they disappearing because of nasty CF moderators which simply didn't like them? Or is it because their authors decided to delete them (more likely than previous one :P)? If that is the second case then I think that authors should not be given option to delete their blog entry. Option to change their post (already existing option) sounds much more reasonable and completely sufficient if author wants his post to be no longer visible. When deleting blog entry they delete not only their entry, but also whole discussion which is often much more valuable than entry itself thus deleting input from community and at the same moment cutting vivid discussion.

Hi. Near the Le Meridien hotel (and also probably all around the Phuket) you can meet unfriendly homeless dogs. If you don't want them to attack you, try avoiding them and hold big stone in your hand (to make them afraid of you, not to throw at them :f). One of them bite me yesterday in the leg from behind (2 mins walk from hotel) even though I didn't tease him or anything and I needed to go to hospital to take rabeis and tetanus vaccinations. So don't worry about me, but be careful about yourself, I don't want any of you to experience similar troubles.

Yay, that time has finally come! The list of TopCoder's contests is so long that I am unable to normally enter whichever practice room I want, because corresponding buttons are shown by arena in a place that is not visible on my screen :). For some time just dragging arena to top of screen was doing the job, but it is no longer sufficient :P. Am I the only one facing this issue or maybe it is device-specific or maybe I am just a retard and I am missing some easy solution? In order to enter practice room for SRM 686 I used navigation by arrows, but it is just a temporary hacky workaround.

Hi!
On recent OpenCup — Makoto Soejima Contest 4, problem "Random Walk" was posed. We were requested to determine the expected number of visited cells after n steps of random walk on a plane — in each move from (i, j) we go either to (i+1, j), (i-1, j), (i, j+1) or (i, j-1) — all with prob 1/4. More precisely, we needed to output , where M was some integer. In this problem constraint was n ≤ 5000. Actually, this problem becomes much more interesting if we try to solve it for n ≤ 10⁵ in a reasonable time (assume M = 10⁹ + 7 for simplicity). Can you see the solution (if I'm not mistaken — it exists)?

Qualifcations already happened :). Let's discuss problems.

Yesterday at SRM 670 I got a funny story which I want to describe. During challenge phase I noted that one solution of medium problem in my room uses Floyd-Warshall. I thought "Oh, why haven't I thought about it during coding phase? Much shorter than those DFSes!", but then I noted that unexpectedly this infamous order of loops is not correct. It went like this:

FOR(x, n) FOR(y, n) FOR(z, n) dis[x][y] = min(dis[x][y], dis[x][z] + dis[z][y]);

while everyone should know that FOR(z,n) should be the outer loop, not the inner one. I tried to hack this solution, so I inputted graph 0-3-2-1, however my test was rejected, because problem was about trees and there was a constraint that parent of vertex i should be less than i and I didn't have time to come up with another testcase. Unexpectedly, this solution passed systests! I thought that its author is very lucky. However it turns out that for trees with this constraint this order of loop result in computing correct distances!

What we need to ensure is that we will somehow detect this one particular path during execution of that algorithm. With this order of loops it consecutively tries to compute distances dis[0][0], dis[0][1], ... dis[0][n — 1], dis[1][0], etc. in lexicographical order. Initialization consists of conditions dis[i][i] = 0, dis[x][y] = dis[y][x] = 1 iff <-> x-y is an edge. We will inductively (on lexicographical order) prove that it computes correct distances. Assume that x-y is not an edge.

Consider two cases:

1. y is not a descendant of x
   Let z be parent of x. We have z < x, so (x, y) > (z, y) (lexorder of pairs), so dis[z][y] was already computed and x-z is an edge, so both dis[x][z] and dis[z][y] are valid values, so we will detect that path when looking at z.
   
2. y is descendant of x
   Let z be parent of y. We have z < y, so (x, z) < (x, y), so dis[x][z] was already computed and z-y is an edge, so both dis[x][z] ad dis[z][y] are again valid values and we are done.

Funny how bugged version of Floyd-Warshall turns out to be correct on trees with this weird constraint on parents :P.

Hi.

As we all know, when hacking, plain black code on a white background written in faint font is shown to us. It is a pain in the insert here your favourite part of body to read such codes, I think that supposed difficulty in hacking shouldn't be telling "1" apart from "l" or coping with tediously looking code. In my opinion syntax should be highlited appropriately and hacking window should be much larger. I think this would be very noticeable for all users of Codeforces and will make hacking much more fun and less repulsive. Do you agree with me in this matter?

Hi. BOI (Baltic Olympiad in Informatics) will be held on Thursday and Friday. I just learnt that organizers provide possibility of participation in an online mirror of that contest. Enjoy: https://sio2.mimuw.edu.pl/en/c/boi2015-online/dashboard/ !

Hi. Can someone shed some light on that mysterious mirror? It's in the schedule but there are no other informations in English CF... How it will be conducted, like a normal CF round or some ACM style contest? Can anyone knowing more than I share his knowledge? I guess that this round won't follow typical CF round, so it would be great to know something more and I suppose that our russian colleagues know pretty much.

P.S. When registering I got to know that it will be rated, but before that I didn't know even this.

Hi. I got a problem with TC Arena and I described it here: http://apps.topcoder.com/forums/?module=Thread&threadID=849024&start=0&mc=1#1991748 but since I need a quick help I decided to put this also here because more people will see this. If somebody could help it would be great.

Hi. I think that title of that blog entry somehow explains what I want to tell. I just think that since problems point values can be multiplies of 250 now, then dynamic scoring should be adjusted accordingly, so that we get intermediate state 750 between "1000 one AC more -> 500".

Hi. Today I got an exam on "Algorithms and data structures" for people which learnt sorting month ago and there was a problem that neither me nor Marcin_smu and few other good guys didn't solve and I'm interested in a solution, so maybe you can help?

We are given an array of integers a[1..n] and an integer k ≤ n^1 / 2 such that at least k different values are present in a. We need to swap some elements so that first k elements are pairwise different, they are sorted in increasing order and everything is changed in a stable way, which means that for a fixed value our changes preserved order among elements within that value. Moreover everything needs to be done inplace, that means we can use at most constant additional memory. Whole algorithms has to run in .

Hi. In this entry I want to discuss the score distribution and drain of points (by that term I mean how fast points value of problem is becoming smaller) in longer contests (joint ones like #270 or ZeptoLab). In my opinion everything (drain + typical distribution) works fine in regular contests, but not in those longer ones.

Due to standard habits adjusted to regular contests, distribution in longer ones (typically 7 tasks with difficulty similar to Div2A, Div2B, Div1A, ..., Div1E and 2,5/3h) is similar to 500-1000-1500-2000-2500-3000-3500. Also, contests are longer, so task submitted in the end of 3h contest is worth only 30% of its original value (drain is 0,4% of original value with every minute, but resulting in not lower value than 30% of original one, even when wrong submissions are taken into account). Then, having accepted problem worth 3500 pts after 2h and 55 mins without any previous wrong submissions is worth 1050 pts, while D submitted after 0,5h is worth 1320pts — much more than 1050 pts (even after 1h it will still be 1140pts) — it is clearly unreasonable! Then, if someone made a small bug in D or received random TLE, he will likely end up in a very bad position even though he did the hardest problem!

In my opinion, joint contests need special treatment for them to be fair. In my opinion ideal score distribution should be like 250-500-750-1000-1500-2000-2500 and drain should be smaller, scaled in such a way that if someone submits something in the end of contest it is worth 52% of original value (like in regular contests). There is a sufficient number of joint contests to make this issue important (for example — CF #270, MemSQL Round 1, MemSQL Round 2, upcoming Bayan Warmup, ZeptoLab, Rockethon). I hope that proposed solutions are not a problem from technical point of view (at least changing typical distribution should be no problem, adjusting drain may be more complicated).

What do you think about this? Share your opinion.

I just wanted to share with you that image :P.