Page 1 of 1
10030 - Computer Dialogue
Posted: Mon May 13, 2002 8:41 pm
Could any one explain the flow of the sample IO (i.e. how to sample input produces the sample output)? Since I totally have no idea on what the word "communication" means in the problem.
Thx in advance.
Posted: Fri Jun 14, 2002 8:17 am
It's a very tough problem. The idea is, for every file on the server, imagine that it picks that filename, and sends the extension to one client and the name to the other. If the extension is unique to that file, then the "extension" client immediately knows which file was sent, and no query messages are exchanged. Otherwise, the "extension" client sends a message to the "name" client. Now, the "name" client considers ONLY those files which could have caused the "extension" client to send this query: in other words, it disregards all files with unique extensions. If, among the remaining files, the name that it received is unique, it knows which file was picked, and does not send a further query. Otherwise, it sends one. The "extension" client now has more information and thus a reduced set of possible files, and so on.
You want to determine which files take at LEAST m messages to be determined (since the clients can also arbitrarily stop sending queries). In the example data, LICENCE.TMP, LICENSE, FILEID., and FILEID.TMP will never be determined, no matter how many messages are sent. PSTOTXT3.DLL and PSTOTXT3.EXE are each determined after 2 messages. All other files take fewer than 2 messages to determine - in other words, if the server picks one of those files, it is impossible for 2 queries to be sent.
Posted: Sun Jun 16, 2002 8:06 pm
Thx. I got what's going on now~
What an interesting problem it is~