The classical problem goes as follows:

There are 100 numbered prisoners and 100 ordered boxes containing their numbers (1 per box). Each prisoner goes into the room with boxes alone and must open and look into 50 of them one by one. After leaving, all boxes are closed. A prisoner cannot reorder or otherwise modify the boxes. Each prisoner does this separately from the others and they can't leave any clues behind. The prisoners are allowed to sync on strategies beforehand.

The original question asks about the best strategy if the goal is for ALL of them to find their own number. The answer is to follow the permutation chains, i.e. look into the box that's labeled with their own number and then look into the box with the number they saw inside it and repeat. This gives >30% success rate for arbitrary $$$N$$$ boxes ($$$N=100$$$ in the example) because if there is no permutation cycle of length larger than $$$N/2$$$, all prisoners will find their number, and the odds of that happening can be computed and are actually bounded by a constant regardless of the number of prisoners.

You can read more about the classical problem here

Recently I came up with the following variation: What if we have the exact same setup but we want NO prisoner to find their own number. They're still forced to open 50 different boxes by the same rules, but if any of them sees their own number they are all executed.

Using the exact same strategy of following permutation cycles, the prisoners will only succeed if the permutation consists of a single cycle of size $$$N$$$. This happens in $$$1/N$$$ of the cases.

I and indjev99 spent quite a long time trying, but we could neither find a better success rate than $$$1/N$$$, nor prove that this is optimal. I couldn't find this variant of the problem in literature either. The proof that the solution is optimal in the classical case is not really applicable for the variation. Any ideas?

It seems that there's something wrong with the Gym. Attempting to create a new training results in:

"Ooops! Something has broken down in Codeforces. Do not panic, you can try to reload the page or return Home. Anyway we will carefully read megabytes of logs, analyze stacktraces and fix the problem."

with a "All your bug are belong to me" image.

I thought I could repurpose one of my existing contests, but that seems impossible as well — any FTP link of my existing gym contests gives "This site can’t be reached".

I'd appreciate any fix/workaround as I was hoping to set up a quick practice contest for friends of mine today.

Bump: Problem still persists. If for some reason this is happening only for me, I would appreciate any comment indicating that.

Greetings Codeforces community!

This March, CodeChef is celebrating 10 years of cooking delicious problems and I would like to invite you all to participate in the March Long Challenge, sponsored by ShareChat. The long challenge is a 10-day long contest with 8 problems for you to solve. This month, there are some additional birthday gifts up for grabs! For more details, head over to the contest page now!

ShareChat — India’s fastest growing social network is offering internship and job opportunities to participants of March Long Challenge. The contest and job opportunities are open to programmers across the globe and problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese. Visit the contest link to know more.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

• Admin: teja349 (Teja Vardhan Reddy)
• Tester: Enchom (Encho Mishinev)
• Editorialist: taran_1407 (Taranpreet Singh)
• Statement Verifier: Xellos (Jakub Safin)
• Setters: Abhinav Jain, adityad1998 (Aditya Dimri), aleex (Alexey Filinovich), Dalgerok (Andrew Orap), Ashishgup (Ashish Gupta), danya.smelskiy (Danya Smelskiy), kingofnumbers (Hasan Jaddouh), mgch (Misha Chorniy), KUMAR_PRANJAL_RAI (Pranjal Rai), Wild_Hamster (Volodymyr Mykytsei), yashChandnani (Yash Chandnani)
• Russian Translator: Mediocrity (Fedor Korobeinikov)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI
• Bengali Translator: solaimanope (Mohammad Solaiman)
• Hindi Translator: Akash Shrivastava

Contest Details:

• Start Date & Time: 1st March 2019 (1500 hrs) to 11th March 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
• Contest link: https://www.codechef.com/MARCH19
• Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
• Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://www.codechef.com/laddu
  (For those who have not yet got their previous winning, please send an email to winners@codechef.com) Good Luck!
  Hope to see you participating!!
  Happy Programming!!

Hello CodeForces Community!

We’re excited to invite you for the July Long Challenge 2018 sponsored by ShareChat. Join us for ten intense days of coding challenges! Joining me on the problem setting panel are:

• Problem Tester: Enchom (Encho Mishinev)
• Problem Authors: qoo2p5 (Daniil Nikolenko), ohweonfire (Sunli Chen), rajat1603 (Rajat De), teja349 (D Teja Vardhan Reddy), taran_1407 (Taranpreet Singh), (Zeren Li), scube97 (Shubham Sangamnerkar), AndrewB330 (Andrey Borzyak), Barichek (Ihor Baranblat), Reziba (Abizer Lokhandwala), i_am_groot_ (Anuj Maheshwari)
• Problem Editorialist: adamant (Alexander Kulkov)
• Statement Verifier: Xellos (Jakub Safin)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: VNOI Team

And special thanks to mgch (Misha Chorniy) for coordinating the contest preparation!

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 6th July 2018 (1500 hrs) to 16th July 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/JULY18

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie.
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!
Hope to see you participating!!

Three months ago I got second place in the March Long Challenge on CodeChef. It took quite a lot of my time and falling behind on some uni work to do that, but I thought that if I manage to grab a top2 prize, it'd definitely be worth it. The second place prize for long challenges is $300, so I was quite happy with my achievement.

From there on, trying to actually get the prize has been extremely annoying and so far unsuccessful.

I waited for about 20 days with no news from them at which point I sent an email, but got no response for a week. I asked on here in a blog on what I should do. The only comment advised me to contact them on Facebook and so I did. They said that they will check it out and within a day, on April 4th, I got an email telling me that I've won and asked me for my Paypal info, which I immediately sent .

Of course, no response or prize for another 20 days. I sent a follow-up email on the 23rd of April to ask about it, and received an email on the 25th, assuring me that they're having some technical problems and the prize should be there by a week.

As you can already guess — no sight of the prize in a week. I send a follow-up email on 11th of May — no response whatsoever. Another one on 21st of May — no response as well.

Finally last Thursday (31st of May) I sent them a message on Facebook, as that had worked last time. Alas, no response or prize as of the time I'm writing this.

So I just want to ask if that's just a common practice? It seems ridiculous to me. Nobody forces them to announce cash prizes if they do not intend to give them, and any "technical problems" reasons are just crap. A company cannot successfully send $300 through Paypal for 3 months already? Seriously, they've been having those long challenge rounds for years now, one would really expect the process of sending prizes to be played out enough times not to mess it up.

If it's a common practice for them to act like this, making me feel as if I'm trying to get money from a scammer, they should really be shamed about it.

Finally, I'd love to say that I'm pissed off because of principles and the money does not matter, but that's a lie. I'm a student with high enough tuition and the main reason I spent so much time doing the long challenge round is the cash prize.

UPDATE : I received my prize within a day of this post. This leads me to believe that the main problem is perhaps communication. I am thankful for the quick reaction of the admin and apologise if the post was too harsh.

Last month I got second place in CodeChef March Challenge. The prize was $300 for second place, but I still haven't been contacted. I wrote to winners@codechef.com over a week ago with no response.

I don't really mind waiting more, I would just like to ask if someone who has received a prize can confirm that such delays ( month) are normal for CodeChef and to confirm that they do really give the prizes.

Hello everybody,

Today was the practice session of CEOI 2016 and the following interesting problem was given:

You're given N distinct integers. Print the maximum sum you can get by adding two of them that are coprime.

N is up to 100,000 and all the numbers are between 1 and 500,000. Time limit is 1 second, memory limit is 256MB.

Some solutions passed but most of them were using some odd tricks with unclear complexity. I was wondering if some neat solutions exist?

Hello everybody,

I've been practicing for a while now with some old competitions and, as you know, many of them are not uploaded on any online judge so you have to test your solutions by yourself. For this purpose I use Codeforces Gym and prepare the problems in Polygon. The trouble comes from the fact that not all of the competitions provide model solutions. Most of them give the test data, but it is in the form of input-output files and from what I've managed to understand — Polygon wants a model solution to generate output files.

My question is : Is there a way to prepare a problem in Polygon by manually uploading the correct outputs of the tests and having no model solution?

Thanks in advance!

Hello everybody,

As most of you know recently the June long challenge in CodeChef finished and I want to bring attention to one specific problem — Chef and cities. Roughly the part of the solution that is difficult to come up with can be summarised as:

"You have an array of N integers and you have two types of queries — update some integer or ask about the first digit of the product of all numbers." (The original problem has more details but they are solved trivially)

I was eager to see some real solution (unlike cheats with double values) so I checked the author solution and to my surprise it did something very simple — it calculated the log of the product and used it to find the first digit.

