I was trying to add yesterday Google Code Jam qualification round to the gym and decided this time to avoid typing in statements myself and print them from website to PDF and attach to the contest. I thought that I'll be able to create a contest with statements in attachments easily and get contest like 2009-2010 Petrozavodsk Winter Training Camp, Moscow SU Unpredictable + SE + old ST Contest for example. It turned out that I have no idea how do that.

What I did:

1. Created regular contest in Polygon with checkers, tests, solutions, etc but with no statements.
2. Created a gym contest and added polygon contest's descriptor through FTP.

This creates a contest but there are two issues about it:

First of all I had no idea how to attach PDF statements. Eventually I was able to do that using Codeforces Contest Wizard in update mode using a link in gym contest. This Java tool is not that intuitive to use but I was able to upload my PDF document eventually and specify that this is English statements. Is there easier/better/other way to do that?

Secondly, my problems in gym have no name, usually I specify the names as part of the statement in the Polygon but since I had no statements in Polygon I had no names as well. I tried using Contest Wizard to solve this issue as well but the only way I think I found to do that requires uploading all problem data (checker/tests/etc) which I'm not going to change and don't want to bother getting that again assuming that Polygon already created everything.

If somebody wants to help me with that I can give an access to the gym contest, but I would be grateful for an advice as well.

I'd like to inform you that on 30th of June on Coursera will start second session of Tim Roughgarden's "Algorithms: Design and Analysis, Part 1" course. I took first session of this course a couple of years ago, in fact this is a source of my initial knowledge about algorithms and data structures and I started taking part in competitive programming contests soon after finishing second part of the course. I would definitely recommend taking it, I'd say that it should be interesting and useful for CF green & blue rating zone coders. The course consists of video lectures, quizzes and programming assignments (it's not a pure theory class) and will take approximately 4-8 hours per week to finish it successfully.

To give you an idea on topics covered by this course, let me just copy the course syllabus here:

Week 1: Introduction. Asymptotic analysis including big-oh notation. Divide-and-conquer algorithms for sorting, counting inversions, matrix multiplication, and closest pair.

Week 2: Running time analysis of divide-and-conquer algorithms. The master method. Introduction to randomized algorithms, with a probability review. QuickSort.

Week 3: More on randomized algorithms and probability. Computing the median in linear time. A randomized algorithm for the minimum graph cut problem.

Week 4: Graph primitives. Depth- and breadth-first search. Connected components in undirected graphs. Topological sort in directed acyclic graphs. Strongly connected components in directed graphs.

Week 5: Dijkstra's shortest-path algorithm. Introduction to data structures. Heaps and applications.

Week 6: Further data structures. Hash tables and applications. Balanced binary search trees.

There is a second part of this course as well which covers greedy algorithms, dynamic programming and NP hard problems, I would recommend taking it as well but it turns out that there was a session of it which finished recently, I don't know when they will schedule the next one but I guess you can still watch the lectures.

I have written a bat script for Windows to automate a bit testing DCJ solutions on multiple examples, putting it here, might be helpful to somebody. I've written it to test C++ solutions but in case you write in other languages you should be able to change it easily.

script itself:

echo off

set PYTHONPATH=C:\Program Files (x86)\Python27\
set DCJ_PATH=c:/Temp/SP/DistributedCodeJam/dcj/dcj.py

cls
for %%* in (.) do set TaskName=%%~nx*
echo %TaskName%

for %%f in ("%TaskName% (*).h") do (
	echo ----------------------------
	echo %%f
	copy /y "%%f" %TaskName%.h > NUL	
	copy /y "%%f.out" expected.out > NUL
	for /F "delims=" %%i in (expected.out) do echo EXPECTED: %%i

	"%PYTHONPATH%\python.exe" "%DCJ_PATH%" test --source=solution.cpp --nodes=3
)

There are two path variables on top, don't forget to set them appropriately.

Here is an output for sandwich problem:

Sandwich
----------------------------
sandwich (1).h
EXPECTED: 14
STDOUT 0: 14
Duration: 15.6001ms (longest running instance: 2)
----------------------------
sandwich (2).h
EXPECTED: 0
STDOUT 0: 0
Duration: 15.6001ms (longest running instance: 1)
----------------------------
sandwich (3).h
EXPECTED: 5
STDOUT 0: 5
Duration: 31.2002ms (longest running instance: 0)
----------------------------
sandwich (4).h
EXPECTED: 50
STDOUT 0: 50
Duration: 15.6001ms (longest running instance: 2)

How to make it working:

1. Download sample libraries from DCJ Dashboard. I download them with Google Chrome to the same folder all at once, so they get names like 'sandwich.h', 'sandwich (1).h', 'sandwich (2).h', etc. The script assumes that all input files have names matching 'PROBLEM NAME (TEST_CASE).h' pattern, to do that I simply download first input file twice so it becomes 'sandwich (1).h'.
2. Copy all 'sandwich (*).h' files to the same folder where your solution is.
3. Put this script to the same folder, change path variables in the script.
4. For each *.h file create an expected output file appending .out extension to it. So expected output for 'sandwich (1).h' should be at 'sandwich (1).h.out'.
   

That should be it and you should be able to run the script and check all testcases in one run. It is assumed that you already made DCJ tool running on your PC in advance.

I'd like to start a discussion on how CF community is involved or at least notified about the changes happening in CF and in CF API in particular.

It seems that there are people more or less constantly working on implementing some new features on CF. And sometimes we can see blog posts from MikeMirzayanov or somebody from CF team highlighting a list of changes which happened during some period, but these posts are very rare, they are published like once or twice per year, while it seems that we have something changed almost every month. CF has very strong community, some people from the community do something on their own built on top of CF web site or CF API (submit solution from command line, VIM plugin, my CF achievements project). For all of us it is critical to be aware of changes happening on CF. For example this submission script stopped working after CSRF security fix. Another example I found today: since it's launch CF API had a bug that when retrieving hacks hacker and defender were swapped, turns out this was fixed several weeks ago. My achievements web site relies on retrieving hacks through CF API, so I had a workaround to swap them back, and turns out it's broken for several weeks because there is no need to swap hacker&defender anymore. Of course I can blame myself in this as well, I should have implement a check because I expected that CF will fix the bug at some point, but still I think it would be great if CF administration could inform us about such changes happening (hopefully in advance of course).

