올해도 아쉽게 끝났다.. cut line 조금 뒤에서 간당간당. 내년에는 R1C 쯤에서 통과할 수 있을 것 같다.

  1. 영어 읽기에 시간을 너무 쓴다.
  2. pycharm file input redirection을 빨리 만드는 방법도 필요
  3. template도 만들어두고, print(*args, file=sys.stderr, **kargs) 도 추가하기. class 자동 출력하기
  4. 평소에 typing 빨리 하는 습관을 들여야겠다. vi도 더 빨리 잘 쓰기.

2020 R1A

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

Pattern Matching

다행히 일찍 좋은 생각이 났다.

더보기

*가 중간, 또는 끝에 있는 경우를 나눠서 생각하고

대충 다 붙여서 아무거나 만들어내기

 

Pascal Walk

더보기

운 좋게도 level L에서 2^n 또는 L까지 2^n -1을 만들 수 있는 것은 비교적 금방 생각했다.

그런데, N과의 약간의 차를 해결하지 못했다.

 

한편, test set 1 풀이도 생각을 했었다. 왼쪽 또는 오른쪽 가장자리 1을 이용하기.

그럼에도 불구하고, 이게 test set 3의 "N - 2^n 차" issue를 해결할 수 있는 hint가 되리라고 생각을 못했다. 조급해 하기만 했다.

 

결국, 다른 (어려운) 방법으로 해결해보려고 시간을 너무 보냈다. 가운데로 내려가서 옆으로 올라왔다가 마지막 숫자를 맞추기... 불가능한 방법일지도.

 

Square Dance

 

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1355

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

문제를 정확히 이해 못했었다. test set 2 풀이를 생가하기에는 시간도 모자라서 포기했다.

나중에 youtube 해설을 찾아보기

 

 

2020 R1B

Expogo

막 풀다가 문제를 잘 이해 못했었던가? 잘 기억 안난다. 자꾸 틀려서 말렸다.

나중에 youtube 해설을 찾아보기?

 

Blindfolded Bullseye

잘못 생각했다.

나중에 youtube 해설을 찾아보기

 

Join the Ranks

잘 모르겠더라. 생각한 방법으로는 잘 안 풀렸다.

나중에 youtube 해설을 찾아보기

 

2020 R1C

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

CDT 새벽4시에 일어나지 못하고, 30분 쯤 늦게 시작했다.

 

Overexcited Fan

쉬워보였고, 생각은 금방 했는데, 왠지 모르지만, WA가 자꾸 나왔다.

여러 test case를 만들어서 시간을 많이 들여도 bug를 못 찾았는데, 다시 시도했더니 통과했다 T_T

"IMPOSSIBLE"의 spell이 틀렸었나..

 

Overrandomized

문제를 이해하는 데 시간이 너무 오래 걸렸다. 예제가 1개밖에 없어서 문제를 다 해석해야만 했다.

풀이는 생각보다 쉬웠다.

괜히 무리하게 고점을 노리고 3번 문제부터 풀어보다가 나중에 돌아와서 이 문제를 급하게 풀었는데 마지막 1분이 모자랐다..

일찍 일어났으면 통과했을텐데 아쉽..

 

test set 1, 2를 참고는 하되, test set 3부터 노린 것은 유효했다.

test set 3을 풀면, 1, 2는 저절로 풀렸다.

 

Oversized Pancake Chappers

 

https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003172d1

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

너무 어렵게 생각했는지도 모르겠다. 어려우면 빨리 다른 문제로 넘어갔어야 했다.

test set 1은 비교적 쉬울 것 같은데, 마지막에 이것만 시도할걸..

더보기

A_i를 2^k 수준의 group으로 나눠서, 위 group을 쪼개면 아래 group partition으로 나눠진다고 생각했다. 이런 식으로는 풀기가 너무 어려웠다.

일부를 덜어내고 반으로 잘라야만 빨리 같은 많은 조각을 생성한다고 생각했는데, 이것도 잘못된 생각이었다.

