A — Dawid and Bags of Candies

As long as we have only 4 bags, naive solution is enough. We should make unordered selections out of 4, at first by 1, then by 2 and then by 3 bags. If for some selection we got amount of candies equal to half of total, then answer "YES". Else — answer NO.

My solution

B. Ania and Minimizing

If k==0, print original number.

If number is a single digit.

Then, if k==1 (and now it's 1 for sure), then we can replace that digit with 0 (answer "0"), otherwise.. well we never fall into this branch.

If number is 2 or more digits long.

1. If first digit is not 1, then replace it with '1' and --k.
2. Go through rest of digits (but stop if k is 0). If current digit is not '0', replace it with '0' and --k.
3. Print modified number.

My solution

C. Anadi and Domino

At first, what is domino? It's a complete graph with 6 vertices with addition that each vertex also has loop (don't mixup with cycle). Edges are tiles. Or let say, if we could put tiles on edges, then we could put tile on each edge, even with all the limitations we have in this task. And we would had no more tiles after all.

But in this task we have a graph with up to 7 vertices. So...

If number of vertices is 6 or less.

Then this is a subgraph of domino graph. In this case we can put different tiles on all of its edges with all limitations satisfied.

So in this case just return "m" (amount of edges in given graph).

If graph has 7 vertices.

Just downgrade this case to previous one.

We should merge some two vertices. What happens in this case?

When we merge vertices A and B, with amount of edges E(A) and E(B) respectively, then we get some amount of common edges, let it be "C". After A and B will be merged we will have new graph with 6 vertices and amount of edges m2(A, B) = m — C.

So we just should enumerate all possible pairs of A and B and get one with maximum possible m2: m2 = max(by(A, B), m2(A, B)).

And one more thing. When merging vertices what happens with edge A-B itself? In this case we will get a loop. This is OK, domino graph allows up to one loop per vertex. If there is no A-B edge, then result graph will be with no loops, this is also good to us.

My solution

D. Marcin and Training Camp

Let's just consider two students. We can send them together then and only then if their skills masks are equal.

Now extend this statement up to group of students. We can send group of students with the same skills mask, let it be "G". And we can associate this mask with group. After sorting students by group we still may have some lone students, with original skills set.

But there is no "then and only then" for groups. So whom more may take a group of such students?

• Any lone guy with skills mask A, if it is a submask of group skills mask: G or B == G.
• Any other group.

Out of latter follows, that instead we can send all groups at once + some lones. Masks of lones we send must be a submask of one of the groups we send.

UPD: I know how to hack myself :-) what's wrong with statement above?

If there are no groups, alas, we can't send anybody. For there would be no compatible students. Everybody is too original to travel and will stay ahome.

Algorithm

1. Sort students by groups. Associate mask with each group. Only group's total experience matters in next steps. So it's enough to represent groups as a dict(Mask, Experience).
2. Go through lones. If there is a suitable group G for lone A, then include A into G (which just means to update group's experience: experience(G) += experience(A) ).
3. Calculate total experience of all groups. Print that number as a result.

My solution