Now this is okay in theory, it is okay in mathematics — but my first thought was 'what about precision?'. Surely if you have some tricky number then you might get some precision error and since you're looking simply for the first digit — there's not relative error allowed. So I quickly came up with the following test:

9
3 3 11 41 101 271 3541 9091 27961
1
2 1

You can confirm yourself that :

3*3*11*41*101*271*3541*9091*27961 = 99999999999999999999

And unless I've missed something crucial it seems that it's a valid test. However all three solutions provided by the author in his analysis ('Setter', 'Tester', 'Editorialist') would print 1 as a first digit, just as my cheaty solution with double values does.

This test is incredibly small given the constraints. You have integers with values up to 10⁹ and up to 10⁵ of them. This allows the product to contain thousands and thousands of digits, making me seriously doubt any solution based on floating point numbers.

I was wondering if a proper solution even exists at all? Am I overlooking some constraint or just missing something or is the author solution plain wrong?

So I was away for a couple of days and I come back to this :

......

Hello everybody,

I was playing around testing stuff with Collatz conjecture and I got the idea of a simple generalisation:

0) Pick a natural number

1) If the number is divisible by A, then divide it by A,

2) otherwise multiply it by B and add C.

3) Repeat 1-2 with the new number.

Will we always reach value 1 regardless of the initial picked value? According to Collatz conjecture we always will for A=2, B=3, C=1.

The generalisation has some constraints such as B + C ≥ 1 and A, B > 0 (so we can ensure that we stay in positive numbers) and also ignoring triples (A, B, C) such that B and C are both divisible by A, as such triple (A, B, C) is obviously gonna behave the same way as (A, B / A, C / A).

Now I wonder about triples (A, B, C) that fulfill the Collatz conjecture idea — you always end up at 1, let's call a triple that fulfills that a Collatz triple. I wanted to see if there are other Collatz triples (not prove, obviously, but experimentally check for computable values) other than the well-known (2, 3, 1).

However, as we increase the numbers they start to blow-up easily and overflow a lot, so I managed to get results for very few triples, and didn't find any new Collatz triple, so I was wondering if somebody has done a similar experiment and maybe found any?

Wikipedia briefly mentions this generalisation in 'Undecidable generalisations' claiming it's an algorithmically undecidable problem to determine whether the values always reach 1, but if I'm not mistaken this doesn't mean that other triples don't exist.

Collatz conjecture isn't one of the most useful ones but I like its simplicity so if somebody has done experiments of their own or knows some interesting published ones, I'd be glad to see the results.

Thanks in advance! :)

Hello everybody,

Today was the second day of RMI(Romanian master of informatics) and I participated onsite. It took me a couple of hours to solve two of the problems and then I had whole three to tackle the last one. Alas, it turned out to be too difficult for me to get more than 10-20 points.

The short statement of the problem is simply :

Support 2 types of queries on an array of size N:

1) Given "L R" find greatest common divisor of all numbers from index L to R, that is gcd(a[L], a[L+1],..., a[R])

2) Given "L R k" update the array in the following way:

a[L]+=k

a[L+1]+=2*k

...

a[R]+=(R-L+1)*k

There are up to 100,000 numbers and queries with time limit of 1s and memory limit of 128MB. The initial numbers are up to 200,000,000 and in each query of type 2 we can have k up to 200,000,000 (resulting in numbers becoming as big as 10^18).

Query problems are usually my favourite but I couldn't come up with anything here. The queries just seem very different. If someone has some solution, please share.

Hello everybody,

It often happens that I have to multiply polynomials quickly and of course FFT is the fastest way to do so. However, I've heard that FFT can have precision errors. I'm not very familiar with the mathematical theory behind it, so I was wondering how can I know whether precision errors will occur and what to do to avoid them. I've also heard about NTT (Number Theoretic Transform) which is similar to FFT but it works with integers only (using modular arithmetics?) but I don't know much about it.

So my questions are :

1) How can I know whether regular FFT using complex numbers would give precise errors, what does it depend on?

2) Is there somewhere I can read about NTT and how it works. I don't have strong mathematical background so something more competitive-programming oriented would be perfect. Additionally, is NTT always precise?

3) Could someone provide quick and simple implementations of FFT/Karatsuba/NTT of simple polynomial multiplication? I've written FFT and Karatsuba before, but my implementations were so bad that they were often outperformed by well-written quadratic solutions.