해설을 읽어보니, 나누어 떨어지는 D, fully-usable slice를 빨리 찾는 게 도움이 되나보다.

 

나중에 youtube 해설 찾아보기

 

 

1,2번 문제를 빨리 풀면 통과 가능했다.

또는 1,2 full로 풀고, 3::test_set_1 풀기.

 

by 언제나19 2020. 5. 2. 22:38

2020 R1 A 시작 전에 연습

 

2018 R1B

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007764/0000000000036601

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

풀다가 large data set을 못 풀어낼 것 같아서, 해답을 봤다. 좀 더 과감하게 중요한 부분만 직관적으로 생각할 걸 그랬다. 

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007764/000000000003675b

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

문제를 이해하기가 너무 어려워서 포기

 

analysis와 https://www.youtube.com/watch?v=BFr6bGLq3r4 해설을 봤더니, 문제를 이해했으면 비교적 풀기 쉬었을 것 같다.

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007764/000000000003675c

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

이것도 영어 이해하기 헷갈리게 왜 lead가 귀하다고.. 엄한 데 시간이 든다.

생각한 방법을 구현하다가 Test set 3를 풀려면 구현이 너무 복잡할 것 같아서 해답을 봤다.

analysis를 봤더니, 생각한 방법이 Test set 2만 풀 수 있는 방법이었나보다. 차례로 잘 소비하면 3도 풀 수 있을 것 같은데...

Test set 3용으로는 완전 색다른 풀이 방법이 있었다.

 

https://www.youtube.com/watch?v=c2yuORofkAw 31분쯤을 보니, 이 분도 조금은 비슷하게 생각하신 듯

듣고 보니, Test set 3용 풀이가 생각보다 simple하게 구현할 수 있고, 실행 시간도 적게 걸리네.

 

 

 

R1C

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007765/000000000003e064

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

더보기

각 위치의 글자가 어느 단어에 속하는지 기록하고, 글자를 이어갈 때마다 속하는 set의 교집합을 구해서 교집합이 null이면 해답이 나오도록 풀려고 했다.

각 2개 sub단어에 대해서만 만족한다면 긴 단어에서도 만족하게 될테니, 글자를 이어갈 필요가 없겠는데, 그렇지 않은 경우도 있겠다 싶었다.

divide and conquer가 실행속도를 더 빠르게 할지 생각하고 있었다.

 

해답은 썰렁했다.. 왜 점수가 저만큼 높은지 모르겠네.

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007765/000000000003e068

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

는 문제를 잘 이해를 못했다. 어려운 것 같지는 않다. skip.

더보기

 

online algorithms

https://www.youtube.com/watch?v=IyWOjd-oZ4o&list=PLjbPFHE4z0zcsmzMPOg-J16SIDS3t0ylw

bipartite matching이랑도 관련이 있다길래 찾아봤는데, 무슨 관련이 있는지 잘 모르겠다.

 

https://www.youtube.com/watch?v=dorq_YA6plQ&list=PLEGCF-WLh2RJh2yDxlJJjnKswWdoO8gAc&index=2&t=0s

lesson 2부터는 녹음이 잘 돼있어서 소리가 크게 잘 나온다.

 

https://www.youtube.com/watch?v=0CdxkgAjsDA

https://www.youtube.com/watch?v=GhjwOiJ4SqU 

https://www.youtube.com/watch?v=HWHjQdNC-7Y

 

 

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007765/000000000003e0a8

 

Code Jam - Google’s Coding Competitions

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

codingcompetitions.withgoogle.com

더보기

DP까지는 생각했는데, test set 1 밖에 풀 수가 없다.

test set 2에서는 max(W)를 무한정 늘어나지 않게 하는 trick이 있었다.

 

DP를 연습삼아 풀어보는 것도 좋겠다.

 

 

by 언제나19 2020. 4. 10. 14:11
| 1 2 3 4 5 6 7 ··· 199 |