Search in this blog
Showing posts with label Competitive Programming. Show all posts
Showing posts with label Competitive Programming. Show all posts

Wednesday, May 4, 2016

Tuenti Challenge 6 Solutions

Tuenti Challenge 6 has finished, I liked it more than the previous one (which I liked it a lot).

I didn't solved all questions but half of them, here is are brief details for them.

Here is the repository containing all the codes: https://github.com/AlexITC/tuenti-challenge-6

I will update this post if I solve another task, I hope you enjoyed the contest as much as I did.


Challenge 1 - Team Lunch:
You are given an integer N representing the number of dinners, you have to output the minimum number of tables required where all dinners can sit together.

One table can have up to 4 dinners, adding one table can have up to 6, so, each time we add a table, we can sit 2 extra dinners, as N is small, we can try every possible value using linear search or binary search the answer, there is a direct formula too.

Notice that N can be 0, so we need to handle this corner case.

Binary search code: https://github.com/AlexITC/tuenti-challenge-6/blob/master/01/TeamLunch.java


Challenge 2 - The Voynich Manuscript:
You are given a list of words and need to answer many queries, each query contains two integers L and R, and you have to tell what are the three most common words in the interval [L, R] (from the list of words).

The list of words if fixed and the number of distinct words is not so high, we can store the indices where the word occurs (for each distinct word), a query can be answered using binary search on each work having O(M * logN) time complexity (M is the number of distinct words and N the total number of times a words occurs).

Implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/02/TheVoynichManuscript.java


Challenge 3 - YATM Microservice:
You are given something that seems a code in a unusual programming language, the idea is to understand how it works and print the required output.

There are two ways to solve this problem:
1. Program an parser and a state machine to process all the code:
This would leads to a time consuming and a little bit boring task. Also is easy to made mistakes misunderstanding something in the logic.

2. Notice that the input is a well know format called YAML, the input represents a hash table, there are a lot of parsers for this format, having this, is really easy to code a simple state machine.

I didn't notice the format and coded the first idea, here is my long java code: https://github.com/AlexITC/tuenti-challenge-6/blob/master/03/Microservice.java


Challenge 4 - Hadouken!:
You have a fixed list with 5 strings and you are given a string S, you need to count how many times a string would match as a sub string in S if the last character is missing, in other words, count the number of partial matching requiring to change the last character to get a full matching, with the condition that you will try to match the longer string first.

The statement is confusing but you can throw the two longer strings from the fixed list and count the other 3 only, the strings are small, so brute force will work.

Implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/04/Hadouken.java


Challenge 5 - Hangman
This was an unusual but interesting problem, indeed it was one of my favorites, you are given an IP address, a list of words and a Hangman picture.

The given address uses Telnet protocol, connecting to it gives you an interactive hangman game, typing a letter updates the interface setting the positions where the letter occurs in the word or setting an error, you are required to complete the level before the time expires, completing a level move you to the next one having less time and a longer word, the idea is to write a program to play the game fast enough to complete all levels. One important thing is that the word to guess is in the given dictionary.

My strategy to guess a word is as follows:
1. Keep in a list all the words in the dictionary having the required length of the word to guess.
2. Find the letter occurring the most times in our list.
3. If the letter was correct, find the positions where the letter occurs and filter the list with the words containing that letter in these positions only (the list is reduced), continue in 2.
4. If the letter is incorrect, filter the list with the words not containing this letter, continue in 2.

I avoid to count letters already found to not repeat the same letter twice (in step 2).

My program is semi-automatic, it require me to press enter each time a level is completed, I used this to have time to copy the keys manually.

Here is my ugly implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/05/Hangman.java


Challenge 6 - Through the Looking-Glass
This was an interesting but frustrating task, you are given something that seems a QR image with a lot of noise.

I cleaned the image (with so many effort): https://github.com/AlexITC/tuenti-challenge-6/blob/master/06/result.png

The QR contains this URL: https://en.wikipedia.org/wiki/Piet_Mondrian