So my main concern is that CF community is not informed well about some important changes happening on CF, it makes it harder to do something on top of CF if you are not even aware when API is changing or some bug is being fixed. I'm not sure how it should be handled though, CF blogs do not seem to be a good solution in this case because they get almost no attention as soon as they go off the 'recent actions' list. Also major part of the community might be not interested in these updates. I'm not asking to implement something for this particular purpose, even simple mailing list will work fine for me.

Another point similar to the one I discussed above is that it's not clear how community can affect the development of CF API. Obviously CF API is implemented for the community so we should have a way to tell CF what we actually need. For example while working on CF Achievements site there were several places where CF API was not enough to grab all the data I need and I wanted to inform CF about it, but I don't what's the best way to do it:

1. PM to Mike? Quite often he might be busy, might not have time to respond, etc. Also again it leaves the entire community uninformed. Some other people in community might also need similar features so it doesn't seem to make sense to discuss this topic in PM.

2. Ivan's introduction of CF API blog post? But it's quite old, I don't think anybody from CF team monitors it, Ivan is not working in CF anymore.

3. Create a new blog post? Also doesn't seem to be a good option. It will be lost as soon as it will go off 'recent actions' list, it might be unnoticed by CF team.

Again, I'm not sure what is the best option to handle it, but something like issue tracker should do it well.

So I want to discuss this topic here both with the community and with CF administration. It might be a case that community is happy with the way it is right now, in this case I'll just switch back to PM'ing CF administration :-)

Я вот захотел поучаствовать в OpenCup (территориально: Киев), что мне надо сделать, чтобы попасть на площадку?

Я нашел только этот список за старые года на сайте opencup: http://opencup.ru/index.cgi?data=ocd/regions&menu=index&head=index&class=ocd&ncup=ocd. На указанные там Киевские email-адреса гугл письма отправить не может, сервер получателя их возвращает обратно.

Вопрос: кто виноват и что делать?

UP: Вопрос еще не решён, указанные в комментариях участники не смогли помочь.

Hi!

I'd like to introduce my project to Codeforces community. My project's name is 'Codeforces achievements' and as you can probably guess it is about achievements! Your achievements on Codeforces site. For those who do not like my long posts I should mention that the link to the site is at the end of this post.

Introduction

Last summer I left my last job, so I have quite a lot of spare time which I could invest in my hobby. Also I decided to learn something more or less new for me (for last several years my job was to write desktop software for Windows), so I decided to put my hands on some modern popular web-framework. At that point I chosen Python and Django, cause it was matching one position I applied. So I had a time and I wanted to learn Django. The best way to learn something is to practice in it, so I started looking for the idea for the site to create (didn't want to write yet another forum engine). Luckily at that point I ran into I_love_Tanya_Romanova's comment:

System> tourist unsuccessfully challenged LeBron's 250-point problem.
Achievement unlocked:)

That was it! I like the idea of achievements in the games and I decided that I want to something similar for Codeforces. That achievement Bohdan mentioned in his comment became the first achievement I implemented in my CF-achievements.

Achievements

The original idea was to have more funny & unusual achievements and less hard time-consuming achievements like 'solve XXX problems'. I think I didn't really succeed in that, there are not that many achievements there but I still have a couple of ideas for the future (of course I'm open to your ideas as well). Generally at the moment there are two types of achievements implemented. First one is something like 'language expert', in order to get this one you need to solve 50 problems in some particular programming language or language family. The second type of achievements can be rewarded for something you did in a single contest. For example tourist might try to hack your solution and if he doesn't succeed you get a You didn't even scratch me! achievement. Unfortunately Gennady won't be able to get this achievement himself, I apologise for that.

I was trying to come up with funny & interesting names for achievements, if you do not get the point in some achievement's name feel free to Google it or ask about it in the comments.

I should also mention here that all the achievements are given only for the online round you take part in, there is nothing for solving the problems after the round has finished. Also some achievements might take only rated rounds into account. There is a description for each achievement on how to get it.

Technical side

The site at the moment is not automated much, I need to manually start achievement crawling jobs after each contest so please do not blame me if you don't see your achievement two minutes after contest is over. It might take around 10-15 minutes after the system test phase for me to run all the scripts. I might also be in the gym, stay patient then :-) I'm working on automating the site.

And finally...

Finally the link: CF-achievements

Link to 'You didn't even scratch me!' achievement

You start point should be the main page and the user search textbox there, type in your CF handle and see what you have earned.

I should say that the project is in the beta stage at the moment, there is a lot to be done, I just wanted to involve the community into it, get some feedback and maybe some support. I'm open to all ideas about this project, please feel free to post them as comments here. Also you can see that the site was designed by a programmer (me), if you are more talented designer that I am, I would appreciate your help.

Initially I was going to let you know about it after CF round 288, but looks like Div. 1 part of it was cancelled so I decided to introduce it immediately. Also in the last round I_love_Tanya_Romanova got his achievement in CF, the idea of this site was born when I saw his comment so I decided it's good sign to start.

Hope you enjoy it,
Marat.

Hi guys!

I'm currently unemployed, looking for a job and would like to make some survey here, basically the topic would be "the interesting job". To give you a quick introduction: I was working as a .Net developer for around 7 years in different but more or less similar outsourcing companies, I've started participating in competitive programming 1.5 years ago and eventually this ruined my career in regular outsourcing cause the tasks there most of the time are more boring and less brain-teasing than what you have in CP.

To be clear, what I want here is to have as much opinions as possible, I would appreciate any ideas, consider this topic to be a brainstorming platform. I just want to broaden my understanding of what is there outside of the companies where I was working before. I'm interested to hear about your companies (I won't blame you if you decide to advertise your company in this blog post), or maybe you won't give out the company name but will share what do you do there, whether you find it interesting or not, anything.

I'm interested to hear about different areas you are working in, I'm not even restricting it to be a programming job, maybe something CS-related (but still supposed to be interesting for a programmer), maybe you're working in CS-research centres, maybe in some educational centre, maybe you're winning a lot of monthly/yearly contests and selling the T-shirts you get there and that's basically your salary.

Good example of what I'd like to see here is gojira's Rockethon introduction blog post where he was introducing Rocket Fuel, what do they do there, why is it interesting to work there, what might be the challenging task there and what does it have to do with competitive programming.

Случайно нажал "Сохранить" в русскоязычной версии сайта, теперь вы видите тут разбор на английском под российским флагом. Если кто знает, как удалить только русскую версию этой записи, напишите мне в личку, пожалуйста :-)

475A - Bayan автобус

