As you may know, Codechef long challenge is currently running. After the first one, I thought that I should just ignore it, but I've received a second ask for help with a problem from this contest...
Probably I'm not the only one being asked and that there may be more questions in the future. I'm always surprised by such questions. If you don't know how to solve a problem and you want to be able to solve it someday, then trying to cheat definitely won't make you such a person. What's their motivation if not just solving the problem (which makes no sense, because in this way you should just want to get better)? A bet with friends? Asking random people who are able to tell admins about this question is not a good idea then. Wanting to get a higher rating? Also stupid, you shouldn't get a rating to show that you are good, you should be good to show that you are able to get a rating.
Also, note that one of them was saying that he didn't ask for help because he didn't ask for any approach, while in my opinion asking for information which is not known for everybody is still cheating.
So, my question is how do you guys react in such situations. Here are my replies if somebody is interested.
Should I show their nicknames? Should just this blog and discussion be a way to show them that they should try to solve them by themselves? Probably it won't be the first discussion about it. I don't know, maybe making the world better is just a dream, but let me know what do you think in the comments.
Also, please note that I'm a bit irritated, as they used "question" instead of "problem"/"task".
There are many blogs on Codeforces, and most of them aren't very important a long time after publishing, like round announcements, saying "hello", asking for a better explanation of problem B than the one in the editorial, and so on. Among them, there are a few very interesting blogs that are a great resource of knowledge, like ODE by MiFaFaOvO, HLD by Vladyslav, suffix automaton by quasisphere or even Blogewooshes.
In my opinion, it would be great if there would be a special place for such blogs, accessible for example, by navigation bar, where they would be somehow sorted. It would be much easier to think "Let's learn something new!" and to do it. Also, probably Codeforces would have the greatest such base for competitive programmers. What do you think guys and MikeMirzayanov?
EDIT One more argument after thinking a bit more: of course there are a lot of papers, but everybody here knows that it's much easier for "us" to learn from blogs written by other competitive programmers. An example which comes to my mind: I've heard that parametric search sometimes isn't very popular in papers because it has something like $$$O(\log(limit$$$_$$$for$$$_$$$coordinates))$$$ and it isn't "proper" to have something like this in the complexity while ofc for us it's great and has a lot of usages. Competitive programming and paper-science differ a lot, so a base of knowledge for us would be great and we have a lot of it written and hidden, so why not organize it?
Can somebody tell me what's going on with Project Euler problems on HackerRank? Do they just steal the problems? Project Euler says that they ban everybody who spoils solutions to problems above 100, and it took me a few minutes to find a solution to one of the later problems with difficulty $$$80\%$$$.
I see a few options:
Maybe Project Euler doesn't know about it? -- Hackerrank isn't as quality as CF or PE, but still, I think that PE's admin would already hear about it, and it's big enough that it might look like a problem.
Maybe PE allows HR to take their problems? -- Of course, it's possible, but knowing the policy and rules of PE it looks very strange -- finding this code took was very easy, somebody just posted it in the comments section on HR.
Money? -- ???
The same admins? -- ???
Of course, everybody sometimes steals a problem, to use it in his/her school or university for example, but this looks like a huge process. Does anybody have any information? I'm just curious.
So, one person (we know who) was annually making a poll to choose the best problem of the year. I'd like to see the results of the voting, but there's no poll. Should we wait a bit longer or maybe can someone do such a poll.
OK, this might be a bit strange. Many people ask others "How to become a better programmer?", "How to become red in two weeks?" or "Can somebody explain to me the solution to problem B?" under the editorial with a beautiful explanation to problem B. My question will be a bit different.
It'll be about marathon problems, especially about Marathon Matches. I'm not so bad at it, I've been the best in my problem in Deadline24 eliminations a few times or so, but I'm much worse on long contests. Now, it looks almost impossible for me to win a Marathon round. I'm not sure how should I practice, there are many ways to practice normal CP, but marathons are different. You have to spend a lot of time on one problem to produce a good enough solution. Also, I don't know what am I missing — bad idea, implementation details, wrong temperatures (I'm still not sure if I anneal correctly) or if my code is simply too slow to check enough options?
So, is there any list of tips from people who are for example Red on TopCoder or are regular Marathon finalists? Some ways to know what am I doing wrong? Or maybe even some tutorials? Psyho, Milanin, mugurelionut, wleite, CatalinT, how did you guys become so good?
And yes, here it is, Radewoosh getting back to basics and asking for tips :P
Hello everybody! A new round is upcoming and I'm honored to be its author. The round will first appear as the onsite for Dasha.AI Code Championship and later we will hold a rated mirror. Everybody is welcomed to participate in Codeforces and I wish good luck for people in Saint Petersburg and Novosibirsk.
Using the opportunity, I want to thank:
Scoring will appear later.
Good luck and see you during the contest!
UPD1a: Scoring in div2: 500-750-1250-1750-2500-3000
UPD1b: Scoring in div1: 500-1000-1500-2250-(1500+1250)-3500
UPD3: Congratulations to the winners!
In the onsite competition in Saint Petersburg:
In the onsite competition in Novosibirsk:
As we all know, polygon is a really great system for the problemsetters. I have one proposition, which may make it a bit better.
After making an invocation with all the tests, if we add some tests in the future and rejudge this invocation, the new tests will also be included. That's really great and helpful. Things are different if we consider solutions. If we add a new solution, we have to manually remove each invocation and add it back with a new subset of solutions. In my opinion, it would be nice if new solutions would be added automatically to the invocations which have the option "all solutions" marked.
What do you think about it guys? MikeMirzayanov, can you consider this?
I'm not sure what's exactly happening right now. I know that a few (about 7) last SRMs was a series of fuck-ups, so I assume that people from marathons also aren't sure what should be done now. Can anybody from topcoder write any clarification?
We've been waiting more than two weeks for the systests for the first round (if I'm not mistaken). Are the current standings final? Is there any way to be informed about the news and know the current status?
There's some information that you wanted to make three stages of standard matches and three matches in each of them. Why is leaderboard showing stages numbered $$$2$$$, $$$3$$$ and $$$4$$$ and the fact that stage "$$$3$$$" had only two matches and stage "$$$4$$$" still had no matches... I'm not sure if the stage "$$$1$$$" is missing, or if you didn't manage to organize matches in stage "$$$4$$$". Or maybe just the leaderboard doesn't work? It would be nice to check stage dates in the "rules" section, but they are missing here too...
Fortunately, there are dates of the online rounds in the "rules" section. And they say that the second round is going to end tomorrow... Are you sure? Has it even started?
In conclusion, what are you planning to do now? Can you tell us some dates? Or at least guarantee that the marathon finals will take place this year?
Also, I want to ask about the new system. There is definitely at least an intention to go in the good direction, we already can use standard I/O, but will it go further? By further I mean just sending only one file like on any other platform, or letting us use standard I/O also on SRMs.
If you've already seen this task somewhere, I'd be grateful for the link.
You are given a string of length about $$$10^5$$$. There are many queries about intervals of this string and for each interval, you have to calculate the number of distinct subsequences (not necessarily contiguous) of this interval.
The solution builds a segment tree and keeps matrices in each node. Have you seen this problem?
Long time no see, right? So maybe it's a good idea to try to return to my blogs slowly. This time the blog will be about a trick, which usually isn't necessary to solve a task, but can be useful to make implementation much more comfortable.
Let's look at this problem. It is about some DP on a tree in which we have to use convex hull trick to improve the complexity. The task requires merging two convex hulls with "smaller to bigger" trick. I recommend you to read the statement before reading the rest of the blog (and the editorial if you don't know how to solve it).
Once, during one training, my team and I noticed something strange. I'll write a little bit later what it was exactly. The point is that after the contest we decided to investigate how c++ rand() behaves on our machines (we use Linux). So, we used a Berlekamp–Massey algorithm on the results of rand() taken modulo 2.
The result is shocking — the length of the linear recurrence is only 527! No, the results aren't cyclic, just the recurrence is short.
"Cool, but who cares? Just some random fact which I wouldn't notice and it wouldn't have any impact on me." — wrong!
We discovered it while solving a task which required calculating the rank of a binary matrix. We wanted to check something, so we just generated big matrix using rand(), which turned out to be a bad decision. As only the first 527 columns were, let's say, independent, the rest were determined by first 527 ones, so the rank didn't exceed 527, and we lost much time just wondering what's happening.
Moreover, if the number of columns is even, the rank is only 496 (for matrices big enough of course). Guess what's the length of the recurrence if we look only at every second value of rand().
Yep, you're right — 496. One can notice that 527 - 496 = 31 and that 31 divides 527! Illuminati!
If anybody can explain precisely what's happening for even number of columns, it would be great. Also, if anybody knows how does rand() look inside and can say a few words about it, it also would be great.
Hello coders! I hope that you are enjoying the New Year as much as me. To make its beginning even greater, Codeforces is going to host a contest and I will be an author of all tasks. Hello 2019 will take place on Friday.
Using the opportunity, I want to thank to:
The round will consist of 8 problems and you will be given
two and a half three hours to solve them. Yes, the round will be rated.
There will be no interactive problems, but if you want you can read this document anyway, it's always good to learn new things.
Good luck and see you during the contest!
UPD2: I'll be on the Discord channel after the contest, so you will be able to ask me about the problems.
UPD3: You're probably wondering what the statements will be about. I hope that it will be another great year for Codeforces. As it's the community that creates it, I decided to write statements about the people who already have or had their part in Codeforces' history. As I wanted to be objective, the statements will be about 8 people who triumphed the most times in CF rounds. Using the opportunity, I want to invite these 8 people to take part in the contest. Let's say that the first person who will guess the set in the comments wins some free contribution. Good luck!
UPD4: The round will be 3 hours long.
UPD5: The drain will be adjusted and the scoring will be 500-1000-1500-2000-2750-3000-3500-4000.
UPD6: The round is over, congratulations to the winners!
And to the first-to-solvers!
Sorry for the long break, but the last weeks of holidays and the first weeks of academic year took my attention. I hope today's trick will make you forgive me. :P
I invented this trick a few years ago, but for sure I wasn't first, and some of you already know it. Let's consider the following interactive task. There are n (1 ≤ n ≤ 105) hidden integers ai, each of them from range [1, 1018]. You are allowed to ask at most 103000 queries. In one query you can choose two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ 1018) and ask a question ''Is ax ≥ y?'' The task is to find the value of the greatest element in the hidden array. The checker isn't adaptive.
Unfortunately, this task is only theoretical, and you cannot solve it anywhere, but it'll turn out, that solution can be handy in many other, much more complicated problems.
Because after Round #507 sad men in suits visited me in my flat, this time I won't write about any task from the future. Instead, this blog will be about my own trick. I said "my own," but probably some of you have already heard about it or even figured it out, but I've developed it by myself, so I consider it as my own.
In particular, it's GEOMETRY TIME!!!. But please, don't escape already. I also don't like this topic so much, that's why I really like this trick. Let me tell you a story from one onsite Polish contest, which took place a few months ago. I was thinking about one of the problems, and I've figured out that I had to do some binary-search (on doubles) and then check if a set of half-planes has a non-empty intersection. The answer would tell me in which direction should I turn in the binary search.
Firstly, I grabbed my head, because I've never written an intersection of half-planes. I had my acm library with Errichto's codes inside, but my knowledge in usage of his part was limited to copy-pasting FFT and Rho-Pollard. Not only I, but also Swistakk figured out the thing about binary search and was trying to intersect half-planes normally, but he failed (we still aren't sure why, probably because of precision issues). Then, I reminded myself a task from eliminations to BubbleCup 2017 (you can find it here), which I solved with the mentioned trick.
It's time to continue the series of Polish tasks. I've decided to write about my own task one more time. Its name is "cook" (you can submit here). The task isn't very hard, but it uses cute (in my opinion) trick. The statement goes as follows:
There is a cook in a restaurant. He has n (1 ≤ n ≤ 106) orders which he must fill. Every order is a piece of paper, and all orders are speared on a spindle (sharp stick with pierced pieces of paper) in a fixed order which cannot be changed. Normal cook would just take orders one by one from the top of the spindle and fill them in this order, but the cook in this task has supernatural cooking powers and can combine orders to fill them faster. In particular, if at some moment there are k out of n orders still on the spindle, he can choose one of three options:
— He can take the topmost piece of paper and fill this order in time one(k).
— If k > 1, he can take two topmost pieces of paper and fill both orders in total time two(k).
— If k > 1, he can take topmost pieces of paper and fill these orders in total time half(k).
This task is interactive, so you should communicate with the library and ask it for values of one, two and half. You can ask as many times as you want and assume that the library works in negligible time, so your only limit is the time limit. Please, note, that when k = 2 functions one and half both fills only one order, but they might take different amounts of time. This same applies to other similar situations.
Also, the cook has an energy level, initially equal to e (0 ≤ e ≤ 106). He likes preparing food without any tricks, so whenever he uses the first option his energy increases by one. However, his half combo tires him very much, thus each time when he chooses the third option his energy decreases by one. Cook's energy cannot drop below zero at any time. Of course, we are asked about the minimum amount of time in which cook can finish all orders. Final energy level doesn't matter.
Last thing: memory limit is unusual because it's equal to 8MB.
This time I've decided to choose a task from my own contest which took place last April and was known as the Grand Prix of Poland. If you want to write this contest virtually in the future, then consider not reading this blog. If you've participated in this contest and maybe even solved this task, then anyway I recommend reading it, cause this task has many very different solutions, each of them being very interesting (in my opinion). It's also a reason why this blog is longer than previous ones.
I'll write about task C "cutting tree" (not uploaded to the ejudge yet :/). The statement goes as follows:
You are given a tree with n vertices (1 ≤ n ≤ 2·105). The task is to calculate f(k) for each integer k from the range [1, n] where f(k) is defined as the maximum number of connected components of size k which we can "cut off" from the tree. A connected component of size k is a set of k vertices such that it's possible to traverse in the tree between any pair of these vertices using only vertices from this set. Chosen components are not allowed to intersect, so each vertex must belong to at most one component.
All signs in the sky and on the ground indicate that you've enjoyed my first blog, so here is the second one. I've decided to choose a Polish task again, as there are plenty of interesting ones. This time we'll take a look at the "plot purchase" (you can submit here), which is a bit easier, but a few years ago I was very proud of myself when I solved it. The statement goes as follows:
You are given a square n × n grid (1 ≤ n ≤ 2000). In every cell, there is a number from the range [1, 2·109]. You are also given an integer k (1 ≤ k ≤ 109). A task is to find a subrectangle of this grid such that the sum of values in this subrectangle lies in the range [k, 2·k] (or report that there is no such subrectangle). Just print coordinates of its opposite corners.
The community wants so the community gets it! :D Here it is, my very first blog about tasks and algorithms. At the beginning I've decided to post my entries on codeforces, maybe I'll switch to something different if it becomes uncomfortable.
To pour the first blood I decided to choose a task from one of the old ONTAK camps. Task's name is "different words" (you can submit here). The statement goes as follows:
You are given n words (2 ≤ n ≤ 50 000), every of length exactly 5 characters. Each character can be a lowercase letter, an uppercase letter, a digit, a comma... basically, it can be any character with ASCII code between 48 and 122 (let's say that k is the number of possible characters). A task is to find all pairs of indexes of words which are . Two words are if they differ at all 5 corresponding positions. So for example words and are really different and words and are not, because in both of them the third character is . As there can be many such pairs (up to ), if there are more than 100 000 pairs, then the program should print that there are only 100 000 and print this number of pairs (arbitrary chosen).
Please, note that this task comes from the contest which took place a few years ago, so don't think about bitsets. :P