The interesting thing is that there is an Esoteric Programming Language called Piet, the noisy image seems to use the colors required by Piet, there are some interpreters online which didn't worked for me, you can try it yourself, or you can download and compile an interpreter.

Note than the image should be mirrored before giving it to the interpreter.

Also, for more information on Piet Mondrian, check out his page on Artsy: https://www.artsy.net/artist/piet-mondrian


Challenge 7 - Tiles
You are given a matrix of integers representing a tile in an infinite board, you are required to find a sub rectangle in this infinite board having the maximum possible sum or say that sum if infinite.

The sum is infinite if the sum in a row or the sum in a column in the matrix is greater than zero, this is true because the row or column can be used indefinitely and the sum will increase every time.

Assuming the sum is not infinite means that the rectangle is contained in the matrix or is a cyclic rectangle (a suffix + a prefix), we can copy the matrix three times to form a bigger matrix and find the maximum sub rectangle sum (which is a well known problem), this can be done with O(N^3) time complexity extending Kadane's algorithm.

Implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/07/Tiles.java


Challenge 8 - Labyrinth
This was another unusual but interesting problem which I enjoyed solving it, you are given an IP address allowing socket connections, it shows you a partial maze with 7x7 tiles, and your current position, you can traverse the maze using the letters 'u', 'd', 'l', 'r', each time you move, the partial maze is scrolled revealing new tiles.

In this challenge you need to get the key which is in the borders of the maze, so you have to explore the whole maze, to make the things more interesting, once a connection is started, it will be expired after 13 minutes.

I used two algorithms, one going always to the left and the other going to the right, after each move I save the new tiles, each algorithm discovered more than half of the maze, after storing the results in a file I merged them into a single one to recover the key.

Implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/08/Labyrinth.java


Challenge 9 - 0-1 Immiscible numbers
You are given an integer N, and you have to find the smallest multiple of N composed by ones and zeros only, the ones should occur before zeros.

There is an interesting property I found which I can't proof: any integer X not divisible by 2 or 5 have a multiple composed of 1's only, this multiple is the smallest for our problem.

Another property: Any integer of the form 2^N or 5^N or have a multiple containing exactly N 0's.

The second property tend to be really useful, for any integer X the number of zeros is max(twos, fives), where X is divisible by 2^twos and 5^fives.

We can count the number of zeros required and reduce the number removing prime factors 2 and 5, counting ones can be done with a linear time algorithm, this is quite slow for bit cases but is enough to get the output required.

Implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/09/ImmiscibleNumbers.java


Challenge 12 - Pika Virus
You are given two trees and have to check they have the same topological structure, in order words, check is they are isomorphic, there are not so hard algorithms to check this in polynomial time, the constraints are small so we can try a simpler and slower approach.

If the trees are isomorphic we are required to match each node from a tree with the one lexicographically smallest node from the other tree, and the ancestors doesn't need to match. This crazy condition made me to loss several hours trying to figure out why my output was not the expected one, and as I saw in twitter, my case was not the only one.

Implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/12/PikaVirus.java


Challenge 14 - SpeedRunner
You are given a matrix representing a board game, there are some rules defined about the movements. In brief, you are standing in a tile and want to exit, before exit you need to grab all the keys, print the minimum amount of frames to exit breaking times with keys pressed, breaking ties with the lexicographically smallest string of keys pressed.

The maximum number of keys is 16, so we can use dynamic programming with bit masks to find the optimal order to grab the keys (see Traveling Salesman Problem), we need a function to compute the optimal path from a tile S to a tile T, removing the lexicographically constraint, a simple Dijkstra's algorithm will work.

We can compute the optimal route from any tile to the tile T (reversing the graph leads to a single Dijkstra), after this we start at S reconstructing the optimal path to reach T, in each step we choose a tile being in one of the optimal paths and keep the lexicographically smallest.

You need to take care implementing this because the code is long and can be tricky.

Implementation: https://github.com/AlexITC/tuenti-challenge-6/blob/master/14/SpeedRunner.java
Posted by at No comments:
Labels: ,

Sunday, October 25, 2015

Competitive Programming Resources

