chokudai's blog

Tokio Marine & Nichido Fire Insurance Programming Contest 2022（ABC256) Announcement
By chokudai, history, 3 years ago, In English

We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256).

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

  • Vote: I like it
  • +57
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

A-F are pretty cool, how to solve G?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, I already used union-find and summing up the minimum cost for each component. Still WA.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    You should only do that for cycles, similar problem

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    You need to use

    approach
    → Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Quite cool of the author allowing sqrt-decomp to pass F

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E i stored the graph as undirected one and broke the cycles into 2 cases ,the vertices which belong purely to a cycle and the others which have a cycle and a chain (for these i rand dfs from vertices whose adjoint size was 1 until i found a vertice with adjoint size 3) . But it gave WA. Could somebody point out why the approach is wrong.

code

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    i realised my mistake (there can be more than 1 chain attached to a cycle).Pls ignore the above message

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On the way from reading C to understanding C I somewhere lost meaning of h[],w[], to be maximum posible value of row/col, instead of exact value. Then its hard to solve.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

normalize discussing ABCD's of abc contest (_/_)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I use segment tree + lazy propagation for arithmetic progression for problem F. But I got wrong answer, can someone point out where I might be making the mistake?

My submission

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think maybe your multiplication has a risk of integer-overflow.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm... if I do modulation each and every time, wouldn't it be the case? Oh and also I do something like #define int long long

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh sorry, I didn't notice your #define int long long. But I still guess that it has something to do with integer-overflow. Maybe your line-126 int chg = v - a[x]; has a negative chg and this may lead to something that is not expected.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider this simple testcase.

    Input
    Expected Output
    Your Output
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for providing such a cool contest.

Problem D involves a wonderful trick. By implementing a[L]++ and a[R]--, and then calculating the prefix sum, we could find out all the intervals that have been covered.

Problem E is about graph with directed edges, and one should be familiar with topological sorting and also how to find out the cycle.

Problem F needs some mathematics to deduce the expression of Dx, and one should also be very careful of integer-overflow.

As for Problem G, at first, I was scared by the super huge N. After I found out the state transition of dp, then I realized that it could be reduced to logN by using Fast-Exponentiation-Algorithm (matrix version). But my definition of dp state is somehow a little bit complicated and didn't finish codes before contest ends.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The easiest and worst sol for problem C :)

#include <bits/stdc++.h>
using namespace std;

int main() {
	int h1, h2, h3, w1, w2, w3, ans = 0;
	cin >> h1 >> h2 >> h3 >> w1 >> w2 >> w3;
	vector<vector<int> > a(3, vector<int>(3));
	for (a[0][0] = 1; a[0][0] <= 30; a[0][0]++)
	for (a[0][2] = 1; a[0][2] <= 30; a[0][2]++)
	for (a[2][0] = 1; a[2][0] <= 30; a[2][0]++)
	for (a[2][2] = 1; a[2][2] <= 30; a[2][2]++) {
		a[0][1] = h1 - a[0][0] - a[0][2];
		a[1][0] = w1 - a[0][0] - a[2][0];
		a[1][2] = w3 - a[0][2] - a[2][2];
		a[1][1] = h2 - a[1][0] - a[1][2];
		a[2][1] = h3 - a[2][0] - a[2][2];
		if (a[0][0] + a[0][1] + a[0][2] == h1)
		if (a[1][0] + a[1][1] + a[1][2] == h2)
		if (a[2][0] + a[2][1] + a[2][2] == h3)
		if (a[0][0] + a[1][0] + a[2][0] == w1)
		if (a[0][1] + a[1][1] + a[2][1] == w2)
		if (a[0][2] + a[1][2] + a[2][2] == w3)
		if (a[0][0] > 0 && a[0][1] > 0 && a[0][2] > 0)
		if (a[1][0] > 0 && a[1][1] > 0 && a[1][2] > 0)
		if (a[2][0] > 0 && a[2][1] > 0 && a[2][2] > 0) ans++;
	}
	cout << ans;
	return 0;
}

It got Accept

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The first 6 IFs are fairly useless since allways true, so it would be easier to remove them.

    → Reply