Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden on 2014-07-09 00:31:49 by Mitch Schwartz

DCODE - The Modern Dress Code

no tags 

Byteland is making preparations for the approaching period of feasts, cabaret shows, and general merrymaking. The women in Byteland are especially excited about the Grand Ball to be held on the last Saturday of the holiday period, and have already started making preparations. At present, one of the most important questions for every lady seems to be: What should I wear for the ball?. This problem is far more important than you might imagine possible, since the months after the period of feasts will offer no celebrations whatsoever, and during this time every lady likes to think back to how charming and original she looked at the ball. And of course, you have to remember that if two female friends come to the party dressed in the same dresses they will both be the subject of jokes and chuckled remarks for years.

 

As in most difficult problems among ladies, the gentlemen of Byteland are forcibly involved and asked to help out. So, every day each woman asks her man for advice on what to wear. Unfortunately very few men in Byteland know anything at all about fashion so they all come to you and ask for help.

You do not have a lot of to do with Bytelandian fashion either but, as a computer specialist and a generally clever person who never gives up, you know how to address any problem. You have modeled the situation as follows:

  • there are 1<=k<=20 days left till the grand feast,
  • dresses in Byteland come in different colors, which you have numbered with integers starting from 0,
  • the relationships between Bytelandian women are given by a graph (adjacent nodes denote two friends),
  • every lady would like to have a dress of different color than all her friends, otherwise she will be most unhappy.

You have a plan to provide the men with a simple set of rules to help them determine the best, most unique color of clothes for their ladies. Since you only have a limited amount of time to spare, each man will have to content himself with the same algorithm from you. Because most of the men don't use a computer, you should use a very simple language to express your algorithm.

Task

Prepare an algorithm which, if applied properly by all the men, will guarantee that as few of the ladies as possible are unhappy due to their dresses.

A short description of the language you should use is given below:

  • each program is a list of rules,
  • each < rule > is of the form:
    < rule >::= if < comp_condition > then { < comp_command > };
    
    < comp_command >::=< command >;
    < comp_command >::=< command >; < comp_command >
    
    < comp_condition >::=< condition >
    < comp_condition >::=not < comp_condition >
    < comp_condition >::=(< comp_condition > or < comp_condition >)
    < comp_condition >::=(< comp_condition > and < comp_condition >)
    Please note that after each < command > and < rule > you must put a semicolon.

  • < command > is simply an assignment of the form:
    < command >::= < symbol >:=< expr >
  • < symbol > can be one of the following strings:
    • a state component: color, a, b,
    • an additional local variable: l0, l1, l2, l3, l4, l5, l6, l7, l8, l9.
  • The expression < expr > should be constructed using:
    • writable symbols (as given above) and several special read-only variables which give you some information about the graph:
      deg       degree of current vertex
      delta     maximum vertex degree in a graph 
      n         number of vertices 
      m         number of edges
      nr        number of possible colors
      daysleft  number of days remaining till the ball
      
    • operators (in order of precedence):
      + -       arithmetic plus and minus
      * / %     arithmetic multiplication, division and remainder 
      
    • function rnd(< expr >), returning a random number between 0 and < expr > - 1 inclusive.
    • functions mina, minb, minc returning the minimal value of variable a, b, color respectively, taken over all the neighbours of the vertex (or the smallest integer for a vertex without neighbours). Functions maxa, maxb, maxc act similarly for maximum values of variables.
  • < condition > is a logical expression taking one of two forms:
    < condition >::= < expr > < operator > < expr >
    < condition >::= < exist-operator > ( < expr > )
    
    The binary < operator > is one of the comparison operators ==, <, or >. The unary < exist-operator > is one of the following functions: Eaeq, Ebeq, Eceq, which return true iff for some neighbour of the given vertex the value of variable a, b, color, respectively, is equal to < expr >.

The algorithm has to be applied by every man every day. More formally speaking: at the start of the process all variables have random values. Every morning all the men assign 0 to their variables l0,l1,...,l9. Exactly at noon, each lady comes to ask for advice. The man does all he can to help her: he processes all his rules from top to bottom, and repeats the process as long as at least one of the IF clauses is true. (However, if he has to do it more than one hundred times, he will give up in dispair). Then he tells the lady the color he has chosen for her. Every evening, the men meet at the pub, and when they have nothing left to talk about, they exchange information about how the women are boring them, and what values of a, b and color they have had to come up with today. (It is interesting to note that, as a side effect, functions E_eq, min_ and max_ actually make use of the previous day's values of the neighbours' variables.)