As usual for A we have an implementation problem and the main question is how to implement it quickly in the easiest (thus less error-prone) way. During the contest I spent almost no time thinking about it and decided to implement quite straightforward approach — start with empty string and concatenate different symbols to the end of it. The result is quite messy and worst of all I forgot one of the main principles in the [commercial] programming — separate logic from its presentation. The "presentation" here is all these bus characters which are all the same across different inputs. So I paid my price, my original solution failed on system tests.

Much better approach afterwards I looked up in Swistakk's solution — you copy&paste the "template" of the bus from the example test into your source code, then you just change the characters for each of 34 possible seats. Result becomes much cleaner — 8140120.

475B - Сильно связный город

For B we already might need some kind of algorithm to solve it, though for the constraints given you might use almost any approach. If you just have a directed graph then in order to check whether you can reach all nodes from all other nodes you can do different things — you can dfs/bfs from all nodes, two dfs/bfs from the single node to check that every other node has both paths to and from that node, or you can employ different "min distance between all pairs of nodes" algorithm. All of these seem to work fine for this problem.

But we shouldn't ignore here that the input graph has a special configuration — it's a grid of vertical and horizontal directed lines. For this graph all you need is to check whether four outer streets form a cycle or not. If they form a cycle then the answer is "YES", otherwise "NO". The good explanation why this works was already given by shato. And then the entire solution takes just 10 lines of code — 8140438.

475C - Картина Камаль оль-Молька

There are probably several completely different ways to solve this problem, I will describe only the one I implemented during the round. The start point for the solution is that there are three cases we need to cover: either first time we move the brush right or we move it down or we do not move it at all. Let's start with the last one. Since we're not moving the brush at all then it's obvious that altered cells on the painting form a rectangle. It can also be proven that the only case we need to consider here is the rectangle 1x1, that's the only rectangle which cannot be achieved by moving some smaller rectangle. So we need to count the number of altered cells, if it is equal to 1 then the answer is 1.

Now we're left with two cases to consider, you start by moving right in the case and you move down in the second case. You can write some code to cover each of those cases, but you can also notice that they are symmetric in some sense. To be more clear, they are symmetric against the diagonal line which goes from (0, 0) point through (1, 1) point. If you have some code to solve "move down first" case, then you don't need to write almost completely the same code to solve "move right" case, you can simply mirror the image against that diagonal and invoke "move down" method again. Small trick which saves a lot of time and prevents copy-pasting of the code.

Now let's try to solve this last case. Basically the approach I used can be shortly described like that: we start in the leftmost topmost altered cell, then we move down and that move already leaves us only one option what do in the next moves until the end, so we get the entire sequence of moves. As well as getting these moves we also get the only possible width and height of the brush, so we know everything, I was not very strict while moving the brush so at the end I also compared whether these moves and these sizes in fact give exactly the same image as we get in the input.

That was the brief explanation of the "move down" method, now let's get into details. First of all since we move down immediately from the start point then there is only one value which can be valid for the brush width — it is the number of altered cells which go to the right from the start point. So we know one dimension. Now let's try moving the brush. Ok, first time as we said we move it down, what is next? Then you might have a choice whether you want to move right or to move down again. The answer is to move right first because your width is already fixed while height might be unknown still, so if you miss point to be altered in the left column of the brush and you move right, you might still have a chance to paint it if you take the correct height of the brush. But if you miss the point to the right of the current topmost brush row then you won't be able to cover it later, because your width was fixed on the first step. Here is a picture:

Grayed out is the current position of the brush. So what I'm saying is that you should move to the right if the cell in the red area is painted, otherwise you will definitely miss it. So this simple thing gives you the entire idea on how to build the only possible sequence of moves. You also need to calculate some possible value for the brush height. It can be calculated just before moving right, in order not to miss any painted cells you need to extend you height of the brush to cover all the painted cells in the leftmost column of you current brush position (this was highlighted as green on the image above). Now you know all the information about the probable painting — you have both dimensions of the brush and you know how it was moving, as I said before all you need to do is to double check that these moves and these dimensions in fact give you the same painting you get. If it gives the same painting then the answer for this case is width·height, otherwise there is no answer for this particular case.

If you implement all of these steps carefully and you won't paint cells more than one time, then you will be able to achieve an O(N·M) complexity.

475D - CGCDSSQ

It seems that all the solutions for this problem based on the same observation. Let's introduce two number sequences: a₀, a₁, ..., a_n and x₀ = a₀, x_i = gcd(x_i - 1, a_i). Then the observation is that the number of distinct values in x sequence is no more than 1 + log₂a₀. It can be proven by taking into account that x is non-increasing sequence and value for greatest common divisor in case if it decreases becomes at most half of the previous value.

So we have this observation and we want to calculate the count of GCD values across all the intervals, I see couple of ways how we can exploit the observation:

1. We can fix the left side of the interval and look for the places where gcd(a_l, ..., a_r) function will decrease. Between the points where it decreases it will stay flat so we can add the size of this flat interval to the result of this particular gcd. There are different ways how to find the place where the function changes its value, some people were using sparse tables, I have never used those so won't give this solution here. Otherwise you can use segment tree to calculate gcd on the interval and then do a binary search to find where this value changes. This adds squared logarithmic factor to the complexity, not sure if that passes the TL easily. Otherwise you can do basically the same by doing only one descent in the segment tree. Then you get rid of one logarithmic factor in the complexity but that will make segment tree a bit more complicated.

2. Another solution seems to be much simpler, you just go left to right and you calculate what is the number of segments started to the left of current element and what is the greatest common divisors values on those intervals. These values you need to store grouped by the gcd value. This information can be easily updated when you move to the next element to the right — you can check that part in my submission. Our observation guarantees that the number of different gcd values that we have to track is quite small all the time, it's no more than 1 + logA_max. Submission: 8141810, maps are used here to count gcd values, using the vectors instead makes it running two times faster but the code is not that clear then.

475E - Сильно связный город 2

Here we can start with the simple observation — if we have a cycle then we can choose such an orientation for the edges such that it will become a directed cycle. In this case all nodes in the cycle will be accessible from all other nodes of the same cycle. I was using the bridges finding algorithm to find the cycles. So you find all the cycles, for each cycle of size s_i you add s_i² to the answer. Then you can collapse all the cycles into the single node (storing the cycle size as well). After merging all cycles into single nodes original graph becomes a tree.