I do know that these questions were probably asked before so I apologize beforehand. I tried to google but most things I found were math-oriented.

Thanks in advance :)

The second day of the Balkan Olympiad in Informatics has finished and the competition went pretty smoothly, there was a minor bug in the tests of the second problem, but it was fixed quickly.

Final results

The tasks in the second day were, in my opinion, more interesting than the first day. Once again here's a link with the problems (from both days):

Tasks

Clarkson

This problem was quite interesting and the solution was based on a suffix structure. Both suffix array and suffix tree were good enough to solve the problem, and building them for O(N log N) or perhaps even O(N log^2 N) was sufficient. The structure was used so you can calculate the function:

F[i] — the largest substring in the first string, starting at index i, that is present in the second string.

After this function was computed, binary search for the answer combined with dynamic programming was enough to solve the problem in O(N log N), making the total complexity O(N log N) assuming the suffix structure is built fast enough.

Fun fact : I actually practiced my suffix trees right before the first competition day as the last BOI had a problem that involved suffix structures and I wasn't able to solve it because I couldn't build a suffix tree/array, and I was worried it might happen again :)

Radio

This was the hardest problem of the day and one of the best in the competition. Here is my solution in summary:

Let's imagine each tower as a segment [X-P; X+P]. Obviously our goal is to increase the P of the chosen subset in such a way, so that each pair of chosen intervals will overlap or touch. It is easy to see that this means that all of the chosen intervals will have at least one common point, that is, there will be a point that belongs to all intervals. Let's call this the "middle" point. Fixing the middle point gives an easy linear computation of the cost.

This gives the idea for solution with N=K. However we can't try all 10^9 positions, so we have to make the following observation: It is sufficient to try interval endings to be middle points. I will not prove it, I believe it is easy enough to see. This gives us straightforward O(N^2) solution.

To speed it up we can break down intervals to beginnings and ends, and process them as events going from left to right. Keeping some proper values, one can easily speed it up to O(N log N) in total, which gives 45 points (subtasks 1, 2 and 4).

For subtasks with Si=1, I am not sure what the intended solution was, but from what I understood it has to do with finding a median point as it will always be the best choice for a middle point.

Finally, for the final subtask one again has to process endpoints as events from left to right, however keeping a few priority queues is necessary. I call "active" those towers that I will preserve, and "unactive" those that will be sold. Then at all times I keep 4 sets/priority queues:

1) RightUnactive — all unactive towers whose beginning hasn't been processed

2) MiddleUnactive — all unactive towers whose beginning has been processed, but whose ending hasn't

3) MiddleActive — all active towers whose beginning has been processed, but whose ending hasn't

4) LeftActive — all active towers whose both beginning and end has been processed

It turns out that after processing a new endpoint, only a few changes can occur in those sets, and the sets can be easily updated if they are sorted in the right way. I will not go into details as my solution was quite long. The total complexity should be O(N log N) and worked in 0.2s on the largest testcase.

Tiling

Finally this was a tricky problem if you wanted to prove your solution. The crucial observation was that you had to break the grid into L*K squares of size NxN, and query once in each (I'm not sure if it mattered which cell in each square, I used center cells) and then the answer always gave an unique solution and was minimal in respect to queries. Proving that is difficult as far as I know, but it wasn't necessary, quite a few people managed to find out that these are the optimal queries.

Probably the harder thing was actually finding the tiles' layout. I used backtracking with optimizations so that some "obvious" tiles were put before the backtracking, but sadly I spent too much time on problem 2 and couldn't finish my optimizations, hence 70/100.

The surprising thing was that the intended solution was a quick way to place the tiles without backtracking (as backtracking should be exponential?), but almost all competitors managed to pass with the backtracking. I do not know the quick way so maybe someone can find out how it works?

Medals distribution will be announced tomorrow at the official closing ceremony, thanks for reading :)

Hello everybody,

The annual Balkan Olympiad in Informatics is being held in Ruse, Bulgaria and the first day has just passed. Every year I post the problems and my solutions/thoughts about them, but this year the organisers were kind enough to upload the problems themselves, so here are the tasks.

Circus

The first problem actually turned out to be the hardest. The problem has a few quadratic complexity solutions that take up to 51 points and can be found easily. Only one person had 100 on this problem, and only two others had more than 51 (having 82). The solution of all three was similar and was a bit "risky" as it relied on an unproven fact — the path will change direction very few times. As it turns out, the path has the general form of "go right for some time — go left for some time — go right". This is not proven but I couldn't find any tests disproving it (any ideas of why is it correct would be nice) and it seemed to give full score if an idea based on it was implemented nicely.

