For problem 1241C. Legacy tut.

Here's another idea to solve it in linear time. Whole idea is to become a thug seller, haha! You sell ticket, but you can take it back! Any time! But respect police, ah? So whenever you take ticket back, you return funds. Otherwise you'll never reach k.

Idea

This is how whole thing works. OK, we also swap x and y, so x is always better.

1. All non-x and non-y buyers should wait. You respect their.. booking, but kindly ask them to quit the line. They will get their tickets after you deal with X and Y. Besides those guys will get best price.
2. So, you start selling X, or Y. Whatever it is, you sell most expensive remaining ticket. AND.. if at some point you've just realized, that you could sell even more expensive ticket, but it is sold with lower profit, you just take it back, (give money back) and sell it again with better profit. Buyer who just suffered lose of ticket is to be calmed by buying another (probably cheaper) one.

Here are some additional notes for 1238E's tutorial, which is kindly made by awoo и Roms. I got stuck there for a while with final expression.

( I even wrote solution with traces, haha (see after cut) )

First, let's think about base expression for total moves amount. And then in top-down way try to come to solution.

Moving rightward, for each symbol $$$s$$$, with keyboard position $$$x$$$ we will accumulate all moves between that symbol and all symbols at left.

Disclaimer: this is not my solution. Everything I could do is to chew it up to myself, and public here as well.

Recently I was checking out solution for "1221G — Graph And Numbers".

The most intriguing thing was independent sets counting.

Hi folks!

I think most of you are cool programmers and know several programming languages. Below are some thoughts (and one open-source project) regarding to C++.

Disclaimber

(below is not some super cool algorithm, neither problem solution, rather thoughts, and some may be off-topic proposal, so sorry for that)

Stake

I love the performance you can get by means of C++. If you know what are you doing, you can get awesome results. But syntax... well, I'd like to make it better.

At least following things:

• modularity
• reflection
• set of syntactic sugars.

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