poikniok's blog

By poikniok, history, 4 years ago, In English

The recently announced Codeforces Round #415 is at a time which directly overlaps with TCO17 Algorithm Round 2A. Given that the TCO schedule was announced a while ago could the Codeforces round possibly be moved?

Read more »

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

By poikniok, history, 4 years ago, In English

So for the last week or so I have not been able to view the second or later page of the submissions of my friends, aka the following URL:

“The page is temporarily blocked by administrator.”

I was hoping this problem would fix itself but given that it has been a week now and I enjoy reading the submissions of my friends I thought to inquire.

Read more »

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

By poikniok, 4 years ago, In English

So when I woke up this morning I saw that Codechef removed 2 of the 7 problems that were in the monthly long contest, link, because they were “found to be available online”. I wanted to make this post to protest this decision, as I feel like this sets a bad precedent, and does not have many benefits in my opinion.

My issue lies with the fact that part of reason I compete in long contest is so that when I do indeed solve a problem, I enjoy being able to look at other solutions after the contest is over, and learning from them. Removing problems makes this impossible I believe, and is also simply discouraging.

In addition I feel like the Codechef writers should spend 10 minutes Googling around before putting problem in. If they can not find anything in 10 minutes than I would say even if the problem can indeed be found somewhere, say on Chinese blog with code written in assembly, that it is nontrivial enough to find that it is okay to include the problem.

Having problems included for 3 days, letting people solve them and spent a lot of time thinking about them, and then removing them, makes for a bad contest in my opinion. As somebody who solved the problems without finding solutions online I would have been perfectly happy if they kept the problems, the fact that other people may have solved them by Googling does not upset me at all, particularly since in my opinion Googling is always a part of Codechef long contests, as at the very least for approximation problems and the like one can frequently find academic papers on the topic.

Anyway just wanted to make my opinion known, I don’t suppose the Codechef people likely care what I think, but maybe if people agree with me then they can change their policy for future.

Read more »

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

By poikniok, history, 4 years ago, In English

I have a question to ask experienced contestants about the plausibility of a possible way to improve at programming contests, by somewhat rapidly trying to read through problems and their editorials / solutions.

There have been several existing blog posts on Codeforces about reading theory vs solving problems, however my question is rather different, as rather than reading theory I am curious about specifically reading problems, and then the solutions to the problem immediately, without spending any time on personally thinking about or implementing solutions.

To give a specific example of such a source of problems I am considering attempting doing this with past Topcoder SRMs, as they have the nice property of having both editorials and also the ability to browse contestant solutions through the TC browser here ordered by the ranking / competence of the solver, and also the forums of course which at a certain time period were quite active.

Having done this for about a dozen SRMs this approach seems mildly promising to me, as by removing the need to solve the problem one can get a general idea of what kind of ideas are solvable by certain methods very rapidly. Certainly one does not gain any deep understanding of the problem, but it seems on a per time basis training one’s self to recognize patterns in problem types is somewhat useful. Particularly for me, there is no realistic way that I will ever actually work my way through solving the massive archive of past problems on Topcoder, and thus it seems nice to get some intuition from all the past work that people put into creating the problems and their editorials.

On the other hand I have not heard much about anybody implementing such a training method, which does provoke some skepticism I suppose. General advice has always seemed to me to involve either reading books / blogs / forums about general concepts, or solving problems oneself. Thus I must ask if anybody has embarked on such a project, and if it had any positive results, or alternatively if the consensus is that reading problems and their solutions is useless without personally implementing them?

Thanks for any advice!

Read more »

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

By poikniok, history, 4 years ago, In English

I am curious to hear if anybody has stories to share of people who delayed graduation in hopes of making it to ACM ICPC world finals, or doing better at world finals. Was it a success, or just more heartbreak for them?

As a somewhat unrelated aside, does anybody know what happened to Ferlon, of this livejournal fame?

Read more »

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

