serialn   3년 전

59682566번 제출 코드를 보시면 노골적으로 확인할 수 있습니다.

입력을 받고 처음 입력된 사원부터 시작해서, 사원의 직속상사, 직속상사의 직속상사... 이렇게 꼬리를 물고 검색하다가 자신이 그 상사가 되면 return 1;로 NZEC 에러를 일으키는 코드인데요.

NZEC 에러가 납니다.

2%에서 런타임에러 나버리는 제 알고리즘의 채점에 납득이 가지 않아 채점 데이터가 이상한 것 같다고 생각하고 assert문과 return 1; 을 이용해 고의로 에러를 일으켜서 여러 번 점검해본 결과 첫 데이터는 100,000명의 사원을 입력시키고, 그 중 87500~95000명의 사원이 자기 자신을 상사로 두고 있는 것 같습니다.

문제대로 '아래에서 위로(바텀-업)' 공정이 불가능한 구조입니다.

또 이 87500~95000명에는 사장이 포함되지 않는데, 문제에 의하면 사장이 작업을 마치지 못하면 작업은 완료되지 않습니다.

문제가 이상하거나 데이터가 이상한 것 같아 제보합니다. (제출이 1600개인데 정답이 없는 이유인 듯 합니다.)

wnwoghd22   3년 전

저도 이 저주받은 문제에 영혼이 묶여있긴 하지만... DAG로 사장을 루트로 하는 트리를 만들어서 순회를 했을 때 전체 사원 수 만큼 방문하는 것으로 보아 사이클이 존재하는 것 같지는 않습니다. 단순 스케줄링 문제가 아직도 안 풀리는게 좀 이상하긴 하네요.

serialn   3년 전

데이터가 문제든 이 문제에만 채점 서버가 오작동하는 거든 간에 문제가 있어보입니다. 200바이트도 안 넘는 간단한 C코드로 입력 첫번째 사원부터 시작하는 사이클의 존재를 보일 수 있는데요. 풀이도 아닌데 소스 여기 적을 수도 없고 난감하네요. 다들 한 번 해보시길 권합니다.

serialn   3년 전

(어제 59682566번 제출의) 디버깅 과정을 조금 정정하자면 처음 입력된 사원(1번)에서 시작하지 않고, 처음 입력된 사원의 상사(입력 배열의 0번 인덱스)에서 시작했습니다. 번호가 1번부터 시작한다는 것을 유념하고 각 인덱스에서는 1을 미리 빼거나 인덱싱할 때 뺐습니다. 오늘 assert문으로 테스트해본 결과(59696795번 제출) 처음 입력된 사원의 상사는 100000번임을 알 수 있었습니다. 하지만 고리이므로 예상한 대로 0에서부터 시작해도(59697489번 제출) 결과는 같습니다. 고리에는 100000번과 1번 사원이 포함되어있기 때문입니다.

serialn   3년 전

assert문을 정반대로 알고있었네요...

댓글을 작성하려면 로그인해야 합니다.