Hello Codeforces!

On October 27, 17:05 MSK Educational Codeforces Round 31 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

The round will be **unrated** for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 problems** and **2 hours** to solve them.

The problems were prepared by Ivan BledDest Androsov, Vladimir 0n25 Petrov, Alexey Perforator Ripinen, Mike MikeMirzayanov Mirzayanov and me.

Good luck to all participants!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | biGinNer | 6 | 175 |

2 | natsugiri | 6 | 228 |

3 | palayutm | 6 | 283 |

4 | LHiC | 6 | 293 |

5 | eddy1021 | 6 | 295 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | Hinata_On_Fire | 18 |

2 | halyavin | 22:-10 |

3 | dreamoon | 33:-35 |

4 | kuko- | 15 |

5 | STommydx | 12:-1 |

259 successful hacks and 368 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | eddy1021 | 0:01 |

B | eddy1021 | 0:02 |

C | gritukan | 0:06 |

D | cyand1317 | 0:18 |

E | eddy1021 | 0:36 |

F | zscoder | 0:35 |

UPD: Editorial is uploaded

?detar ti si

!

https://pasteboard.co/GQNNymL.png

https://pasteboard.co/GQNO1vS.png

Sorry I do not like the sea :( I often get seasick

xD

I have made a chrome extension which automatically downvotes any comments with the phrase "is it rated". You can download it from: goo.gl/V8KP39

spoiler:u Got trolled!!

Anyways, the music is good :P

so mean XD

Can you tell me where is music from?

Guy in the middle is only interested in the educational round, not rating :)

Is it rated? Фалунь Дафа хорош!

Wow! 2 contests in a row. I am so excited. :D

UPD: FIXED!SpoilerIt isn't rated!

Score distribution? :)

Is it rated?

Very nice contest!!! D was a very interesting problem, it tricked me into thinking I have a correct solution when it was miserably wrong.

Can you please tell me how to solve D? I noticed that it will probably be some kind of divide and conquer but that's where I got stuck, but I might be completely wrong (again.. ).

It's just merging 2 to 3 piles of balls every time, with each time the cost.equals to the sum of the number of balls merged, so a greedy algorithm would work.

Think backwards. You have all the elements in their original position and you want to put them in starting position with smallest cost. To solve this, you can adapt the greedy algorithm to find the Huffman code. There are two main differences:

1) You get the 3 smallest elements to generate a new one (instead of two).

2) In the case when you have a even amount of elements you'll get a suboptimal solution if you follow this algorithm. But you can be greedy here too, just convert the smallest two to a new element to get and odd number of elements.

Thank you!

Thinking backwards can sometimes be very helpful, but I've never used it on a construction/greedy problem.

I'll bear this trick in mind.

how did you come up with this solution?

I tried some approaches that didn't work. Until I realized the problem we were trying to solve was almost the same that this one: https://en.wikipedia.org/wiki/Huffman_coding#Problem_definition

You can see the relation if you see the problem backwards. Initially you have all colors in their positions and you want to bring them all to first position.

This problem has a known greedy solution. If you don't know the solution for the Huffman Coding problem, please read about it. You'll need to know it in order to understand next paragraph.

The thing is that now you have a ternary (not a binary) tree. So we must adapt the solution. My first try was to greedily try to get the 3 smallest values and merge them. But this does not work when you have a even number of colors, because you'll have to make an operation with only 2 nodes.

First I tried to make this operation using two nodes as late as possible in the merging process (when we have only 2 or 4 nodes left), but this is not optimal. So I drew some test cases and concluded that you should do it as soon as possible, so every case you have a even number of nodes you should merge the smallest two and get a problem with odd number of nodes, in which you can apply the greedy approach.

Can you please explain the solution for problem-D in detail. Can you please explain what changes when n is even. I am still unable to to visualise the solution you told.

Please read my comment above.

Greedy will work to solve D.The process of D is to build a Huffman Tree.So we can construct a Huffman Tree with 3 leaves each node that isn't a leaf to get the answer.

What's more,there're similar problems in China.

Seems that a greedy algorithm would be the best solution for F while I used min cost flow. The time limit is quite loose.

defender & Hacker same person :p

What is the hack for div2 B ?

6 1 4 4 4 4 4