By poikniok, 5 years ago, In English

Have been thinking for a while on how to prove the following statement, does anybody have an explanation for how to solve this type?

We have a undirected graph with 2n + 1 nodes, with the property that, for any subset of n of them, there is some other node that has an edge to all n. Prove that there is a node that has an edge to every other node, that is, prove there is a node of degree 2n.

Read more »

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

By poikniok, 5 years ago, In English

Finals will be starting shortly, live stream can be found (UPDATE: contest has started already) here.

Scoreboard can be found here.

Problem statements are here.

Scoreboard from the warmup is here, does anyone know why the warmup had 36 contestants?

Read more »

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

By poikniok, history, 5 years ago, In English

I was curious to ask the Codeforces community what they think of the current CS research fields, and how possibly mediocre people in competitive programming can fit in / contribute. I am trying to find / think of a research field that I could possibly work in, and find productive and possibly contribute in, that is accessible to those who are weak intellectually.

It is very discouraging for instance thinking about theoretical CS, as the people are so strong mathematically and otherwise, and then even I see lots of red people on CF who it seems never try or have anything happen research wise. So to me then it seems clear, if there are red people of CF who never accomplish anything research wise in theoretical CS, then for somebody like me the situation is beyond hopeless, and therefore that is not the field.

However the issue with more applied fields is that they seem somewhat less interesting at times, and there is a lot of very specific knowledge required. So far thinking about things it seems that maybe computer vision or something like that could be better than theory / algorithms, however there seem to be downsides to this too.

I am curious if there are people on CF who have thought in similar way, and come up with any interesting conclusions? Because otherwise it seems that it is off to industry, however is that really the only option? Basically I guess to rephrase the question, does anybody think there are fields where having marginal programming ability in addition to marginal mathematical skills can amount to something? And maybe ideally the field would be interesting too…

Read more »

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

By poikniok, history, 5 years ago, In English

This is a blog post about possibly creating a new category of “problems” if one were to so call them on Codeforces, with the category being very standard problems requiring one specific data structure or idea. Now before you respond as to why one would want such a useless or simplistic thing, I think there are several useful scenarios. In particular sometimes right now I find myself in a workflow where I would like to try a particular concept, for instance topological sorting, max flow, range minimum queries, union find, or any other algorithms / data structures like that. Right now on Codeforces to do so one has to find a problem that uses such an idea, however of course the problem will have other extraneous ideas / tricks thrown in which one also has to code. And then the other thing is that for some concepts, such as maximum flow and even more advanced topics there are no simple problems that use it, they are all Div1 D and E problems which is quite intimidating.

What I sort of envision is problems where the purpose is clear and simple, for people to practice implementation. For instance problem called Topological Sorting, which would ask a user to sort a graph in topological order, or return if it is not possible. Or a problem called Union Find that would give users two queries, to join two indices, and to check if two indices are connected.

In particular I guess this would be sort of an extension of the Education series, except even more distilled down to basic algorithms, as even the Educational series requires innovative thought, or at least it seems that way to me.

Another aspect of this that I think would be very useful is to check / compete on the speed of implementation. For instance one of the few flow problems that is easy enough for me to understand is 546E - Soldier and Traveling, however it also has tiny limits, so after I implement maxflow I do not have great idea of how fast my version is. Maybe there would also different versions of maxflow problem, with different constraints, and at the highest level of constraints individuals could also compete with each other on fastest implementations, and people like me could check the leaderboards to learn fast implementations of various algorithms.

Now I understand that for this to happen takes a lot of work, and in some sense it is useless to suggest that other people do something, of course it is always great if other people do things. However I do not recall recently this sort of idea being suggested recently in any blogs, and I wonder if there are other people in the Codeforces community who feel the same way that I do.

