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

• Contest URL: https://atcoder.jp/contests/abc307
• Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230624T2100&p1=248
• Duration: 100 minutes
• Number of Tasks: 8
• Writer: kyopro_friends, math957963, evima, m_99, Nyaan
• Tester: MMNMM, leaf1415
• Rated range: ~ 1999
• The point values will be 100-200-300-400-475-550-550-600.

We are looking forward to your participation!

We will hold Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）.

• Contest URL: https://atcoder.jp/contests/abc306
• Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230617T2100&p1=248
• Duration: 100 minutes
• Number of Tasks: 8
• Writer: physics0523, yuto1115, evima, Nyaan, m_99
• Tester: m_99, cn449
• Rated range: ~ 1999
• The point values will be 100 — 200 — 250 — 400 — 475 — 525 — 600 — 650.

We are looking forward to your participation!

The 1st anniversary contest of Markov Algorithm Online is in a week.

Markov Algorithm Online is a puzzle game site you can play with Markov algorithm. I wish you enjoy it!

AtCoder Beginner Contest 131 is on this Saturday.

• Contest URL: https://atcoder.jp/contests/abc131
• Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190622T2100&p1=248
• Duration: 100 minutes
• Number of Tasks: 6
• Writer: sheyasutaka, yuma000, DEGwer, gazelle, satashun
• Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

I was interested in this problem in GCJ Finals and thought of its general case (= the board size is infinite).

Rule

You are given two (or more) type of polyominoes. Find a shape satisfies the condition "can be filled completely with some number of polyominoes of the same type in no overlaps" for each type of polyomino.

A shape with fewer cells is considered better but it's not necessary to minimize.

Sample

Problems

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

I welcome your solutions or new problems!

I qualified for DCJ but I couldn't go. What's happened:

• 8/1 — I broke my elbow bone. It's OK, I'll go.
• 8/4 — I got a very high fever over 40℃. It was recovered yesterday and it wasn't an infection. It doesn't matter anymore.
• 8/5 — I had a terrible diarrhea. It was not healed enough to travel and finally I gave up.

I'm very sad but not despairing so much now because I'm living and I passed FHC R2 with only one hand and a high fever;)

I hope a great success of the Code Jam events!

SRM637 Div1Medium can be solved even if the width of the board is very very large.

There is O(|black cells|) solution.

Let's consider only 8 cells near the edge. There are three(four) cases:

1) There are black cells in both side.

In this case, already result is fixed because the players can not change a parity of the number of turns while the game ends.

2) There are black cells in only one side.

In this case, the first player can win because he can decide a parity by coloring the other side cell black.

3) There is no black cell in both side.

In this case, the player who color a side cell black at the first loses. Hence the winner in the board without 8 side cells wins. You can determine the winner recursively.

0) The width of the board is less than 4.
In this case, it is easy to determine the winner.

Div2 A Appleman and Easy Task (Author: EnumerativeCombinatorics)

This is a simple implementation problem. You can solve by searching adjacent cells of every cell.

Div2 B Appleman and Card Game (Author: EnumerativeCombinatorics)

This is simple greedy problem, but it seemed to be reading-hard. The statement says, "Choose K cards from N cards, the score of each card is (the number of cards which has the same character in K cards. (not in N cards)"

It is clear that this total score is (the number of 'A' in K cards)^2 + (the number of 'B' in K cards)^2 + ... + (the number of 'Z' in K cards)^2 This value will be maximized by the simple greedy algorithm, take K cards from most appearred character in N cards, the second most appearred character in N cards, and so on.

Div1 A / Div2 C Appleman and Toastman (Author: hogloid)

First I describe the algorithm, and explain why it works.

• Sort {a_i} in non-decreasing order.
• Then, for i-th number, add (i + 1) * a_i to the result.(i=1...n-1)
• For n-th number, add n * a_n to the result.

Actually, when you multiply all numbers by -1,the answer will be the minimal possible value, multiplied by -1.

It's Huffman coding problem to find minimal possible value. Solving Huffman coding also can be solved in O(nlogn)

In Huffman coding, push all the numbers to a priority queue. While the size of the queue is larger than 2, delete the minimal and second-minimal element, add the sum of these two to the cost, and push the sum to the queue. Here, since all the numbers are negative, the pushed sum will be remain in the first in the queue. Analyzing this movement will lead to the first algorithm.

Div1 B / Div2 D Appleman and Tree (Author: hogloid)

Fill a DP table such as the following bottom-up:

• DP[v][0] = the number of ways that the subtree rooted at vertex v has no black vertex.
• DP[v][1] = the number of ways that the subtree rooted at vertex v has one black vertex.

The recursion pseudo code is folloing:

DFS(v):
 DP[v][0] = 1
 DP[v][1] = 0
 foreach u : the children of vertex v
  DFS(u)
  DP[v][1] *= DP[u][0]
  DP[v][1] += DP[v][0]*DP[u][1]
  DP[v][0] *= DP[u][0]
 if x[v] == 1:
  DP[v][1] = DP[v][0]
 else:
  DP[v][0] += DP[v][1]

The answer is DP[root][1].

UPD:
The above code calculate the DP table while regarding that the vertex v is white (x[v]==0) in the foreach loop.

After that the code thinks about the color of vertex v and whether we cut the edge connecting vertex v and its parent or not in "if x[v] == 1: DP[v][1] = DP[v][0] else: DP[v][0] += DP[v][1]".

Div1 C / Div2 E Appleman and a Sheet of Paper (Author: snuke)

For each first type queries that p_i > (the length of the paper) — p_i, you should express the operation in another way: not fold the left side of the paper but fold the right side of the paper. After such query you need to think as the paper is flipped.