The actual solution was to run a Dijkstra algorithm starting from position M, and for each rope to calculate the minimum distance that you can hold on to it and still be able to reach the final. The trivial implementation is O(N^2) as you may have to consider all N^2 pairs, but it turns out that there is some way to optimize it and make it somewhere around O(NlogN). There is no analysis yet, so this is the vague idea I understood.

I got 51 points on the problem as I couldn't come up with anything better than quadratic complexity.

Happiness

This problem was solved by about 8-10 people. The solution wasn't very difficult — one had to notice that a problem might occur at such i, that A[i]>2*A[i-1]. As the numbers were up to 10^12, you could have at most log 10^12 such points, and you could easily check whether each one is a problem in O(log) per check, making the total complexity O(log^2) per query.

As far as I know, one could implement O(log) per query complexity solution using Balanced Binary Search Tree, but it wasn't required. I scored full score with an O(log^2) solution.

TTT

This problem was the easiest. It is not hard to see that the grid quickly becomes smaller and there are not too many valid states, so simply brute-forcing them all with some memoization could solve all test cases instantly. I also managed to get full score on this problem.

In the final ranking Hristo Venev (Bulgaria) and Marko Stanković (Serbia) got 1st place, both with 282 points. Looking forward to day 2 :)

Hello everybody,

Just now I learned max-flow-min-cost algorithms and of course, my first thought was "great, now I don't have to know the Hungarian to solve the assignment problem", but then I stumbled upon the sentence "the Hungarian algorithm solves the assignment problem much faster".

So I looked around the web for good explanation and I found about a couple of thousand links to this Topcoder article, however for some reason it is not working for me. I do not know if it's a problem on my side or the article is just taken down.

I wanted to ask if somebody has the article saved or perhaps has another good article on the Hungarian algorithm with possibly both O(N^4) and O(N^3) complexities explained.

Thanks :)

Hello everybody. So I was really bored tonight and looked at so many comments being like "sorry_dreamoon is X" and then people arguing and disagreeing. Since I had nothing better to do, I decided to finally unravel the truth of who he actually is. Here is the full case and how I actually got to him, hope you enjoy! :D

Selection

Let's start by the obvious. He managed to get first place in Div2 and he got second in Div1 (would've been first if the scores were static). So what we know is that he is really good.

Let's look at the past 10 Div1 contests. It turns out that only 8 times it happened that someone with a rating of less than 2500 got in top5. This is 8 times out of 50 people being in top5. But he was second and almost first, so he is better than that.

It turns out actually, that in the past 10 Div1 contests, only 2 times it happened that someone with rating less than 2500 got in top3.

Combining this information with sorry_dreamoon's confidence and great results — we can assume that his rating is 2500+. That leaves us with 76 suspects.

Reducing the suspects

As pointed out a few times, the obvious way is to remove all people that participated in CF rounds #284 and #292, as those are the rounds sorry_dreamoon participated in. Obviously it's hard to perform well on two accounts, so we can be sure those people are not him. Removing those from our suspect list we are left with 36 suspects.

Reducing the suspects even further

As you can notice from the blog post of round #292 dreamoon_love_AA invited sorry_dreamoon to participate 26hrs ago (as of when I was investigating) and the respond (top comment) was almost immediate. This shows that our suspect was browsing codeforces at the time. And since the account was initially made only as a one-time joke, he most likely was browsing from his real account.

So from this, we can remove all our suspects that havent logged in the last 26 hours.

Well, believe it or not, we're down to 18 suspects!

The final conclusion

Now here the things start to get a little bit tricky. But imagine the following scenario:

You create an account with the only purpose to be first in a competition. If you fail, it will be somewhat embarrasing. While you want to keep your identity private, you want to be as good as you can. Would you use your primary programming language?

For me at least, the answer is absolutely yes. If you are used to a language, then your maximum performance is with that language and changing it is incredibly risky.

While not certain as the other two methods of eliminating, this method is still logical — "there is no good investigation without some assumptions".

So, sorry_dreamoon is using Java. Guess how many people from our 18-people-long suspect list use Java? That's right, you got it — 1!

And who is it... inserting drum roll