Now it comes to some kind of a magic, as far as I've seen from the discussions here people were make an assumption about the optimal solution, but nobody proved this assumption. Assumption goes like this: "there exists an optimal solution which has some node (let's call it root) such that for every other node v you can either reach root from v or you can reach v from root using directed edges of this optimal solution". Intuitively this assumption makes sense because probably in order to increase the number of pairs of reachable nodes you will try to create as least as possible components in the graph which will be mutually unreachable. So we have this assumption, now in order to solve the problem we can iterate over all nodes in the tree and check what will be the answer if we will make this node to be a root from the assumption.

Let's draw some example of the graph which might be a solution according to our assumption:

Here the root is drawn on top and every other node has either a path to the root or a path from the root. So let's say we decided that some node will be a root but we didn't decide yet for each of its children whether their edges will directed to the root or from the root. In order to fulfil our assumption the orientation of the edges within some child's subtree should be the same as the orientation of the edge between the root and its child. There will be two more numbers which we need to add to the result — pairs of reachable nodes within some child's (root children only!) subtree and pairs of reachable nodes for nodes from different subtrees. Let's introduce some variables:

s_i — size of the i-th cycle from the step when we were merging the cycles. In our tree all cycles are already merged into a single node, so s_i is a weight of the i-th node. It can be equal to 1 if node i did not belong to any cycle.

W_i — weight of the entire subtree rooted at node i.

It can be seen that if we orient all edges in the subtree in the same manner according to our assumption then the number of reachable pairs of nodes will not depend on the chosen orientation. Each particular node i adds the following term to the final result: s_i·(W_i - s_i). Now we need to decide what should be the orientation of all the edges adjacent to the root. Let's declare two more variables:

in — sum of W_i for all root's children whose edge is directed towards the root.

out — same for the children whose edge is directed from the root.

So if we have those definitions then the last term for the result will be equal to: (in + s_root)·out + in·s_root. We can see that this term depends only on the in and out values, it doesn't depend on which particular children contribute to each of these values. We check which values for in and out we can achieve, we can do it using the DP similar to the one used in knapsack. So we check every possible value for in, based on this we can calculate out value because their sum is fixed and equals to W_root - s_root, then we put them into the formula above and check whether it gives us a better total answer.

There is one more thing to be noted about this solution — you can see that I said that we need to iterate over all nodes and make them to be the root, then you will need to get all the sizes of the children for particular root and for those sizes you will need to find all the possible values for their sums. The sum can be up to N, for some root we might have up to O(N) children, so if you've fixed the root then the rest might have O(N²) complexity. This might lead you to a conclusion that the entire algorithm then has O(N³) complexity, which is too slow for the given constraints. But that is not the case because outermost and innermost loops depend on each other, basically there you iterate over all the parent-children relations in the tree, and we know that this number in the tree equals to 2(N - 1), less than N², so in total it gives O(N²) complexity for this solution.

Submission: 8168350

475F - Мультивселенная

Let's try to solve this problem naively first, the approach should be obvious then — you have a set of points, you iterate them left to right and you mind the gap between them. If there is such a gap between two neighbours you split this meta-universe with vertical line and do the same thing for each of two subsets. If you found no such gap by going left to right, you do the same going top to bottom. If you are unlucky again then you are done, this is a universe, it cannot be split. Let's think about the complexity of this approach now, even if get the points sorted and split for free then the complexity will highly depend on how soon you found a place where you could split the meta-universe. For example if you are lucky and you will always split close to the start of the sequence then your total complexity would be O(n), which is very good indeed. If you will encounter the option to split somewhere in the middle of the sequence, which means that you split the meta-universe in two halves, you will get a O(NlogN) solution, not linear but still good enough for this problem. The worst case occurs when you split always after iterating through the entire sequence, that means that in order to extract one point from the set you will have to iterate through all of them, now the complexity becomes O(N²), that's not enough already.

Let's think about it again, we got several cases, two of them are good (when we split in the beginning or in the middle) and the third one is too slow, it happens when we split always in the end. We need to make our solution better in this particular case and that should be almost enough to solve the entire problem. The obvious approach how to get rid of "split at the end" case is to start iterating from the end initially. And it should be obvious as well that it doesn't change much because your old start becomes the end now. But what we can do instead is to start iterating from both sides, then in any case you are winner! Intuitively, if you encountered a way to split at some end of the sequence then you're good to go because you spent almost no time on this particular step and you already found a way to split it further. In the opposite case, if you had to iterate through the entire sequence and found a split point in the middle you should be still happy about it because it means that on the next steps each of your new sets will be approximately two times smaller, that leads you back to O(NlogN) complexity. Also you should not forget that you need to do the same for Y coordinate as well, that means that you need to have four iterators and you need to check them simultaneously.

This is the basic idea for my solution, there is just one more detail to be added. Initially I told that our complexity estimate is given if we "sort and split for free". That's not that easy to achieve, but we can achieve something else almost as good as this one. In order to split cheaply all you need to do is to avoid the actual split :-) Instead of splitting the sequence into two subsequences you can just leave the original sequence and extract part of it which will become a new subsequence. Obviously if you want to make this operation cheaper you need to extract the smaller part. For example if you have a sequence of points sorted by X and you found a split point by iterating from the end of the sequence then you can be sure that the right subsequence will not be longer than the left sequence, because you iterate from the left-hand side and from the right-hand side simultaneously. Now we need to take care about sorting part as well. This one is easy, all you need to do is instead of storing one sequence of points you store all the points in two sorted sets — one by X and one by Y coordinate. In total this should add just one more logarithmic factor to the complexity.

That is the entire solution, I'd like to get back one more time to the complexity analysis. We have a recurring algorithm, on every step of the recurrence we're looking for the split point, then we split and invoke this recurring algorithm two more times. It looks that for the worst case (which is split in the middle) we will split a sequence into two subsequences of the same size, so we have a full right to apply a Master theorem here. On each step our complexity seems to be O(NlogN) (log factor because of using sets) so the "Case 2. Generic form" section from the Wiki gives us a solution that our entire algorithm has an O(Nlog²N) time complexity. Am I correct?

My submission — 8138406

471A - МУХ и палочки

Нам даны длины шести палочек и надо проверить, какое животное мы может из них собрать. Единственное условие, общее для обоих животных, — четыре палочки-лапы должны быть одной длины. Так как это условие общее, то в случае отсутствия хотя бы четырех палочек одинаковой длины ответ будет однозначно "Alien". Если же такие четыре палочки есть, то кого-нибудь мы точно соберем, надо только решить кого. В этом случае ответ будет зависеть от того, равны ли оставшиеся две палочки. Весь алгоритм получается такой:

1. Найти число, встречающееся не менее четырех раз.

2. Если такого числа нет, то ответ — "Alien"

3. Иначе надо удалить четыре вхождения этого числа из входного массива.

4. Если два оставшихся числа равны, то ответ — "Elephant", а иначе — "Bear".

Вместо того, чтобы искать число встречающееся четыре или более раз, можно было просто отсортироваться входной массив, взять третье или четвертое число и проверить, встречается ли оно четыре раза.

Авторское решение: 7977022

Так как ограничения в задаче очень маленькие, можно было заняться и перебором. Перебрать можно все возможные значения длин для ног, головы и тела. Если взять эти числа (ноги — четыре раза), и получится такой же набор, как во входных данных, то ответ найден. Если для всех вариантов длин они не совпали с изначальным массивом, то ответ — "Alien". Хотя в этой задаче перебор получается не проще основного решения.

Решение с перебором: 7975645

Вообще вроде участники допускали два типа ошибок в этой задаче:

1. Не учли, что ноги могут быть той же длины, что и голова или тело. Мы учли, что такое непонимание может быть и специально добавили это уточнение в условие. И все равно кто-то напоролся на это.

2. Были так же решения, в которых числа в изначальном массиве сортировались, а потом проверялись сравнивались числа на определенных позициях. Многие запутались в том, какие же числа сравнивать. Правильно сделать это можно было так:

 // 0-индексация, массив уже должен быть отсортирован

     if (l[0] == l[3]) cout << (l[4] == l[5] ? "Elephant" : "Bear");
else if (l[1] == l[4]) cout << "Bear";
else if (l[2] == l[5]) cout << (l[0] == l[1] ? "Elephant" : "Bear");
else cout << "Alien";

Такое решение: 7977214

Хоть это решение и короче основного, но в нем есть широкий простор для ошибок, да и подумать немного приходится, поэтому я бы предпочел писать решение выше.

Надеюсь, картинки вам понравились!

471B - МУХ и важные дела

Надо проверить можно ли составить три различные перестановки индексов массива, так чтобы элементы, соответствующие этим индексам получились взятыми в неубывающем порядке. Так как первая часть вопроса сводится к тому, есть ли три таких перестановки, то некоторые участники начали прямо считать количество перестановок, удовлетворяющих условию отсортированности. Этого делать не стоит, так как количество перестановок может легко переполнить и int и long. Часть решений на этом упала.

Можно пойти с другой стороны. Допустим вы уже собрали одну перестановку, идущую в ответ. Тогда в изначальном массиве вы можете найти два равных элемента, переставить их в перестановке и получить вторую перестановку. Сделав это еще раз, вы получите третью перестановку. То есть для наличия ответа достаточно найти две пары чисел, которые можно переставить. При этом даже можно, чтобы одно число в этих двух парах общим, главное чтобы не полностью пары были одинаковые. Найти две такие пары чисел можно в один проход массиву, если его предварительно отсортировать. Тогда нам просто надо проверить равно ли текущее число предыдущему, и если да, то мы нашли два элемента, которые можно поменять местами.

Полностью алгоритм таков:

1. Создадим новый массив пар (tuples) но основе исходного массива. Первым элементом пары будет значение элемента, вторым — его индекс. Использование пар во многих языках программирования даст нам возможность легко отсортировать массив по значению (первому элементу пары).

2. Сортируем массив по значению.

3. Проходим по массиву и ищем элементы, которые можно поменять местами. Пары можно поменять местами, если их первые члены равны. Запоминаем индексы таких пар для обмена. Если нашли две пары индексов для обдмена, то из цикла можно уже выйти, хотя можно и дойти до конца.

4. Проверяем сколько пар элементов мы нашли, которые можно поменять местами. Если меньше двух, то ответа нет.

5. В противном случае ответ существует. Тогда выводим изначальную перестановку, потом меняем местами первые два элемента, чьи индексы мы запомнили на третьем шаге, выводим полученную перестановку, переставляем местами еще два элемента и выводим последний раз получившуюся перестановку.

Авторское решение: 7977528

471C - МУХ и карточные домики

Карточный домик. В этой задаче требовалось заняться немного математикой, правда совсем чуть-чуть. Давайте сначала посчитаем сколько карт нам потребуется для создания одного этажа с R комнатами:

C = C_{комнаты} + C_{потолок} = 2·R + (R - 1) = 3·R - 1

А для постройки дома из F этажей с R_i комнат на i-м этаже необходимое количество карт составит:

где R — общее количество комнат в домике.

Тут уже можно заметить важное свойство — в правильном домике остаток N + F должно делиться на 3 нацело. То есть если вы нашли каким-то образом интервал возможных значений высот домиков, то в этом интервале в ответ пойдет только каждое третье значение высоты, остальные высоты будут давать ненулевой остаток.

Теперь давайте выясним какой максимальной высоты может быть домик из N карт. Для того, чтобы построить максимально высокий дом при ограниченном количчестве карт, очевидно нам надо на каждый этаж тратить как можно меньше карт. Но у нас есть ограничение, что количество комнат на каждом этаже должно быть меньше, чем на этаже ниже. Получается, что для постройки дома максимальной высоты стратегия должна быть такой: мы ставим одну комнату на самом верхнем этаже, две комнаты — на этаже под ним, потом три комнаты, и так далее. Количество карт, необходимое для строительства такого дома, составит:

Это минимальное количество карт, необходимое для постройки дома из F этажей. Из этого уравнения мы можем посчитать максимальную высоту дома, который мы можем построить из не более, чем N карт, достаточно просто найти максимальное F которое дает N_min <  = N. Математики могли бы решить это квадратное уравнение руками, а у программистов два варианта:

1. Проверить все возможные значения F пока N_min не превысит N. Так как N_min растет пропорционально F², то нам понадобится проверить не более чисел. Так мы получим решение с временной сложностью , что вполне укладывается в лимит по времени.

2. Второй вариант — сделать двоичный поиск. Если искать это максимальное количество этажей двоичным поиском, то сложность алгоритма будет уже O(logN). Это было мое изначально задумываемое решение, но потом решили, что и решения за корень пусть проходят.

