Anyone else wasted a lot of penalty on problem A because I didn't realize $$$n$$$ is constant across all test cases...

Screencast with some commentary

Is the last problem known? I was just tired of thinking about it and submitted some greedy.

Here's my screencast, which includes a bit of commentary. Thanks for the round!

You can also directly do D with min-cost circulation. Add a dummy vertex, an edge of cost $$$-L$$$ for some large $$$L$$$ from the dummy to to every M in the initial tiling, and an edge of cost $$$-L$$$ from every M in the target tiling to the dummy.

Then add an edge of cost $$$s (|x_i - x_j| + |y_i - y_j|)$$$ between $$$i$$$th M in initial tiling and $$$j$$$th M in target tiling, and an edge of cost $$$f$$$ from every M in initial tiling to the dummy, and an edge of cost $$$f$$$ from the dummy to every M in the target tiling.

Output cost of min cost circulation plus $$$L \cdot (\text{number of M's})$$$.

For D, there is a solution with O(r*c) nodes and edges.

It uses min cost max flow. The graph has 2 + 2*r*c nodes. Two nodes are for the source and sink, and there are two nodes for each cell of the grid, representing the two colors. There are 4 types of edges:

1. Source to initial color, with cap 1, cost 0
2. Final color to sink, with cap 1, cost 0
3. Between opposite colors of the same cell, with cap INF, cost 2*f
4. Between adjacent cells of the same color, with cap INF, cost s

The max flow of this graph is always r*c, and the mincost flow divided by 2 is the answer.

Can you please elaborate solution of Problem C?

In B the number of edges inside a polygon with $$$a$$$ edges is less than $$$a$$$ so you only need dp values of kind $$$(a, n \% a)$$$.

I had an $$$O(n \log n)$$$ solution to B. Notice that the answer is of form $$$a + ab + abc + \ldots = n$$$. Rewrite as $$$a(1 + b + bc + \dots) = n \Leftrightarrow b + bc + \ldots = n / a - 1$$$. That is basically the form of the answer for $$$(new~n) = n / a - 1$$$. So to get the answer you can just do $$$ans_n = \max \limits_{d|n} ans_{n/d-1}+1$$$ plus-minus the polygons of size 2 case.

A bit weird that very trivial A costs more than not-so-trivial D-small.

For me, the round was OK, but, unfortunately, concentrating on D small instead of very doable C-large costed me advancement to the next round. Participating in like 5 contests a year also does not help :)

Anyway, the contest was nice, and it feels good to come back from "retirement" from time to time, so thanks to the organizers!

What do you think your rating would have been if you actively took part in codeforces contests? (My guess is around 2700)(I'm excited to hear your opinion) Thanks.

The way I did D had (R * C + 3) nodes, 4 * R * C edges: One for each cell, a source, S, and two sink D' and D. We use the two sinks to limit the max Flow. (We want to fix how many Magentas we move to a valid position, and then do flips for the others).

Construct the R * C graph by adding edges to neighbors of inf capacity, SwapCost.

For every cell M that should be G, add edge from S to it, 0 cost, 1 capacity. For every cell G that should be M, add edge from it to D', 0 cost, 1 capacity.

Then fix the number of Ms we want to solve by SWAPing to destination, i, from 0 to M inclusive. Make the edge D' to D be equal to that number. Do min-cost flow. Result for this being fixes is:

flowCost + (total_bad — 2*i) * FlipCost (take min of all of these).

Since you're only increasing the edge once, the flow you computed at the previous step is already valid, so you'll only need to do one iteration to update it.

Locally my code ran in ~0.2 sec for all tests.

I had the same idea for B but stuck due to no proof of complexity!

I was able to solve only A and B, So this time also no advance to round 3. Also can someone please give out an estimated problem difficulty rating for all the problems ?

The problems seem too straightforward for a R2.

I think C was the most beautiful problem although I got it ac only in last minute :)

I was very surprised at problem A. I did B first because I saw interactive and decided to leave it. After solving B I went back to A and did it in less than 10 minutes, and I only took that long because I was sceptical that it could be that easy.

I don't think either of my solutions for B or C were the intended ones — I solved B top down (analysis says solve it bottom up), and I solved C using a segment tree and recursion (analysis says straightforward DP).

D I got only the small and I was a bit fortunate because I had been brushing up on bipartite matchings recently.

In general I found the contest more accessible than most of the round 2s I did in practice. In previous years at my current level I would have expected to progress less than 50% of the time, so today was a good day for me, which I think means the problems were not too hard.

I'm really devastated... my goal for the past 4 years has been to try to get top 1000 for the code jam t-shirt. This year I was finally going to get 950th place by solving A, B, and C. Except when the contest ended, my placement was 1806, not 950. Because my C hidden cases failed.

Because I forgot 1 very trivial, very important line of python at the top of my code.

I will never, ever, forget this fucking line again.

I nailed the third problem 1 second before the end of the contest, though it didn't help me to qualify

In D, I wrote an algorithm to find random non-optimal greedy answer which I ran for 10^5 times and took the best answer out of them, which passed test 1

I was a bit salty about cutoff for round 3 being too high. At one point I even considered sitting back and watching ranklist after I solved all visible subtasks. Glad that I didn't do it and solved C large as well.

Anyways these are cutoff for round 3s (or score of 1000th rank in round 2) (if anyone is interested) -
2021 — 66/100.
2020 — 39/100.
2019 — 32/100.
2018 — 44/100.
2017 — 23/100.
2016 — 29/100.
2015 — 22/100.
2014 — 40/100.

I was feeling sorry for 1001th rank guy , He literally disqualified for 1 sec

Final time of 1000th rank guy:2:29:13 Final time of 1001th rank guy:2:29:14

I have solved B using a brute force solution with a complexity of around ~36sec.

const int N = 1e6 + 5;

int dp[N];

void fun(int prev, int sum, int cur) {
  if (sum >= N) {
    return;
  }
  dp[sum] = max(dp[sum], cur);
  for (int i = 2; i < N && sum + i * prev < N; i++) {
    fun(prev * i, sum + i * prev, cur + 1);
  }
}

void solve() {
  int n;
  cin >> n;
  int ans = dp[n];

  cout << ans << endl;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  for (int i = 3; i < N; i++) {
    fun(i, i, 1);
  }

  int test;
  cin >> test;
  int tc = 1;
  while (test--) {
    cout << "Case #" << tc++ << ": ";
    solve();
  }  

  return 0;
}

for some unknown reasons, in problem B, my code passed both cases:

#include <bits/stdc++.h>
#define endl '\n'
#define modulo 1000000007
#define int long long
#define PI acos(-1)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#define sinDegrees(x) sin((x) * PI / 180.0)
#define cosDegrees(x) cos((x) * PI / 180.0)
#define tanDegrees(x) tan((x) * PI / 180.0)
#define atanDegrees(x) atan(x)* 180.0 / PI
#define asinDegrees(x) asin(x)* 180.0 / PI
#define EPS 0.000000001
using namespace std;
int power(int x,int y,int m)
{
int temp;
if(y == 0)
return 1;
temp = (power(x, y/2,m))%m;
if (y%2 == 0)
return ((temp%m)*temp);
else
return ((x*temp%m)*temp%m)%m;
}
int inv(int x,int m=modulo)
{
return (power(x,m-2,m))%m;
}
///IOI 2021 bronze medalist isA
int N,testcases;
int REC(int num,int TOT){
if(TOT>N)
return INT_MIN;
if(TOT==N)
return 1;
int maxer=INT_MIN,i=2;
while(TOT+num*i<=N&&i<7)
maxer=max(REC(num*i,TOT+num*i)+1,maxer),i++;
return maxer;
}
int32_t main()
{
//freopen("output.txt","w",stdout);
//freopen("input.txt","r",stdin);
cin.tie(0),iostream::sync_with_stdio(0);
cin>>testcases;
for(int i=1;i<=testcases;i++){
cin>>N;
int maxer=0;
for(int i=N;i>2;i--)
maxer=max(REC(i,i),maxer);
cout<<"Case #"<<i<<": "<<maxer<<endl;
}
return 0;
}

my idea was just to brute force to start with any number bigger than 2, then either multiple it by 2,3,4,5,6. And check the best result. Such a solution should get wrong answer(according to my knowledge I guess). Can anyone contradict/proof if my solution is correct/incorrect?

I ranked 1672 in code jam round2 , so sad that I didn't make it to next round. This year contest is much easier. Usually solving two whole problem and an additional small test set will guarantee you with top 1000 and make it to next round, this year even solving three problems cannot pass.