qwerty787788

Not convinced yet?

You know, when we try to mask our code we would usually change names of variables and functions but the structure and the way your thought goes is hard to change. So, it turns out that sorry_dreamoon has a code including maximum flow — 9251954.

It turns out that qwerty787788 has maximum flow too, in the recent Rockethon — 9762794.

So, looking at the function that actually does the flow you can see the following:

qwerty787788's code :

class Flow {
	int n;
	ArrayList<Edge>[] g;

	Flow(int n) {
		this.n = n;
		g = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			g[i] = new ArrayList<>();
		}
		q = new int[n];
		h = new int[n];
		cur = new int[n];
	}
etc

And this is sorry_dreamoon's code :

static class Flow {
        int n;
        ArrayList<Edge>[] g;

        Flow(int n) {
            this.n = n;
            g = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
            q = new int[n];
            h = new int[n];
            cur = new int[n];
        }
etc

What is the difference? It's literally the word "static".

This is just a small fraction of the flow class. About 90% of it is completely identical.

Conclusion

To be honest I really liked the mysteriousness of sorry_dreamoon but I really had nothing better to do tonight and since I really wanted to live my detective-dream, I hope everybody takes my work with a smile :)

P.S.

And in case dreamoon_love_AA hadn't figured that out by himself yet, I hope it helps him sleep better at night :D

P.S.S.

I hope this doesn't bring any problems to qwerty787788 since he is a very good coder and I think we all can agree that this was a very well carried out joke (though technically my "logic" isn't a solid proof that it's him at all)

So I recently decided to create some Gym contest (for my friends) using polygon. I have encountered a few problems and if someone could please help me out or link me to detailed polygon help, that would be fantastic.

1) Naming the actual problems. As stupid as it may sound I couldn't find how to name the problem. In the statement itself it appears with the name I've chosen, but when you open the contest, this is what you get:

2) Sample input/output tests. In the statement section I found how to add Input/Output descriptions, Notes descriptions and general statement description, but not how to add sample tests in statement. Solved thanks to EROR

3) Changing an already created problem. When I upload the problem to codeforces contest and afterwards change it in the polygon system, I couldn't find a way to update the actual problem in codeforces. It changes fine in polygon system but it keeps the originally uploaded version in codeforces itself. Solved thanks to EROR

4) Using pictures in statement and better fonts/bolding/etc. Writing the statement seems to allow only simple text and not even bolding the text. I see an option to add pictures as resource but I don't have clue how to actually use them afterwards, so some help with that would be amazing. Solved thanks to EROR

Edit 5) Is there a way to change the view to HTML view and not PDF view? I believe it looks better, but by default it opens PDF view when I click on the problem in cf. Also pictures don't seem to work in PDF.

Update:

Names of problems are still not showing up and pictures don't seem to work in PDF format, but I'm unable to change the statements to show up in HTML format. Those 2 problems are still unresolved, so any help is welcome!

Update 2 Thanks to EROR pictures in PDF now work, so blank problem names seems like the main problem.

Sorry if these questions sound dumb, but I couldn't find a good way to solve them.

Thanks in advance! :)

Hello everybody,

Recently I faced yet another problem and I thought asking the codeforces community is the best decision.

Lately I've been learning Ukkonen's algorithm for linear building of suffix trees. However as I was reading some applications I noticed that often you have to build a generalized suffix tree of usually 2, but sometimes more strings. In the papers about Ukkonen's algorithm I managed to find only how to build a single suffix tree.

Now my initial thought was to build a suffix tree for each string and then try to merge them in linear time, but that seemed like a very annoying to implement idea and looking around the web many people said that Ukkonen's algorithm can be used to produce generalized suffix tree.

I was wondering if someone could outline a solution that keeps the structure and suffix links correct and builds a generalized suffix tree based on Ukkonen's algorithm.

Thanks in advance! :)

Hello everybody,

Sometime ago I learnt FFT and its application in multiplying numbers. I never understood completely how it works but I sort of understood the way it multiplied numbers.

Now lately I've heard friends of mine talking about FFT and using it in places I couldn't possibly imagine how would FFT help. I'm having trouble understanding what does FFT compute at all. Wikipedia talks about complex sinusoids and I've tried understanding it but I just jump from a huge article to another and get lost in countless definitions and equations.

A classic example of what I mean is the following problem. The editorial talks about FFT but I can't even comprehend what it is saying.

