루미 알고리즘

#1620골드Love Letter

PO 2025 온라인 예선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Mio and Sara come from two very different families. In Mio's family, everyone wears hats shaped like rectangles, while in Sara's family, everyone wears triangular-shaped hats. This difference in taste has led to feuds that have lasted for generations. Despite this, Mio and Sara happened to meet one day and fell in love at first sight.

Since it is difficult for them to meet, they instead send messages to each other to communicate. Because they are very secretive, we do not know exactly how the devices they use to communicate work. However, we do know a few things: when Sara wants to send a message, she types it in as a sequence of ones and zeros into her device, and then it sends the message. Unfortunately, bad weather can cause problems. When the machine sends ones and zeros during bad weather, it sends the exact opposite. For example, if the weather is bad and the machine tries to send a 0, it will send a 1 instead.

Sara has observed that every time she sends a message, there is bad weather exactly once during a contiguous period of time. This means that if she tries to send a particular message, the message that the recipient receives will be incorrect in such a way that, in a specific interval (which can be of size 1 or more, but not zero), all zeros become ones and all ones become zeros. We call this the interval being corrupted.

For example: if Sara sends 11101001, it is possible that the weather causes the following corruption: 11101001 ⇒ 11010111.

Let the message Sara wants to send be denoted by S and the message Mio receives be denoted by M. Thus, S is never equal to M due to the bad weather. Sara and Mio now want to develop a system to communicate with each other despite the bad weather. It can be shown that if Sara sends exactly S, it will be impossible for Mio to use M to find S. But maybe it will work if Sara sends a message that is slightly longer than S?

Your task is to develop the system for Sara and Mio so that they can communicate flawlessly. You do this by implementing two functions, encode and decode. The function encode will be called with S, and it should then return E. Sara will then send E through her machine.

Afterward, Mio receives the string M and calls the function decode with M, and its job is to use M to find S.

To score points on this task, the system must work. Therefore, decode must always be able to find S, regardless of how bad weather corrupts E. You will get more points if E is short.

Implementation

Your solution to the problem must be written in one of the following languages: C++, Java, Python, or Rust. Below is a description of what the implementation looks like in C++. In most other languages, it works similarly. You can download a reference implementation for your language in the attachments at the bottom of the page.

You must not create a main function. Instead, you should implement the following functions:

• string encode(string S)

  • The parameter S is the message Sara wants to send to Mio. S consists only of the characters 0 and 1. In all test cases, S consists of exactly 100 characters.
  • The return value should be E, the message Sara sends through the machine. E must contain at least one characters and may only consist of the characters 0 and 1.

• After sending E, an interval will be corrupted during transmission.

• string decode(string M)

  • The parameter M is the message Mio receives. This will be E after an interval has been corrupted. Therefore, M consists only of the characters 0 and 1.
  • The return value should be S, the message that encode was originally called with. If the return value is the same as S, you get the correct answer for the test case.

encode and decode can only communicate through the parameters they are called with, S and M. Therefore, your program will be restarted between calls to each function. encode and decode must be fast enough to be called 50 times each within the time limit. The judge is also non-adaptive. This means that how it selects S does not depend on what you choose to send as E. When choosing which interval to corrupt, it will only look at the number of characters in E, not the contents of E.

Reference Implementations

All reference implementations in the attachments implement the following protocol: encode sends each letter in S 5 times in a row. decode then takes each group of 5 characters and says that the value of the letter in S is the one in the middle of the group. This protocol does not work, but it shows what the implementation of a protocol might look like.

It is important that your solution does not read or write from standard input/output. If your solution does this, you will likely get a strange error message. For some languages, the filename is important, so do not change it. Also, do not change the names of functions and classes if they exist. Rust requires extra steps to work, which you can read about in the file rust/readme.txt in karleksbrev.zip.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Let E_max denote the length of the E with the most characters that encode produces in a particular test case group. To score points for a test case, E_max must be small enough.

It is also given that S always consists of exactly 100 characters.

GroupPointsConstraints
17E_max ≤ 510
211E_max ≤ 410
321E_max ≤ 310
40E_max ≤ 310, l and r are even.
50E_max ≤ 310, l is even.
65E_max ≤ 250, l=r
725E_max ≤ 250
813E_max ≤ 210
918E_max ≤ 150

Input Format for the Example Judge

The example judge reads input in the following format:

  • A line with the integers N and K.
  • A line with the bit string S.
  • A line with the integers l and r. This is the interval in E that the judge will corrupt.

Example Interaction

Consider the following input to the judge:

5 25
01011
1 3

When the example program is run, the following happens. Note that the example program does not solve the problem in this case.

EventResult
encode(01011) is calledencode returns 0000011111000001111111111
The judge corrupts the return value of encode(01011)The corrupted message becomes 0111011111000001111111111
decode(0111011111000001111111111) is calleddecode returns 11011
The judge compares 01011 and the return value of decodeSince they differ, the solution gets “Wrong Answer”

출처 표기

출처: Programmeringsolympiaden 2025년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.