Google Code Jam 2019 - Qualification Round

This weekend, I have participated at the Google Code Jam contest. You only needed to get 30 pts to attend the next round !

For the first question : Because each number always has a the number 4 in it, we can just :

create (initialise) string A and string B
for each digit in the number :
     if the digit is a 4 :
          put '1' in string B
          put '3' in string A
     else :
          put the digit in string A

For the second question : It is a pretty easy question. The idea is just to replace 'E' by 'S' and 'S' by 'E':

read the string s
for each character c in s :
     if c == 'E' :
         print 'S'
     else :
         print 'E'

For the third question : just use Euclid's gcd !

Have a look at the official editorial for question 3 and 4 :

https://codejam.withgoogle.com/2018/challenges/0000000000051705/analysis/000000000008830b
https://codejam.withgoogle.com/2018/challenges/0000000000051705/analysis/00000000000881de

Here is my youtube video (doing A and B) : https://youtu.be/0k4q1SMSYSo

Info (1) Cup 2019

This is one of the not interactive question. (2 out of 4 questions are interactive questions). You can try it !

InfO(1) CUP 2019 Third edition International Round

COSTINLAND

Costin is the dictator of Costinland, a country located on a very small island in the middle of Pacific Ocean. One day, Costin started feeling depressed because his island was very small. In order to stop his own depression, he decided to conquer other countries, so that the territory of Costinland and his influence as a dictator

will be even bigger! In order to do that, he needs an army! But no citizen of Costinland fits the dictator’s requirements... So what army would be better than an army of Costins? Thus, being the smartest person living in Costinland, he invented cloning on a Saturday evening. Being a very playful person (the most playful person in Costinland), he wanted to play with his clones while creating them.

Maximum time of execution: 0.5seconds/test. Maximum available memory: 64 MB

For that, Costin chose a piece of land consisting of N x M cells. There are 4 types of cells:“X” (if a Costin steps on this cell, he clones himself; one of the Costins goes right and the other one goes down), “r” (if a Costin steps on this cell, he will go right, regardless of his initial direction), “d” (if a Costin steps on this cell, he will go down, regardless of his initial direction),“.” (if a Costin steps on this cell, he will not change his initial direction and will move to the next cell indicated by his direction).
Costin leaves from (1,1) and wants to reach (N,M), along with all of the created clones. Costin is also very lazy (the laziest person in Costinland), so he asks you “nicely” to help him build such a matrix, such that exactly K clones will reach (N,M). Clones cannot be “lost” on their way (read the constraints carefully).

TASK

Given K, help Costin generate such a (small) matrix that will bring to (N,M) exactly KCostins.

INPUT FORMAT

The first line contains one integer: K.

OUTPUT FORMAT

The first line will contain to integers: N, M (the size of the matrix). The following N lines will contain M characters, describing the matrix.

Page 1 of 3

CONSTRAINTS

•   The character situated on (1,1) must be different from “.”, in order to give a direction
  to the first Costin. (It can be “X”, “d” or “r”)
•   None of the Costins stops until he reaches (N,M).
•   In order not to waste Costins or to lose them somehow during their path, the last line
  of the matrix will consist only of “r” and the last column will consist only of “d”. By exception, the character situated on (N,M) will be “.” (There is no need to give the Costins a direction since they reached their destination)
•   In order to get 100 points, you need to generate a matrix with both of its sides smaller than or equal to 5, for the first subtask, and one with both of its sides smaller than or equal to 49, for the second subtask (more details below in the SCORING section).

Subtask	Score	Restrictions
1	20 points	3 <= K <= 19
2	Another 80 points	19 < K <= 1018

The scoring is very hard to read on the blog, sorry.

SCORING:
Let CxD be the contestant’s matrix size. Subtask 1:

•   If max{C,D} <= 5, you will receive 100% of the points on that test case.
•   If max{C,D} = 6, you will receive 60% of the points on that test case.

                                                                                         If 6 < max{C,D} <= 500, you will receive 60*𝟓𝟎𝟎−𝒎𝒂𝒙{𝑪,𝑫}/500/6 % of the points on

that test case. If max{C,D} > 500, you will receive 0% of the points on that test case.

Subtask 2: If max{C,D} <= 49, you will receive 100% of the points on that test case.

 If 49 < max{C,D} < 62, you will receive 60+40*1.262−max {𝐶,𝐷}/1.262−49 % of the points

on that test case. If max{C,D} = 62, you will receive 60% of the points on that test case.

𝟓𝟎𝟎−𝒎𝒂𝒙{𝑪,𝑫} If 62 < max{C,D} <= 500, you will receive 60* 𝟓𝟎𝟎−𝟔𝟐 % of the points on

that test case. If max{C,D}>500, you will receive 0% of the points on that test case.

Page 2 of 3

COMPILER MESSAGES:

•   "The output does not fit the requirements": You will get this message if your
  matrix does not respect the CONSTRAINTS or the OUTPUT FORMAT.