Competitive Programming / Programming Contest Resources for learning things

This list is going to be edited frequently when I find good resources to learn things.

Tools:
Graph drawing: http://mxwell.github.io/draw-graph/


Improving in CP


Dynamic Programming Optimization Problems:
http://codeforces.com/blog/entry/47932

Non Trivial DP tricks:
http://codeforces.com/blog/entry/47764

Slope Trick:
http://codeforces.com/blog/entry/47821

Floyd Warshall:
https://www.quora.com/Why-is-the-order-of-the-loops-in-Floyd-Warshall-algorithm-important-to-its-correctness/answer/Jayaprakash-Sundararaj

Manacher's Algorithm:
https://www.quora.com/What-is-Manachers-algorithm-How-can-we-use-it-to-find-all-palindromic-sub-strings-in-a-string

Meet in the middle:
http://qr.ae/R3GIji


Suffix Array - Linear time construction (DC3) explained:
http://qr.ae/R6EeWR

Fractional Cascading:
http://codeforces.com/blog/entry/21892
http://www.cs.uu.nl/docs/vakken/ga/slides5b.pdf (Page 43)


Bipartite Matching:
http://www.slideshare.net/KuoE0/acmicpc-bipartite-matching?next_slideshow=1


Algorithms and Data Structures Implementations:
https://sites.google.com/site/indy256/


Suffix Automaton
http://codeforces.com/blog/entry/20861

Binary Indexed Tree for Range Minimum Query
http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

Binary Indexed Tree for coefficients in functions:
http://apps.topcoder.com/forums/?module=Thread&threadID=756271


SQRT Decomposition


Combinatorics:

Trie

Sweep Line


SPOJ Must Solve problems

Centroid Decomposition


Competitive programming courses


Matching in general graph

Matrix Power


Matrix Power alternative using DP

Treap


Splay Tree

Segment Tree

2D Segment Tree

Persistent Segment Tree

Ordered Sets



Data Structures

Map Short Permutation (11, 12 items) to integer

Segmented Sieve


Dynamic Connectivity

Aho-Corasick

Find primes in some interval


Suffix Tree

Suffix Array


Sieve Methods


2-SAT


Graphs

FFT
http://codeforces.com/blog/entry/14744 
http://codeforces.com/blog/entry/20751
http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt

MO’s Algorithm

Game Theory

Manacher’s Algorithm

Minimum Diameter Spanning Tree

Dynamic Programming (DP)

DP with bitmasks

DP over integers

DP Optimizations



Heavy Light Decomposition
http://blog.anudeep2011.com/heavy-light-decomposition/

Ternary Search


Trie

Z-Algorithm


Nim Game
http://web.mit.edu/sp.268/www/nim.pdf


World Finals 2015 solutions

Andrew Stankevich Contests

Regional Contests with editorial

Training Advices

Saratov University Notebook


Complex Numbers in Geometry
https://uqu.edu.sa/files2/tiny_mce/plugins/filemanager/files/4041834/cnum_mr.pdf





Link-Cut Tree
http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
http://www.cs.cmu.edu/~avrim/451f12/lectures/lect1009-linkcut.txt

Burnside's lemma
http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html



Posted by at No comments:
Labels:

Sunday, October 4, 2015

The 2015 ACM-ICPC Caribbean Local Contests (Real contest) Solutions

The 2015 ACM-ICPC Caribbean Local Contests (Real contest) and Gran Premio de México & Centroamérica Fase III happened in 2015/10/26.

I will explain my way for solving all the problems here, if you don't understand something or have a question don't dude to ask.

If you have a different / better solution, share it with us.

THE POST IS NOT FINISHED, I WILL DO IT AS SOON AS I CAN.

I hope this can be useful for you.


The problems can be solved in COJ.
A. Naebbirac Phrases (Trivial)
B. Careful with Poison (Combinatorics)
C. Counting Figures (Ad-hoc, Sweep line?)
D. Dr. B - Tree II (DP)
E. Even Number of Divisors (Number theory, Binary Search)
F. Fast Traveler Game (Simulation)
G. Fear of the Dark (HLD, Segment Tree)
H. How Many Numbers (Backtracking)
I. List of Natural Numbers (Find the pattern)