Теперь, когда мы знаем теоретически максимальное количество этажей в доме, нам может понадобиться немного скорректировать это число в связи с теми рассуждениями об остатке от деления на 3, которые мы делали выше. Для этого вам, возможно, придется уменьшить максимальную высоту дома на 1 или 2. Опять же из тех рассуждений про остаток мы получаем, что начиная с этого количество этажей каждое третье число вниз будет годиться в ответ, надо их просто посчитать. Посчитать можно, перебрав их (опять вернемся к решению), или просто использовав формулу:

ans = (F_max + 3 - 1) / 3 (integer division)

Кажется все, ну и не забывайте везде использовать 64-битные числа в этой задаче.

Авторское O(logN) решение: 7977863

Авторское решение: 7977888

471D - МУХ и стенки из кубиков

В этой задаче нам даны два массив целых чисел и надо найти, сколько раз второй массив встречается в первом как подмассив, если мы можем предварительно добавить произвольную константу ко всем элементам второго массива. Назовем эти массивы a и b. Как многие участники заметили или знали заранее, эту задачу можно просто решить если перейти к массивам разниц вот так:

aDiff_i = a_i - a_i + 1 (для i =  = 0..n - 1)

Проделаем это с обоими входными массивами, тогда мы получим два новых массива, содержащих на один элемент меньше изначальных. А в новых массивах изначальная задача сводится просто к поиску подстроки (пусть и с большим алфавитом) — мы будем искать строку bDiff в строке aDiff. Эту задачу можно решить многими способами и структурами данных — берите какая вам ближе. Изначально предполагалось требовать решение за линейное время, но потом решили сделать ограничения помягче, вдруг кто суффиксный массив за логарифм захочет сдать. Суффиксных массивов я у участников не видел, но квадратичные решения некоторые засылали :-)

За линейное время задачу можно решить, используя Z-функцию строки или алгоритм Крута-Морриса-Пратта. Я написал так же решение с суффиксным массивом, но оно заменто тяжелее пишется, чем линейные решения.

В этой задаче есть один случай, который стоит учесть отдельно — когда стенка Хораса состоит из только одной башенки, тогда он в любой башенки стенки медведей может увидеть слона и ответом будет n. Хотя для некоторых алгоритмов это можно даже и не учитывать отдельно, если считать, что пустая строка совпадает находится в заданной строке в любой позиции. Еще некоторые участники пытались использовать настоящие строки и приводили разностные массивы к char. Это не работает, так как диапазон значений char гораздо меньше диапазона значений в задаче, и такое решение легко можно взломать.

Я не думал, что переход к разностным массивам будет настолько очевидным решением, поэтому не ожидал, что эту задачу решат так много людей и так быстро.

Авторское решение с Z-функцией O(n + w) : 7978022

Авторское мясо с суффиксным массивом O((n + w)·log(n + w)): 7978033

471E - МУХ и много-много отрезков

Нам дан набор горизонтальных и вертикальных линий, надо стерить некоторые части линий или линии целиком, чтобы оставшиеся линии образовывали единую фигуру без циклов.

Для начала давайте рассмотрим решение упрощенной версии этой задачи, которое не убирает циклы и работает за N². Для такого решения нам достаточно использовть систему непересекающихся множеств (СНМ, DSU), в нее мы кладем все наши линии и начинаем объеденить линии, которые пересекаются. Так же наша СНМ должна считать сумму длин соединенных отрезков, изначально для каждого отрезка мы указываем его длину, а потом СНМ должна при объединении пересчитывать это значение. Так как у нас может быть вплоть до N² / 4 пересечений между линиями, то мы получили квадратичное решение.

Теперь давайте избавимся от циклов. Для этого мы можем модифицировать предыдущее решение в том месте, где оно объединяет множества в СНМ в случае пересечения отрезков. Стандартная СНМ ничего не делает если объединяемые множества и так совпадают, нам же надо поменять это поведение и в случае попытки объедения множества с самим собой мы будем уменьшать значение суммы длин отрезков в этом множестве на единицу. С точки зрения задачи таким образом мы стираем некоторый единичный отрезок в точке пересечения двух отрезков, таким образом мы избавляемся от цикла. Теперь у нас уже есть правильное решение, но оно не пройдет по времени.

Теперь надо это решение ускорить. В худшем случае мы всегда будем иметь N² / 4 пересечений отерзков, поэтому очевидно, что для ускорения решения нам надо отказаться от обработки пересечений по одному. Для начала давайте перейдем от рассмотрения пересечений в произвольном порядке к использованию заметающей прямой. Таким образом мы будем рассматривать все пересечения слева направо, например.

В этом случае понятно, что код, который будет отвечать за пересечения — это код, добавляющий вертикальные линии, поэтому давайте разберемся с этим получше. Допустим мы добавляем вертикальную линии с координатами (x, y1, x, y2), так же можем предположить, что у нас есть некоторый набор горизонтальных линий, проходящих через вертикальную прямую с координатой x, мы поддерживаем этот набор горизонтальных линий по ходу работы заметающей прямой. Итак мы добавляем вертикальную линии, которая, допустим, пересекается с n горизонтальными линиями. Из этих n линий некоторые идущие подряд линии могут уже принадлежать одному множеству в СНМ, в таком случае обрабатывать отдельно каждое из этих пересечений нет никакого смысла, достаточно обработать одно из них и перейти к следующему набору линий, принадлежащему другому множеству в СНМ. И в этом и заключается основная идея в этой задаче — вместо того, чтобы хранить горизонтальные линии по одной, мы можем хранить их блоками, где каждый блок принадлежит некоторому конкретному множеству в СНМ и покрывает некоторый интервал вдоль y координаты.

Класс для этого блока выглядит так:

struct chunk{
	int top, bottom; // координаты начала и конца интервала, который покрывается данным блоком
	int id; // идентификатор множества, которому принадлежит данный блок, в СНМ
};

Нам понадобится некоторая структура данных, которая будет позволять добавлять/удалять эти блоки и находить блок на нужной высоте. Все эти операции мы можем делать за логарифмическое время, используя treap или STL map.

Посмотрим теперь подробнее на то, как это будет работать и почему это будет работать достаточн быстро. В процессе работы заметающей прямой мы будем обрабатывать три типа событий (перечислены в порядке приоритета их обработки) — начало новой горизонтальной прямой, рисование вертикальной прямой, конец горизонтальной прямой. Первая и третья операция каким-то образом меняет наши текущие блоки, вторая операция использует данные о блоках и обрабатывает пересечения. Рассмотрим каждую из операций:

начало горизонтальной линии. В этом случае нам надо добавить еще один блок, чей интервал будет состоять пока из одной точки. Может получиться, что данная прямая будет проходить через интервл, уже занятый каким-то блоком, тогда тот блок надо разбить на два блока — выше горизонтального отрезка и ниже его. То есть, в ходе обработки этого события мы создадим максимум два блока. Это можно сделать за некоторое константное время обращений к нашей стуктуре данных с блоками, поэтому итоговоя временная сложность данной операции — O(logN). Стоит заметить, что эта операция — это будет единственное место, где мы будет создавать новые блоки. Количество вызовов данной операции ограничено N, поэтому в сумме за время работы мы можем получить не более 2·N блоков.

вертикальная линия. Здесь мы должны найти все блоки, с которыми пересечется вертикальная линия, и объеденить их. Искать блоки будем по одному сверху вниз — находим первый блок, потом второй, если второй нашелся, то объединяем их (и сами блоки, и их множества в СНМ) и ищем третий, и так далее. Такой подход гарантирует, что когда блоки для объединения закончатся, то мы потратим на это не больше O(logN) времени. Объединяя два блока мы также потратим O(logN) времени на одно объединение, одна вертикальная линия в худшем случае может пересечь n горизонтальных линий, что даст суммарное время обработки уже O(NlogN). Но несмотря на то, что одна конкретная операция такого типа может работать O(NlogN) времени, мы можем показать, что все операции такого типа в сумме так же будут работать O(NlogN), потому что всего за время работы программы у нас будет создано не более 2·N блоков, как мы показали выше, а каждая операция объединения блоков, уменьшает их количество на единицу. Такой вот амортизационный анализ получился. Еще раз повторю, временная сложность обработки всех операций второго типа составила O(NlogN)

Так же тут есть несколько других деталей, которые нам надо учесть. Например, нам все еще надо избегать возникновения циклов. Поля этого блога довольно узки, чтобы вместить доказательство полностью, но вот эта формула вроде дает правильную поправку, которую нужно внести, когда объединяешь несколько блоков вертикальной линией, идущей от y1 до y2:

d = y2 - y1 - (N_{intersections} - 1) + N_distinctsets - 1

where d — поправка, которую нужно внести к сумме длин отрезков получившегося блока в СНМ

N_{intersections} — количество горизонтальных линий, с которыми пересеклась вертикальная линия. Я находил это значение отдельным деревом отрезков за O(logN)

N_distinctsets — количество различных множеств, чьи блоки были объеденены вертикальным отрезком, их надо считать по мере объеденения блоков

Таким образом можно правильно корректировать значение суммы длин оставшихся отрезков, чтобы избегать возникновения циклов, при этом опять же нет необходимости рассматривать каждое пересечение по одному. Есть еще одна деталь, которую стоит проговорить, — может получиться, что вертикальная линия, попала в некоторый блок, но не пересеклась там ни с одной горизонтальной линией, в таком случае эту вертикальную линию надо пропустить, как если бы она вообще не попала ни в какой блок.

конец горизонтальной линии. Наконец мы досюда добрались и тут вроде все просто. Когда заканчивается какая-нибудь горизонтальная линия нам может понадобиться обновить наш блоки. Всего может быть три случая:

a. Эта линия всего одна в блоке — удаляем блок полностью.

b. Эта линия является каким-либо краем интервала блока — надо удалить эту линию и найти новый край интервала, я это делал с помощью того же дерева отрезка, которое я упоминал выше.

c. Линия лежит внутри интервала некоторого блока — тогда блоки обновлять не надо.

Ну вот вроде и все, таким образом мы получаем O(NlogN) решение.

Авторское решение: 7978166 (в коде структура данных с блоками называется 'linked_list', я думал изначально, что там будет связный список, но постепенно концепция поменялась, а название осталось).

Добрый день Codeforces! Рад пригласить всех к участию в Codeforces Round #269 для второго дивизиона, который состоится в эту пятницу, 26-го сентября. Как обычно программисты первого дивизиона приглашаются поучаствовать неофициально (читай "за респект"), от своего имени очень прошу первый дивизион участвовать.

Задачи будут все мои, так что вы знаете, кого ругать, если задачи вам не понравятся. Со своей стороны я постарался приложить максимум усилий, чтобы избежать подобного.

Это мой первый раунд, так что я представлюсь. Мне 27 лет, уже лет 7 работаю программистом, но вещами типа ACM/ICPC не занимался и открыл их для себя относительно недавно. Пару лет назад узнал словосочетание "dynamic programming" с курса на Coursera и чуть позже открыл для себя Codeforces, с тех пор я пропадаю тут. Я родился и вырос в Санкт-Петербурге, прожил там до 24-х лет. А потом женился, и мы переехали в Киев. Киеву и теперь принадлежит наше сердце, когда-нибудь мы туда вернемся.

Надеюсь, что набор задач в этом раунде будет для вас интересным и в меру разнообразным. А я пока хотел бы представить героев задач. Ими будут три животных из Санкт-Петербургского и Киевского зоопарков. Конкретно это Меньшиков и Услада — белые медведи, символы Санкт-Петербургского зоопарка. Это мои любимые животные в Питерском зоопарке, можете поучиться у них лунной походке. Их третьим товарищем будет слоник Хорас из Киевского зоопарка. Я не в курсе, какие танцы он любит, но вообще он показался нам очень милым и дружелюбным слоном. Мне всегда нравились белые медведи и слоны (как и множество других животных), наконец у меня будет свой раунд про них! Рекомендую запомнить, кого как зовут, так как в условиях задач имена и названия животных используются попеременно. Эта троица выступает за дружбу между странами, я надеюсь, что вы им поможете и поддержите их.

Со своей стороны хотел бы поблагодарить:

• MikeMirzayanov и всю команду Codeforces за этот сайт,

• Gerald за помощь с задачами,

• Марию Белову aka Delinur за перевод условий,

• мою жену Таню за ее бесконечную поддержку во всем, этого раунда бы не было без нее.

Википедия просила напомнить вам, что день, когда состоится этот раунд, будет 269-м днем года (по крайней мере в Московском и множестве соседних часовых поясов) — отличное совпадение с номером раунда. Это Gerald мастерски поставил раунд в расписание.

Раз вы дочитали аж досюда, то я открою вам маленький секрет, который хотят знать все некрасные участники. Секрет заключается в том, что чтобы стать красным, надо решить 1513 задач из архива Codeforces. Мой личный опыт.

