Credits:

1138A - Sushi for Two, idea and development by KAN

1138B - Circus, idea by MikeMirzayanov, development by _kun_

1137A - Skyscrapers, idea by jury together, development: achulkov2

1137B - Camp Schedule, idea and development by wrg0ababd

1137C - Museums Tour, idea by ch_egor, development by qoo2p5

1137D - Cooperative Game, idea and development by mingaleg

1137E - Train Car Selection, idea and development by Schemtschik

1137F - Matches Are Not a Child's Play , idea by GlebsHP, development: _kun_

And now the editorials:

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Can we do div2B in O(n)?

div2B can be solved in O(n) by directly construction, but it is complicate to code. In my code 51091100 I divide number of artists into a total of 3 cases. They are

n_{b}+n_{c}= 0n_{b}≥n_{c}andn_{a}≥n_{b}-n_{c}n_{b}≥n_{c}andn_{a}<n_{b}-n_{c}and each case have 2 subcases, by constructing each subcase, they can be solved in O(n).

I have tried my best to simplfy my code, but I still wonder if there are any simpler code that solve this problem in O(n)

There is simple

O(n) solution for this problem. We havea+b+c+d=n/ 2 andb+c+ 2d=n_{b}+n_{d}which can reduce toa-d=n/ 2 -n_{b}-n_{d}which can brute force inO(n). See my submission 51116077.I see..

For every value of

`a`

, we can finddfrom the reduced equation. Plugging the values in the given two equations, it's possible to uniquely find values ofbandc.Well done!

Thank You for sharing . I understood your concept. But can you please explain why you have used if(f>a[3]) condition ? What exactly is it's usage?

$$$f$$$ is the total of numbers need to be printed after printing values from $$$q[1]$$$ and $$$q[2]$$$. If $$$f>a[3]$$$ means that we have to use values from both $$$q[3]$$$ and $$$q[4]$$$, otherwise the value from $$$q[3]$$$ is enough( There is else statement before return 0). It's just more convenient for me to implement this way. It's not necessary. Array $$$a[]$$$ is not necessary too since we can use $$$q[].size()$$$ instead. My submission is still a bit messy.

Why u have not used f>a[4] condition instead of f>a[3] condition? What is the correct use of f>a[3] condition i cannot understand it,could u please clear my doubt of not using f>a[4] condition or how can u say that if f<=a[3] then there is no need to look for q[4]?

Both of them would be fine. :) From the fourth condition, we can guarantee that $$$f=\frac{n}{2}-x-i<=a[3]+a[4]$$$. If you understand the concept, you will know that we can choose any $$$f$$$ numbers from $$$q[3],q[4]$$$ which is always possible since $$$f<=a[3]+a[4]$$$.(if it passed four conditions in my code). Of course, $$$f>a[3]$$$ is not necessary. It’s just alternate way of implementation. Sorry if array $$$a[]$$$ makes you confused, you can think of it as $$$q[].size()$$$ instead. :)

What would you classify this kind of problem as? I see it as an adhoc problem.

Hey, I am new here.

Solved Div2B in O(1) logic. check my solution here.

Thats O(n)

Sorry for confusion. I was talking only for problem solving Logic. Leaving the input/output and time for shortening the problem.

Div2B is a beautiful problem!

since the recent rounds , division 2 has became slightly tougher than previous rounds and question are really much interesting and new . and also this one was moscow olympiad finals , so u can expect them to be good .

From what I've understood in the announcement, div2 problems only were not part of the competition.

Typo in the tutorial of 1137D — Cooperative Game.

"Let

rdenote the distance from finish vertex to the onefastandslowmet."The

rhere should bex.It seems too many points for Cooperative Game problem. It is just the search a cycle in a list. Very known problem!!

I have submited a solution of Museums Tour problem. It has Run Time Error on test 16 with try http://codeforces.com/contest/1138/submission/51133791. I very carefully look at my code and don't understand what problem is. Can tell me what to do to find error.

Stack overflow, because u use recursive function with depth >= 5kk

Another solution for F with treaps:

Lets have an implicit treap of the order of the vertices. Initially we build it in by simulating the burning process with heap or set.

"When" and "Compare" queries are now easily done in by simply finding the position of a given node (we keep pointers for each vertex id to its corresponding node in the treap).