A - Naebbicar Phares

Read two string S and T and count how many characters are different in S and T at same index, for example if S = "alex" and T = "alxs" answer is 2, is guaranteed that length of S is equal to length of T, the letters in black are the mismatches.

Here is my code.

B - Careful with Poison

First how to solve the problem without the square? Binomial Coefficient is you friend.

Let ways(N, K) = number of ways to choose K elements from a set of N.

This will ignore the square, we have to use the Inclusion Exclusion Principle to remove the invalid ways.

To do this, let represent the square as 9 points in the grid:

ABC
DEF
GHI

The points "C", "E" and "G" are exclusive, this means that if our path can pass only from one of these three points.

Let count(N, a, b) = the number of ways to get from point (0, 0) to point (N, N) passing the point located at (a, b), this can be broke in the number of ways to get from (0, 0) to (a, b) multiplied by the number of ways to get from (a, b) to (N, N).

Now to remove the invalid ways we can use the previous function and the result is = ways(N, N) - count(N, Cx, Cy) - count(N, Ex, Ey) - count(N, Gx, Gy).

Notice that N can be large and is an obvious overflow, we are required to compute the result modulo a prime number, this help us to use modular arithmetic to compute the answer, we can pre compute all the factorials between [0, MAX] MOD M and compute the binomial coefficient using the modular inverse.

Complexity is O(1) per query if you precomputed the modular inverse or O(log(N) ) computing it as required.

See the code for further details.

Here is my code.


C - Counting Figures

This problem can be solved detecting only the figures of 4, 6 and 8 sides.

A figure have 4 sides if is a completed rectangle:

XXXX
XXXX
XXXX

The X is a filled point.

A figure have 6 sides if filling a subrectangle in a corner makes a complete rectangle:

XXEE
XXEE
XXXX
XXXX

The E is an empty point.

A figure have 8 sides if require two corners to be filled as rectangles to build a complete rectangle or if requires to fill a rectangle starting in a side but not in a corner, see the examples:

XXEE
XXEE
XXXX
XXEE

Or

XXXX
XXEE
XXEE
XXXX

This is an easy to find solution but really tedious to code, i'm trying to get a better and shorter approach, my code is around 300 lines long.

THIS WILL BE UPDATED WITH A BETTER SOLUTION.

Here is not my code.




D - Dr. B - Tree II

Let ways(L, K) = number of ways to make a string of length L with exactly K mirror couples, Z is the number of different characters allowed being 10 in this case (all the digits from 0 to 9).

If L is odd that means we should place the middle character of the string and then solve the problem for a string of even length, we can place this in Z ways and only if K > 0 because always this character will be a mirror couple, example, X is the character to place.
...X...

If L is even we can split the string in two parts of length L/2 (left and right) and place exactly two characters, one in left part and one in the right one, in this way we can decide to place a mirror couple or not, for example.

X....X

In this case we are setting a mirror couple and there are Z ways to do it.

X....Y

in this case we are setting two character being not a mirror couple, there are Z*(Z-1) ways to do it, you can place every character at X and every character but X for Y.

Here is a pseudocode:

 ways(L, K)
 if (L == 0 && K == 0) ret 1
 if (L < 0 || K < 0 ) ret 0
 if (L is odd) ret Z*ways(L-1, K-1) 
 ret Z*ways(L-2, K-1) + Z*(Z-1)*ways(L-2, K)

The complexity is exponential but you can memoize the results using Dynamic Programming to get a complexity of O(L*K).

Don't forget to do all operation with modulo.

Here is my code.



E - Even Number of Divisors

We are given an interval [L, R] and we have to count how many numbers K in that interval have even number of divisors, for example, the next list contains the required information for the values in the interval [1, 6]:

K = 1 2 3 4 5 6
D = 1 2 2 3 2 4
C = n y y n y y

K is the value we want to know if should be counted.
D is the number of divisors of K.
C is "y" if have and even number of divisors (should be counted).