Finally, on the day of the ball the women put on clothing corresponding to the color last suggested by their men and it is time to judge how effective your algorithm has been. (This is one of these tasks which, if done badly, may result in getting the programmer lynched by an angry mob.)

Score

There are 50 test cases on which your program will be tested. Graphs used in tests will have no more than 25 vertices. Your score is the sum of scores of your program taken over all test cases. For each test case the score is equal to the ratio of the number of correctly colored vertices (i.e. such that 0<= color< nr and Eceq(color) is false) to the total number of vertices. If all vertices are correctly colored, a bonus of 1/(1+ maximum color used) points is awarded.

A program will be assessed as Compilation Error if it cannot be interpreted due to syntactic errors. If on a given day the rules for a vertex cannot be processed within 100 iterations or the entire simulation takes more than about 60s, your program will be judged as Time Limit Exceeded.

Example

Submit code in the language TEXT, the judge will interpret it properly. Here is an example of a simple single-rule program.

Code:
if (l0==0 and not Eceq ((color-1)%n)) then {color:=(color-1)%n; l0:=1;};

Score:
5.491

hide comments
Flago: 2014-07-14 10:29:57

I don't think I have the knowledge needed about SPOJ system or judge to investigate the issue here, might take a look back to it some day in the future if its still unresolved by the admins.
Anyway, I thank you taking time explaining the situation.

Mitch Schwartz: 2014-07-11 15:34:44

@Flago: Well, ideally this one could be fixed (eventually), as there are many old submissions from inactive users. There's another problem, TIP3, with judge that used to work but suddenly stopped working. That one is still visible. I don't know what is generally better. On the one hand, hiding is unfair to previous solvers, and on the other hand, making it visible is unfair to people who want to solve it for the first time or improve their old solutions. DELIVERY was in similar situation, and I hid that one. (I invited previous solvers to help check the judge for bugs -- nobody replied.) Another reason not to clone this problem is that the problem setter is an admin.

I haven't actually had time to look through the judge source and understand it; it would be nice to know why I got some internal errors even before the judge stopped working entirely. Possibly some changes could be made to the judge that wouldn't affect any existing AC scores, but could remove those old internal errors. It might be tricky because of (pseudo-)random numbers. Another potential issue is that this problem had the only working non-C/C++ judge that I knew of on SPOJ, before it broke. These considerations might be part of why there has been delay in fixing the problem. You are welcome to investigate these things too, and report any findings here; it might speed up the process. Or if you want to communicate privately about it, just let me know.

Flago: 2014-07-11 10:35:00

Ye, couldn't try it, but it seemed original one.
Maybe I could try create another problem equal to this one later ? Dunno if it is allowed tho.

Mitch Schwartz: 2014-07-09 00:31:24

@Flago: Unfortunately, I got no reply. There is nothing that EB can do to fix this. (We can only edit the problem text and the Resource field.)

It seems I am forced to hide it (for now). It's a pity.

Last edit: 2014-07-09 02:33:47
Flago: 2014-07-08 12:54:38

@Mitch : Did you get some news from the admins ? Maybe we can help fix it, yet I'm not quite sure how the right on modifiying a problem works ?

Mitch Schwartz: 2014-06-26 16:45:23

@Flago: Second email sent to admins.

Flago: 2014-06-04 16:20:54

Not quite sure if I'm getting it wrong or if it is broken but even a simple :
"color:=0;"
Give me "Internal error", did I miss something or it is still broken like Mitch noticed ?

Mitch Schwartz: 2013-12-08 23:02:43

The link to the judge is broken. Is there a way to provide a working link? It could be useful, since for example I can't explain why my submissions 8757498 and 8757509 get different scores.

Additional: Many of my recent submissions are mysteriously getting internal error, and the difference between AC and internal error can be from something as simple as changing (x and y) to (y and x) or changing the value of an integer constant (in a seemingly harmless way).

Edit: Thanks to Piotr KÄ…kol for re-uploading the judge so that the link works again. At the moment you would need to change "spoj.pl" to "spoj.com" to get it to work.

Edit 2 (2014-03-15): The judge is giving internal error for my previously AC code; based on the submission history, it was probably broken for a while, but nobody left a comment about it so I wasn't aware. I will write to admins about it.

Last edit: 2014-05-15 16:49:02

Added by:kuszi
Date:2004-12-31
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:TEXT
Resource:DASM Programming League 2004, problemset 5