For "Up" query we notice that we need to extract nodes on the path from the last updated vertex (initially assume this is

n) to vertexu, then reverse their order and finally insert this new reversed subsequence to the end of the treap.The problem is that we are not sure that these vertices are consecutive in the treap. But we can prove that the number of consecutive segments is amortized . The proof is similar to the one for link-cut tree's complexity. So now we have a straight forward by doing binary lifting and "when" query for finding the consecutive segments in the path. I had this solution during the onsite version, but unfortunately it's too slow. Fortunately we can do this finding in by going through the treap and keeping "next" and "prev" pointers in each treap node. This way the complexity is and without optimizations passes in ~3 sec.

Here is the code if someone is interested: 51142776

Also if I'm not mistaken by replacing the treap with splay tree, the complexity will become just .

If you use Google properly, you may solve div1D in one minute.

I don't think problems like this should appear in Codeforces.

I spent my time and effort just to find that my friends all used Google to solve it(they told me after the contest).

It's not fair.

Could you please provide us with a link, so we would know how to google such things next time?

https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare

its a famous interview question.. given a linked list with a loop..find the starting node of that loop. https://www.youtube.com/watch?v=-YiQZi3mLq0 This is exactly what you require to solve this question..no hard googling needed.. just type the above keywords..u will get many blogs describing fast, slow method as mentioned in the tutorial..and this question is not even a modified version of this famous problem..its almost same to same.. thats why maybe it was unfair to have this one in the contest and a suprise that only few were able to solve it..maybe because many were stuck on problem C..like me :P

Sorry for my late reply.

http://global.bing.com/search?q=if+linked+list+have+a+cycle&qs=n&form=QBLH&sp=-1&pq=if+linked+list+have+a+cyc&sc=0-25&sk=&cvid=C990CCB8E2B647558F43CFD6A4AF6B26

There is even a code sample.

By the way, I used Bing because I'm in China. And for some specific reason, we can't use Google these days :(

This is also a standard technical interview question: https://www.geeksforgeeks.org/find-first-node-of-loop-in-a-linked-list/

Can someone describe solution for Div1C. "Museums Tour" in more detail? I can't understand why my submission got

WA 79on this problem.HELP! Why I got RE on test 73? Submission: 51210282

You can try some other compiler. I switched from G++17 to MS C++ 2017 and got AC.

Thanks! I tried MS C++ and got AC, that's quiet strange.

I wonder why my div1C code gets either TLE18 using array analog link list to storage edges, or MLE16 using vectors :( TLE18: https://codeforces.com/contest/1137/submission/51214068 MLE16: https://codeforces.com/contest/1137/submission/51253929

exactly the same to me.

simple o(n) solution for the B problem we need to check for 3 formulas

https://codeforces.com/contest/1138/submission/51265926 link to submission

why to many negative votes??!!1

Maybe because there has been another comment described this solution, your explanation is much more detailed though. (Although the last paragraph is really hard to read)

Can anyone tell me what's going wrong here?? Problem C Code

How to solve 1137B — Camp Schedule by hashes?

got it

It would be great if you can share the approach or provide any links which you referred :D

I referred to this link. It provides a simple way to hash strings while avoiding collision. You can also refer to my submission

can anyone explain the thought process for getting the formula for problem " Skyscrapers " "ans=max(Lrow,Lcol)+1+max(Grow,Gcol)" ?

ok got it by myself ! as for any intersection we are comparing with any two elements row wise and column wise so the number of elements less than and greater will remain the same .and from this we can make this formula

Yes!!! Check below solution. http://codeforces.com/contest/1138/submission/51394343

How could div2A be solved by binary search?

For DIV1 problem B,Why I WA on Test 71,using the fail array(may like Aho-Corasick automation)to calculate the max same prefix and suffix. What is the hacks in Test71. my code is as following https://codeforces.com/contest/1137/submission/51554217

For Div1.C,why do we have to compute in SCC? We can stop our tour in an arbitary city besides 1.

I don't know why I am getting wrong in div2B problem in 9th test. My submissions went pretty well with all 8 test cases.I tried my best but didn't found any error. I implemented div2B in according to your tutorial. Here is my submission. Plz rectify me. See my submission 54278040