Let's define count[i] as the number of papers piled up at the segment [i,i+1] (absolute position). For each query of first type you can update each changed count[i] naively.

Use BIT or segment tree for count[i] because you can answer each second type queries in O(log n). The complexity of a first type query is O((the decrement of the length of the paper) log n) so total complexity of a first type query is O(n log n).

Div1 D Appleman and Complicated Task (Author: EnumerativeCombinatorics,snuke)

First, we ignore the already drawn cell and dependence of cells. If we decide the first row, then the entire board can decided uniquely. We call 'o' is 1, and 'x' is 0. Then,

a[i][j] = a[i-2][j] xor a[i-1][j-1] xor a[i-1][j+1]

For example, I'll explain n=5 case. Each column of first row is a, b, c, d, and e. "ac" means a xor c.

a   b   c   d   e
b   ac  bd  ce  d
c   bd  ace bd  c
d   ce  bd  ac  b
e   d   c   b   a

Each character affects the following cells (denoted 'o').

o.... .o... ..o.. ...o. ....o
.o... o.o.. .o.o. ..o.o ...o.
..o.. .o.o. o.o.o .o.o. ..o..
...o. ..o.o .o.o. o.o.. .o...
....o ...o. ..o.. .o... o....

Generally we can prove the dependence that a[0][k] affects a[i][j] if k<=i+j<=2(n-1)-k and |i-j|<=k and k%2==(i+j)%2. ... (*)

We can separate the problems by (i+j) is odd or even.

Each (i,j), we can get the range of k that affects the cell (i,j) by using formula (*). So the essence of this problem is that "There is a sequence with n integers, each of them is 0 or 1. We know some (i,j,k) where a[i]^a[i+1]^...^a[j]=k. How many possible this sequences are there?" We can solve this problem by using union-find. At first, there is n*2 vertices. If k is 1, we'll connect (i*2,(j+1)*2+1) and (i*2+1,(j+1)*2), if k is 0, we'll connect (i*2,(j+1)*2) and (i*2+1,(j+1)*2+1) (note that i<=j). If both i*2 and i*2+1 are in the same set for any i, the answer is 0. Otherwise the answer is 2^((the number of sets-2)/2).

Also, it is possible to solve odd number version. (How many ways to fill all the empty cells with 'x' or 'o' (each cell must contain only one character in the end) are there, such that for each cell the number of adjacent cells with 'o' will be "odd"? ) I'll hope for your challenge for odd-number version!!

Div1 E Appleman and a Game (Author: hogloid,snuke)

Let C be the number of characters(here, C=4)

Given string S, the way to achieve minimum steps is as follows: Append one of the longest substring of T that fits current position of string S. Appending a not-longest substring can be replaced by appending longest substring and shortening the next substring appended.

Let dp[K][c1][c2] be defined as :

the minimum length of string that can be obtained by appending a string K times and that starts by character c1 and whose next character is c2. Note that next character is not counted in the length.

dp[1] can be calculated as follows:

For every string of length L expressed by C characters, if the string is not included in T, update the dp table as dp[1][the string's first character][its last character]=min(dp[1][its first character][its last character],L-1)

For any (c1,c2), dp[1][c1][c2] is smaller than or equal to log_C(T+1)+2 (since the kind of strings of length log_C(T+1)+2 that start by c1 and end by c2 is equals to T+1). Therefore for L=1...log(T+1)+2, try all the strings as described above.

Also we can use trie that contains all substrings of T of length log_C(T+1)+2, and find what can't be described as a substring of T by one step.

Since dp[k+1][c1][c2]=min(dp[k][c1][c3]+dp[1][c3][c2] | c3=1...C), we can use matrix multiplication to get dp[K].

For a integer K, if there is (c1,c2) such that dp[K][c1][c2]<|S|, the answer is greater than K. Otherwise,the answer is smaller than or equal to K.

Since answer is bigger or equal to 1 and smaller or equal to |S|, we can use binary search to find the ansewr.

O(T*((log T)^2+C^2)+C^3(log |S|)^2)

BONUS: Is there any algorithm that solves in O(1) or O(C^foo)(that is, not depended on |S|) for each |S| with pre-calc?

Some hints: Maximal value of dp[1][*][*] — Minimal value of dp[1][*][*] <= 2

(let's call the maximal value dp[1][i][j]=L. Here, any C^(L-2) strings are contained in T as substring, so for any (c1,c2), dp[1][c1][c2]>=L-2)

Maximal value of dp[1][k][*] — minimal value of dp[1][k][*] <=1 ( k=1...C)

Maximal value of dp[1][*][k] — minimal value of dp[1][*][k] <=1 ( k=1...C)

Even if we use these hints and make C=3, the implementation would be not easy.

If you come up with smart way, please comment here :)

Today, I took 10-th place at SRM583 and my rating changed 1804 to 1981 (+177!). I was very happy.
But then I looked at my rating history and I noticed the sad fact.

My rating at last last time was 1981. Yes, my rating only just returned to last last rating...
Oh, that's topcoder. The most important thing in topcoder is a stability.

I will hold TGO 3rd contest next week from this time.

Herbert contest will be hold at here at this time for three hours.

Do you know "Herbert"?
"Herbert" is the programing puzzle game that was used on Microsoft ImagineCup for three years.
@quolc developed the website "Herbert Online Judge" and we can play "Herbert" now!
"Herbert" is very interesting game and there is more to it than meets the eye. New technics are found even now! How about playing?
Herbert Online Judge
English tutorial

I will hold a contest on Turing game Online from 21:00(Japanese time).

Why don't you participate!

My blog entry of Turing game Online.

I wanted to play more the game of turing machine which used google top page.

So I made Turing game Online.

How about playing?