[Codeforces] Avito Code Challenge 2018

http://codeforces.com/contest/981

 

3시간 / 8문제 대회였습니다. ABC는 맞았으나 D에서 for문의 범위를 N까지 돌아야하는데 N-1까지 돈 것이 하나 있어서 System test에서 나갔습니다. A,B,C 모두 한 번에 맞췄습니다.

 

A - Antipalindrome

 

길이가 50밖에 안되니 그냥 모든 substring에 대해 계산을 해도 되고, 모든 글자가 같으면 0, 자기 자신이 palindrome이면 len-1, palindrome이 아니면 len입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Avito%20Code%20Challenge%202018/A.py

 

B - Businessmen Problems

 

마치 merge sort에서의 merge와 비슷하게 두 배열을 index 순으로 정렬해두고 추가해나가면 됩니다. 이외에도 map에 전부 넣어두고 동일한 원소가 들어오면 큰 값을 택하는 식으로 풀이할 수도 있습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Avito%20Code%20Challenge%202018/B.cpp

 

C - Useful Decomposition

 

문제가 이해가 안 가서 조금 당황했는데, 쉽게 생각해서 그래프가 불가사리 모양인지를 체크하는 문제입니다.(한 점으로부터 방사되는 형태) degree가 3 이상인 element가 2개 이상이면 No, 그렇지 않다면 degree가 가장 큰 element를 root로 잡으면 됩니다. 간단한 문제인데 빨리 캐치하지 못한 것이 너무 아쉽네요.

 

https://github.com/blisstoner/Codeforces/blob/master/Avito%20Code%20Challenge%202018/C.cpp

 

D - Bookshelves

 

APIO 2015년 1번 문항 (https://www.acmicpc.net/problem/10846)과 거의 동일한 문제입니다. 특정 value에 대해 $D[i][j][k]$를 $a[i] to a[j]$를 $k$개로 쪼개서 value를 만들 수 있으면 True, 불가능하면 False라고 정의해봅시다. 이 때 각 $D[i][j][k]$를 $O(j-i-k)$에 구할 수 있습니다. 이제 답의 MSB부터 LSB까지 value가 가능한지 확인합니다. 예를 들어 $2^{60}$이 가능하면 $2^{60}+2^{59}$가 가능한지 확인하고, $2^{60}+2^{59}$이 불가능하면 $2^{60}+2^{58}$이 가능한지 확인하고, $2^{60}+2^{58}$이 가능하면 $2^{60}+2^{58}+2^{57}$이 가능한지 확인하고.. 이런식으로 진행하면 $O(60N^3K)$에 구할 수 있습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Avito%20Code%20Challenge%202018/D.cpp

 

물론 주황에서 떨어질 것을 각오하고 쳤긴 했지만, D가 나간게 많이 아쉽네요 ㅠ_ㅠ