This is not an obvious task but we can invert the problem.

Let f(L, R) = the number of values K in the interval [L, R] where the number of divisors of K is odd.

If we can compute f efficiently, the answer would be (R - L + 1) - f(L, R), (R - L + 1) is the length of the interval.

How to compute this? The trick is that a number K has odd number of divisors if K is a perfect square (see this to believe), there is at most sqrt(N) perfect squares in the interval [1, N], so we can pre compute all perfect squares in this interval (where N is the maximum possible value) and store it in an array.

For answer a query f(L, R) = firstLower(R) - firstHigher(L) + 1

firstLower(N) = the index of the last element in the array strictly <= N
firstHigher(N) = the index of the first element in the array strictly >= N

Both can be computed using binary search.

The complexity is O(N*log(N) ) where N = sqrt(max possible number).

Here is my code.


F - Fast Traveler Game

This is a simulation problem, do what is required and you will get accepted your solution.

Here is my code.


G - Fear of the Dark

This is not an easy problem, you need to know about several non-trivial data structures:
Once you about all of them the problem may seem trivial but code it without mistakes is not easy.
I hope to have the time to explain it better later.

First you need to solve FLIPCOIN in order to prove you understand how to write the required Segment Tree for this problem.

Complexity is O(N * log(N) + Q * log(N) * log(N) ) where N is the number of nodes and Q the number of queries.

Here is my long and modulated code.

H - How Many Numbers

You are given two variables, O and E, you have to count how many distinct numbers can be formed using exactly O odd digits and E even digits, including negative numbers, O + E <= 18.

This is an easy problem solvable with backtracking because the constrains are small.

Is obvious that we can count only the positive numbers and multiply the result by 2.

There are two especial cases to handle here.
1.- The number can't have leading zeros.
2.- If O = 0 and E = 1 means that we need to count all even digits and the number of digits = 1, this means that we have to add 1 to the result for counting the zero, the result for this case is 9, 4 possible even digits positive and negative + the zero.


Understanding the 2 above cases makes easy to design a solution.

Suppose you have a case where O = 1 and E = 1, X and Y are both digits, we need to place them.

XY

The two possibilities are that X is and even digit and Y is an odd digit or X is and Odd digit and Y an even.

The first case is to place an odd digit at X position and an even digit for Y.
There are 5 odd digits for X (1,3,5,7,9) and 5 even digits for the Y position (0,2,4,6,8), so the total is 5*5.

The second case is to place an odd digit at X position and an even for Y.
There are 4 options for X (2,4,6,8) because the number can't start with zero and 5 options for Y, so the result is 4*5.

The answer is 5*5 + 4*5 for positive numbers, so muliply it by 2 to get the required result.

Now we need write a function for the general case.

f(first, odds, evens)
 if (odds == 0 && evens == 0) ret 1
 ans = 0
 if (odds != 0 ) ans += 5 * f(false, odds - 1, evens)
 if (evens != 0) ans += 5 - (first ? 1 : 0) * f(false, odds, evens-1)
 ret ans

This help us to find the answer for positive numbers, handle the case 1 0 outside this.

In this solution we are avoiding to create numbers with leading zeros but there is other way for do it, you can count all the numbers with leading zeros and subtract the numbers starting with zero, use what you prefer.

Be careful because the result doesn't fit in an Integer data type but a Long is enough.

The complexity is O(2^N) per case, where N = E+O

Here is my code.


I - List of Natural Numbers

We can notice that a number K will be added only in the K-th step, using this information we can generate using brute force how many times a number K is added to the list for some steps like 20 for example.

This is the result for the first 15 values.
2, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8

There is no obvious pattern but we can use OEIS and paste this values as input, OEIS will try to find a sequence, fortunately there is a sequence =D.

 The number of times a value K is in the final list is:
  • 2 if K = 1 
  • phi(K) if K != 1
Phi is the Euler's totient function and can be computed in O( sqrt(N) ) which is acceptable for this problem, learn about it.

 Complexity is O( sqrt(N) ) per case.

Here is my code.




Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)