•   "Matrix size too big": You will get this message if max{C,D}>500.
•   "The matrix does not generate the required number of Costins": You will get
  this message if, in the end, there won’t be exactly K Costins in (N,M).
•   If you don’t get any of these messages, you will receive a score according to the formulas from above and a message which specifies the size of your generated matrix for that test case.

EXAMPLE:

Input:
11
Output:
4 4
XXXd
.XXd
.XXd
rrr.

Programming Competitions and Training 1

Competitions

International competitions

IOI

Most people who are less than 18 years old are aiming for the IOI. IOI is also called International Olympiad of Informatics. The IOI contest is taking place at a different country each year. Here is the IOI website : https://ioinformatics.org

Google Code Jam

Google Code Jam is a competition organised by Google each year. To participate the next round, you need to be qualified from the previous round. Participants are automatically qualified for Round A. By doing well in this contest, you can get contacted by Google. Top participants can get a T-shirt and top 25 participants can go to the on site final. Some of the finalist can get a prize. The Google Code Jam website : https://codingcompetitions.withgoogle.com/codejam

Kickstart

Kickstart is another Google competition organised almost every month. By doing well in this contest, you can get contacted by Google. There are no finals and you don't need to be qualified to attend the next round. Here is the Kickstart website : https://codingcompetitions.withgoogle.com/kickstart

Hash Code

Hash Code is also a Google competition organised each year. The difference between other contests and this one is that : you need to have your own team ! Hash Code has got on site finals ... The Hash Code website : https://codingcompetitions.withgoogle.com/hashcode/about

Top Coder

Top Coder offers regular (almost every week) competitions and a on site final. Here is the Top Coder website : https://www.topcoder.com/community/competitive-programming

ICPC

The International Collegiate Programming Contest is an algorithmic programming contest for college students. Teams of three, representing their university, work to solve the most real-world problems, fostering collaboration, creativity, innovation, and the ability to perform under pressure. Through training and competition, teams challenge each other to raise the bar on the possible. Quite simply, it is one of the oldest, largest, and most prestigious programming contest in the world just like the IOI. Here is the ICPC website : https://icpc.baylor.edu


Fario

This is a France and Australien competition. This competition is held every year, and the team leaders from the two teams pick some people via the two training sites : France IOI and Orac. Here is the Fario site : http://orac.amt.edu.au/fario/

European competitions

If you are a bit younger, you can aim for the eJOI (Europe only) who is another competition much easier then the IOI. eJOI just like the IOI is taking place every year in a different country. eJOI is the initials for European Junior Olympiad of Informatics. Here is the 2018 eJOI website : http://ejoi2018.org

Training

CodinGame

This is a french coding website. The thing is that you learn while you are playing. So, check it out : https://www.codingame.com/start

Codewars

You can sharpen your skills with Codewars ! The Codewars website : https://www.codewars.com

Kattis

Kattis is a great training website. Here is the link : https://open.kattis.com

NOI

NOI is a chinese training website. The link to the website : http://www.noi.cn

USACO Training

USACO also has a training gateway website to prepare for the USACO contests. Here is the USACO website : https://train.usaco.org/usacogate?a=oxuybwibj5z

Orac

Orac is a australien training website.
The link to the website : http://orac.amt.edu.au/cgi-bin/train/hub.pl

Luo Gu

Luo Gu is another chinese training website. Here is the link : https://www.luogu.org

Leetcode

Leetcode is not a competitive programming website (more a interview website) but it has a lot of exercises. It also organises weekly constests. Here is the website : https://leetcode.com

UVA

UVA is one of the best programming website. Here is the link : https://uva.onlinejudge.org

Hacker Rank

Hacker Rank is a great training website. Here is the Hacker Rank website : https://www.hackerrank.com/dashboard

SPOJ

SPOJ is another great training website. Here is the link : https://www.spoj.com/problems/

Codeforces and Codechef

They have some great problems ! Here's the link to codechef : https://www.codechef.com/contests/
And for codeforces : https://codeforces.com/

Project Euler

Last but not the least is Project Euler ! This website is a mathematical and programming website :  https://projecteuler.net

Google Kickstart Practice 2019

Google Kickstart is a competition organised by Google. The top competitors from Kick Start rounds may be invited to interview at Google ! Each Kick Start Round is open to all participants, no pre-qualification needed, so you can try your hand at one or give them all a shot.

The Practice round of Google Kickstart has already finished. By the way the algocorner team is ranked 411.

Practice round (idea) analysis :

The first question is a interactive question and the algorithm is just a simple binary search in log(n) per test case.

The second question can be done by a sliding window maximum algorithm or a partial sum.

The third question can be done by using Fermat's little theorem but the implementation of the idea is pretty hard.

Don't forget that there is also Round A the 24 March. Here is the link to the Kickstart Schedule : https://codingcompetitions.withgoogle.com/kickstart/schedule

This is one of Google's coding competition.