I also understand if the Codeforces administration does not want to go in this direction, as it does sort of involve a simplification of the goal of competitive programming, and there is an argument to be made that there are maybe other sites that are better for something like this and so on. However I feel that this is in some ways just an extension of the Educational series of rounds to sort of appeal to maybe newer and less experienced people like me. And also Codeforces has great ranking system and a lot of great competitors that other sites do not. And so if I were looking at implementations of a certain algorithm for a problem, and it is done by somebody who is red I know that they have a lot of experience and probably any implementation choices they make have very good reasoning behind them.

Anyway I suppose there is not much point to this blog, but would be interested to hear if any people have opinions on this, or maybe I missed it and this topic has already been discussed and thought out. Thanks ☺

Read more »

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

By poikniok, history, 6 years ago, In English

I was wondering if any people here had experience with Kaggle? I am just now considering starting out there and trying to learn about machine learning, and wanted to know what opinions people here have. Are the contests and problems as interesting and informative as on algorithm sites like here?

Read more »

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

By poikniok, 6 years ago, In English

I am writing this in the hopes that Codeforces will seriously reconsider allowing purple coders into Division 2 contests. My personal reason for this is that the problem standards in Division 1 contests are quite high, and as a purple coder in the last few Div 1 contests I have not been able to solve any of the problems, and therefore I end up effectively not participating. Having read a few discussions that regard this as almost “cheating” in some way is also frustrating, because is one supposed to submit a known incorrect solution or what? Basically as a blue coder I was perfectly happy, because I could compete in Div 2 contests, and solve the A and B problems and have good shot at the C. However now having moved up to Div 1 has made my experience far less enjoyable, as in the more difficult contests I am simply unable to solve anything, and in average contests I can only hope to solve the 1st problem at best. Now of course the optimal solution to my problem is simply more practice until I am able to solve Div 1 A’s and B’s, and effectively move up to yellow, however this is not a true solution. Basically I feel that Codeforces has a gap into which purple coders fall right now, and it is rather unfortunate. I really do not see any downsides to purple individuals being in Div 2, because it is quite rare I think for any people around my level to even look at the Div 1 D and E problems. And while maybe for grandmasters to solve the Div2 A’s and B’s is insulting because of the simplicity of the problems, as a purple competitor I do not feel this way at all. Particularly looking at the upcoming contests right now and seeing 2 Div2 contests upcoming is rather frustrating, because I will only be able to compete out of contest, without affecting my rating, and because I know when a Div1 contest rolls around in two or three weeks there is a >30% chance I will not be able to solve anything, and will effectively sit out the contest. I realize that such a change should not be considered lightly, given that this has been the way things have been for 5 years almost now, and Codeforces popularity has rightly skyrocketed. However I think that there are strong reasons for this change that have become clear now, one of which is I feel rating inflation, along the lines that being top 200 in Div2 is enough to get bumped up to Div1, and also as competitive programming advances Div1 problems becoming harder. This combination I feel has put many people in situation where they move up to Div1 without having the tools at all to effectively compete. I thank anybody who read this, and also look forward to any comments and counterarguments that people have.

Read more »

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

By poikniok, 6 years ago, In English

So recently I have been trying a new approach to solving problems, which is whenever possible to implementing a quick brute force solution to a problem and then generating testcases with random numbers, and using the brute force solution to generate the answer to these testcases. While of course I can only generate tests with fairly small constraints typically relative to the actual input size, I have found that this approach catches a lot of bugs that I otherwise miss. I came up with this idea from watching Petr and Egor’s screencasts, as it seems they occasionally code up brute force solutions to test against when their submission fails pretests. Now of course I think there are some situations where there is no simple brute force algorithm, and therefore this is not possible. However I am curious if anybody else follows a similar approach during contests themselves, as I am curious if this is a scalable approach as one becomes better. Because while I am not particularly good right now this approach I think saves me more time hunting for bugs on average than it takes in creating the brute force solution. Anyway interested in any feedback, whether people think this is silly or otherwise.

Read more »

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