Why 38 in this case in D ?

How Would I Know that .

Don't comment irrelevant ANSWERS please

For example,I sum up all ai and incorrectly considered the answer to be "yes" when x-sum=n+1 or n-1,so I am hacked only 9 min after the beginning of the hack phase.

What is the test case please.

2 5 1 1 This test can make my program produce wrong answer.

But It is showing as 'invalid' input . Please can you provide me a valid input :)

Between "2 5" and "1 1",there is a '\n'. Maybe you don't enter it.

6 1 4 4 4 4 4 Why 38 in this case in D ?

1 4 4 4 4 4

take (1, 4, 4, 4, 4, 4) and spread like this (1, 4, 4) (4, 4) (4) total cost = 21

take (1, 4, 4) and spread (1) (4) (4) total cost 9

take (4, 4) and spread (4) (4) total cost 8

How to solve E?

go from top to bottom maintaining DSU for current and previous row

It means pair (x, y) is not the same as pair (y, x).

Btw you can always ask jury a question during the contest, use it if you don't understand something in statement

You have to press enter twice

to make a new line.

I think educational rounds should be rated. I mean, they are perfectly good rounds

I consider some problems to not have well known solutions (even though this information is in the description of the educational rounds — maybe the ideia was once used somewhere else, but to recognize the idea in a particular problem statement is always a unique activity) and usually very few people can solve all problems (depending on the difficulty maybe it could be rated just for div 2)

Also if someone does not wish to compete they could just do the round in a virtual participation

Oh boy, commenting without knowing codeforces tradition of downvoting.... That's gotta hurt.

So, he can't write his opinion about site ? Let's remove the comments. Nobody will write their "stupid" opinions.

you have anime profile

can someone explain me how to solve c i didnt' get why people are multiplying the size of the group of connected station with itself because it is not necessary the if there is path from(1,2) then there is also a path from(2,1).

For every group of connected stations, it is necessary that every station is reachable from every other station since every pi's are distinct which means that only one train can leave a station(i's are distinct) and only one can reach it(pi's are distinct). Due to which every connected stations would form a cycle and would contribute it's size^2 to the final result.

In this problem, the graph is directed, so if you have a strong component, it is a cycle.

In a cycle, if you can reach vertex Y from vertex X, you can reach vertex X from vertex Y. In other words, all vertex in the same component can reach all other vertex in this component (including itself).

So, if you have a component with N vertex, then you have N * N pairs reachable from each other.

hey...guys help......i did that ...i ran dfs and got all components...then i joined the first two components with highest verteces ..then N*N for all components...but getting wrong answer on case 18 shows my output>ans

i use disjoint sets to find numbers of cycles and then merge the biggest two cycles.

http://codeforces.com/contest/884/submission/31817720

i did quite the same

All my test cases seems to pass. Maybe you can check the corner cases, where n = 2 or n = 1.

Maybe some problem in there.

hey...guys help......gettin WA...i ran dfs and got all components...then i joined the first two components with highest vertices ..then N*N (N=number of vertex in a comp) for all components...but getting wrong answer on case 18 shows my output>ans

Type cast before you multiply the answer . Like, instead of ans=N*N write ans=(long long)N*N . Do the same for every multiplication hope it will get AC :)

i did http://codeforces.com/contest/884/submission/31812954

Change

into

wow...thanks man....what was wrong with cout<<(llint)(n*n) by the way

The first way you are multiplying two ints and then casting that overflow result to a long. The second way you cast the first n to a long that way the second n is implicitly converted to a long as well when doing the multiplication.

oh..it's clear now .i thought u have to typecast the whole equation ... thanks man

or u can use

1LL * n * n1LL means 1 in long long

yeah..that works too man....didn;t know

C Bertown Subway http://codeforces.com/contest/884/submission/31826056

pretty confused...

I found the problem myself, incorrect max1 and max2 (JUST IGNORE THE POST)

where can i see the problems? im new in this page. :( yesterday i registered for the concourse, but i can't participated. can you helpe me to find the problems please?

http://codeforces.com/contest/884

thank you mister

where is the editorial ?

There is a Telegram bot that informs us upcoming contests regularly

Username is @CodeForcesBot

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).I am confused with something.How can someone solve two problems in two seconds...

two minutes*