Now I know that FFT involves quite serious mathematical theory that I most likely don't know, since I'm only 10th grade, but as I'm competing quite actively in many competitions I thought that understanding it is quite important.

I would be extremely grateful if someone could help me out in understanding what exactly is this algorithm doing by explaining or pointing me to a place I can learn it from. While Wikipedia often has tons of information, it often lacks simplicity and learning from it directly can be really tough.

I am looking for an explanation that would help me understand the concept and idea of the algorithm, and not code or implemenations.

Thanks in advance :)

Marathon24 finished a few weeks ago and my team has received a chance to go to the Grand Finals. However reading carefully the rules described, I saw the following thing :

Communication is realized with text commands sent through the TCP/IP protocol, described in details in the problem statement.

I also checked problems from last year and indeed, they give you a set of commands you can send through TCP/IP to communicate with the contest system.

Now the problem is that none of our team has any clue how this whole TCP/IP communication works. I would really appreciate it if someone could explain how it works and how to create a C++ code that communicates through TCP/IP, as I believe that's what you are expected to do during the competition.

Thank you in advance! :)

Edit: Turns out we can't participate due to complications with travelling, however the question is still valid! :)

Hello everybody,

As the new school year is apporaching I started creating some personal training competitions for me and friends, and as usually I used codeforces gym as it is very easy to use, however I can't seem to upload any contest on there. The wizard can't connect and manually opening the FTP still doesn't connect, so I'm supposing it's down. This has happened before and it got back on in a day or two, but I was just wondering why does this even occur and is there a way we can know when will it be back up?

Obviously the website functions alright at the moment, but the FTP doesn't. What could be the cause of that and how often does that happen?

EDIT: Started working now, still wondering what causes those periodic stops?

EDIT 2: And it's down again and then up again..

Thanks in advance! :)

Hello everybody,

About an year ago I participated in a competition and I did pretty badly and I didn't look at the problems for a while. Recently I tried to solve them and solved one of them, but the other, I just couldn't solve. I've tried for a while but can't come up with anything good enough, so I'd love some help. Here is the shortened statement:

You are given a square of size N (1<=N<=20,000) and a list of M (0<=M<=200,000) cells that are dark, all other cells are bright. The problem is to calculate the sum of all areas of rectangles that are of the same color. That is, output the sum of all rectangles in the initial square grid that are fully dark or fully bright.

Print the answer modulo 10^9+7, since it can be very large.

Input format : N and M on one line, followed by M lines describing the coordinates of the dark cells 1-based.

Sample input:

4 6
1 2
1 3
2 1
2 3
4 1
4 4

Sample output:

58

There are 6 dark rectangles 1x1 and 2 dark rectangles 1x2 and in total area of 10 of dark rectangles. The total are of bright rectangles is 48, so in total 58.

I'm struggling to find any good solution, the format of the competition is to give output files for the given input files, so I suppose something like O(N*N) or maybe even O(N*M) could be the intended solution.

Thanks in advance!

Hello everybody,

Lately I've solved a few problems that include the number of divisors of N in their complexity. Now I'm a person that loves to know exactly the complexity of his algorithms so I tried to look around the web for the values and I read from wikipedia the Divisor Function page, but I couldn't find what I'm looking for (it might've been there, I had tough time understanding most of their explanations).

So suppose D(n) is the number of divisors of n. I'm looking for a good bound on D(n) expressed using n.

Note that it is very easy to see and prove that D(n)<2*sqrt(n), but I did some tests and I believe a stronger (not much stronger but still stronger) bound should exist. Sorry if the answer is already described somewhere online, I had tough time finding it.

Thanks in advance!

Hello everybody,

I like participating in Marathon-type competitions and in the near future I will participate in a few more. However I feel like my solutions are always not good enough. I've been to a lecture of Psyho where he explained some approaches. I know in theory things like Beam Search, Simulated Annealing, Hill climbing. However when I face a marathon task I really have a hard time to choose which one to use and more importantly, how exactly to construct it.

Take a simple NP-Hard problem as the Travelling Salesman. I have no clue how to solve it using any of the above techniques, and I would probably end up using some randomized short backtracks, which would end up with a horrible score.

I would be very grateful if someone could give me some tips, and perhaps explain some not-too-hard approach for the Travelling Salesman problem, so I can learn from that.

Thanks in advance! :)