# Topcoder SRM 699 Div2 review

Single Round Match 699 Sponsored by Cisco Statistics – Problem Editorial   Div II Level One: UpDownHiking Idea is same with editorial.

Div II Level Two: LastDigit Category: Arithmetric The approach is different from editorial which uses binary search.

Div II Level Three: FromToDivisibleDiv2 Category: Arithmetric, graph I couldn’t solve it in contest, so I just followed editorial for my practice.

# Codeforces Round #374 Div. 2 review

Link Codeforces Round #374 Div. 2 (Contest 721) Editorial A. One-dimensional Japanese Crossword Problem Just count consecutive ‘B’ in the sequence.

B. Passwords Problem This is also easy, just count the number for each string length. You even don’t need to process any string manipulation.

C. Journey Problem I felt it is difficult than problem D. During the contest, I tried to solve it by DFS but I got TLE.

To get answer, we can use DP (dynamic programming) to reduce computational complexity as $$O(mn)$$.

D. Maxim and Array Problem Basic strategy to get minimum product is as follows, 1. If the product is positive, […]

# Codeforces Round #373 Div. 2 review

Link Codeforces Round #373 Div. 2 (Contest 719) A. Vitya in the Countryside Problem Basically, check last 2 character to determine its direction is “UP” or “DOWN”. Special case comes when the last number is 0 or 15, in that case the direction changes and you can determine the direction without looking second last character.

B. Anatoly and Cockroaches Problem We can consider 2 patterns for final alignment. Pattern 0 is to align “rbrbrb…” and pattern 1 is to align “brbrbr…”. We will compare the original alignment and final alignment. For each position i, we need to change the color to… Case A: r to b Case B: b to r If […]

# Codeforces Round #368 Div. 2 review

Link Codeforces Round #368 Div. 2 (Contest 707)   A. Brain’s Photos Problem Just need to check if color (Cyan, Magenta or Yellow) exists or not in the photo.

B. Bakery Problem The problem sentence looks long, but after summarize, you just need to find the path between flour storage city and non flour storage city with minimum distance. But to find out these city path, I was using vector which is not fast enough and I got TLE during contest.

We can make search fast, in constant time by using Array to set a type of city.

C. Pythagorean Triples Problem Consider some cases to […]

# scanf and printf are much faster than cin and cout

When I’m solving the Codeforces problem, 707D. Persistent Bookcase, I made some comparison for the performance of I/O function. scanf() and printf() cin >> and cout <<   Test Let’s start from C++ common way, below code uses cin >> and cout <<

It took 748 ms. Next, (old-school,) C way of implementation using scanf() and printf()

It took only 171 ms.   Result function time scanf() and printf() 171 ms cin >> and cout << 748 ms In this experiment, it appears that the speed of cin and cout is much much slower than scanf() and printf(), the difference is indeed quite huge. The overhead of cin and cout took more than 500 ms! You might get a […]

# AtCoder Regular Contest 060 review

Link ARC 060 top page Editorial C: Tak and Cards – 高橋君とカード Dynamic programming I could come up only full search using bit operation during the contest. But it can be solved by DP. Below is full score (Section 3.3 of editorial) implementation.

D: Digit Sum – 桁和 I came up different approach from editorial. Let $$a_i$$ be $$i$$-th digit with base $$b$$. Then, $$n = \sum_i b^i a_i$$ $$s = f(b, n) = \sum_i a_i$$ applies. If we subtract these equation, we obtain $$n – s = \sum_i (b^i – 1) a_i$$ Both side should be integer, and right hand side […]

# Chainer class introduction

Chainer is a library for deep learning. You can implement current trend network e.g. CNN (Convolutional Neural Network), RNN (Recurrent Neural Network) etc. Chainer official document * The post is written in 2016 July, with Chainer version 1.10, but Chainer is still in active development and some of the functionality specification may change in the future. Variable, functions, links and Chain At first, please read Introduction to Chainer. To summarize, input – output relationship of deep neural network is maintained by computational graph internally, which is constructed using Variable, functions, links and Chain. Once deep neural network is constructed, forward/backward propagation can be executed for training. VariableVariable will be used […]

# SeRanet: Quick start guide

This post explains SeRanet project, super resolution software through deep learning. Preparation Dependencies – third party library Install python, pip The software is written in python, and I’m using python version 2.7.6. If you are using OS Ubuntu 14.04, python2 is pre-installed by default. So you don’t need to install explicitly. The version of python can be checked by typing

in the terminal. If you can’t find python, then try below.

To install third party python library, pip command is often used. To install pip, type below in command line

Install popular libraries, numpy, scipy, matplotlib numpy, scipy, matplotlib are widely used for data processing in python. […]