Еще хотел бы добавить: gojira поступил нечестно! В своем объявлении раунда он сказал, что ему от Sammarize переходит титул самого старого автора задач, но он не сказал, каков же был его возраст на тот момент. Так что я не знаю, достанется мне этот титул или нет. В студию вызывается gojira для ответа на этот вопрос!

Увидимся на раунде, а после я буду благодарен за любые отзывы о задачах, хотелось бы знать, что вам понравилось, а что — нет.

P.S.: Как обычно, разбалловка — дело последних пяти минут перед раундом.

новость раз: разбалловка будет нестандартная — 500, 1000, 2000, 2000, 2500

Всем огромное спасибо за раунд, это было круто! Надеюсь и вам понравилось. Мои поздравления победителям. worse сегодня не участвовал, поэтому борьба была жаркой с обеих сторон таблицы. Меньшиков и Услада уже пошли обновлять рейтинги, а Хорас пишет разбор, сегодня ночью обещает быть.

Я понял и учел допущенные с моей стороны ошибки, но еще раз прошу вас дать знать ваше мнение о раунде/условиях/мутности задач/картинках. Более 5К зарегистрированных — это фантастика, спасибо!

К сожалению никто не решил E, хотя hos.lyric был очень близок к этому, его решение упало на предпоследнем тесте, который не был даже самым максимальным, с моей точки зрения. Моя ошибка, что я недооценил сложность этой задачи, но спасибо всем, кто пытался решить ее.

Еще раз спасибо,
Увидимся на следующих раундах,
Марат.

Статистика от DmitriyH
Разбор задач

416A - Угадай число!

Используем стандартный подход к решению задачи А второго дивизион — в лоб. Будем поддерживать диапазон, в котором может находится искомое число. По мере считывания запросов в зависимости от ответов уточняем этот диапазон. Если в конце получился невырожденный диапазон, то берем любое число из него, иначе — "Impossible".

Посылка: 6606892

416B - Гильдия художников

В этой задаче достаточно пройтись по все художникам и работам в правильном порядке. Проходимся по всем художникам, запоминаем когда он закончил работу над каждым шедевром. Последующий художник начинает работу над данным шедевром не раньше, чем предудущий закончил.

Посылка: 6606994

416C - Система бронирования

Решаем задачу жадно. Необходимое наблюдение — в первую очередь нужно сажать группы, приносящие максимальную прибыль и сажать группу надо за подходящий столик минимального размера. Так что берем все группы в порядке уменьшения прибыли и ищем подходящий стол. Если подходящих столов несколько, то берем стол минимальной вместимости. Если подходящих столов нет, гоним данную группу на мороз. Ограничения в задаче позволяют искать столик для каждой группы полным перебором.

Посылка: 6617198

416D - Численность населения

Необходимое наблюдение в этой задаче — если мы покрываем какой-то отрезок одной арифметической прогрессией, то нам будет выгодно (ну или как минимум не хуже) взять как можно больше чисел в этот отрезок, т.е. расширить этот отрезок влево и вправо, насколько возможно. Соответственно жадное решение — берем самое левое число, не покрытое ни одной прогрессией, начинаем новую прогрессию в этой точке и пытаемся покрыть ею максимальное количество элементов. При этом надо внимательно рассмотреть все случаи, что можно а что нельзя покрывать одной прогрессией. В частности:

• Если в отрезке нет ни одного фиксированного значения, то этот отрезок можно покрыть одной прогрессией.

• Если в отрезке есть только одно зафиксированное число, то независимо от того, где оно находится, мы сможем покрыть отрезок арифметической прогрессией с шагом 0.

• Если в отрезке есть два и более зафиксированных числа, то мы можем посчитать требуемый шаг прогрессии и все числа должны подходить под этот шаг. Шаг должен быть целым числом.

• Если прогрессия возрастающая и есть некоторое количество незафиксированных элементов в начале, то надо проверить чтобы при заданном шаге этим незафиксированным элементам присваивались положительные значения.

• Аналогично, если прогрессия убывающая, то брать незафиксированные элементы можно только пока значение, которое должно быть вставлено на эту позицию, положительно.

Посылка: 6607174

416E - Маршрут Президента

Будем рассматривать эту задачу на графе, данном в примере:

Нам надо посчитать сколько всего ребер лежит на всех кратчайших путях между какими-либо двумя вершинами. Рассмотрим сначала более простую версию задачи — посчитать только те ребра на кратчайших путях, которые входят непосредственно в конечную вершину (ту, до которой мы строили кратчайшие пути). Вот, например, ребра лежащие на кратчайших путях из вершины 4 в вершину 2, непосредственно ведущие в вершину 2:

Введем для этого числа обозначение: inEdges_source, v — количество ребер, входящих в вершину v, которые лежат хоть на каком-то кратчайшем пути из source в v. В указанном примере inEdges_4, 2 = 3. Введем также обозначение S_{source, dest} — набор вершин, через которые проходит хоть один кратчайший путь из вершины source в вершину dest. Например, S_4, 2 = {1, 2, 3, 4}. С этими двумя обозначениями нетрудно заметить, что количество ребер, лежащих хоть на одном кратчайшем пути из source в dest будет равно:

То есть ответом для вершин s и d будет сумма значений inEdges_s, v для всех вершин v, которые лежат на каком-нибудь кратчайшем пути из s в d. Значит осталось посчитать эти самые S и inEdges. И то, и другое легко считаются, если известны кратчайшие расстояния между всеми парами вершин. Для вычисления этих расстояний используем алгоритм Floyd-Warshall. Полностью решение получается такое:

1. Считаем минимальное расстояние между всеми парами вершин алгоритмом Floyd-Warshall.

2. Считаем inEdges. Просто перебираем все вершины на роль источника, во внутреннем цикле перебираем ребра. Проверяем по минимальным расстояниям, будет ли это ребро находиться на кратчайшем пути от источника к какому-нибудь из своих концов.

3. Считаем ответ. Тройным вложенным циклом перебираем три вершины — source, destination и mid. Первые две — это вершины, ответ для которых мы ищем. Третья — это вершина, через которую должны проходить кратчайшие пути. Проверяем, что через mid проходит кратчайший путь из source в dest, если это так, то прибавляем к ответу inEdges_{source, mid}.

Все три шага имеют сложность O(n³).

Посылка: 6607257

Пожалуйста, не стесняйтесь репортить все опечатки, ошибки, неточности в личку.