Hello, Codeforces!
The Romanian Master of Informatics is a yearly competition addressed to high school students and organised by the Tudor Vianu highschool in Bucharest, Romania. The format of the contest is the one commonly found in olympiads.
RMI provides a great opportunity for young people to demonstrate their abilities in Informatics, to exchange knowledge and to enhance cross-cultural contacts in high-school education. Coming to RMI 2017, they will have opportunities to make new friends, to visit a friendly country, and to discover the culture of Romania.
CS Academy will host the online mirrors of both competition days. The first contest starts on Thursday, October 05, 11:00:00 UTC, after the onsite competition ends. The problem statements will be available in English.
Contest format
- You will have to solve 3 tasks in 5 hours.
- There will be full feedback throughout the entire contest.
- The tasks will have partial scoring. The maximum score for each problem will be 100 points.
- There will be no tie breaker, so two users having the same total score at the end of the contest will share the same place in the standings.
If you find any bugs please email us at contact@csacademy.com
Don't forget to like us on Facebook, VK and follow us on Twitter.
Is the contest duration 4 or 5 hours?
5 hours.
Could anybody please explain how to solve problem Fashion? I heard from people that they used minimum cut, still I don't seem to figure out how.
Create a node for each item and also a node for each valid set.
For each item node, add an edge from it to the sink with capacity ci, the cost of buying this item.
For each valid set, connect the node corresponding to this set to the three nodes corresponding to the items involved in this set, each with capacity INF. Also, add an edge from the source to the node corresponding to this set with capacity sc, the profit obtained for completing this set.
Let S be the total sum of the profit for each set. The answer is S - M, where M is the minimum cut of this graph.
Why does this work? For each item node, if it's in the set containing the source in the cut, then we say we buy this item. Otherwise, we assume we didn't buy it. Thus, when an item i is bought, the size of our cut increases by ci. Next, for a set of three items, if at least one of them isn't bought, this means that at least one of the three nodes corresponding to the items is sided with the sink. Thus, the node corresponding to the set must also be sided with the sink or else the size of cut increases by INF. This will increase the size of the cut by sc, which denotes the amount lost if we don't complete the set.
How do you solve hangman 2? I'm thinking it smells like hashing, but I'm stuck. I can't seem to find solutions anywhere.