"Это мы опубликуем, это никому не стыдно опубликовать..."

[singalen]

Открыл для себя TopCoder.

Заодно публицну-ка я тестовые задачи и свои решения. Для желающих :)
Тестовая задача раз
Тестовая задача два

Всё пишу на Джаве - так проще и надежнее. Цвета кошмарненькие, попожжее научусь пользоваться этой аццкой утилитой.
Моё решение раз:

public class HowEasy
{
  public static final int LESSER_COST = 250;
  public static final int MIDDLE_COST = 500;
  public static final int HIGHER_COST = 1000;

  public int pointVal(String problemStatement)
  {
    int averageWordLength = calcAverageLength(problemStatement);

    if (averageWordLength <= 3) return LESSER_COST;
    if (averageWordLength <= 5) return MIDDLE_COST;
    return HIGHER_COST;
  }

  private static final String WORD_REGEX = "[a-zA-Z]+\\.?";
  private static final String PERIOD_STRING = ".";

  static int calcAverageLength(String problemStatement) {
    String tokens[] = problemStatement.split(" +");
    int wordCount = 0;
    int wordsTotalLength = 0;

    for (int i=0; i<tokens.length; i++)
    {
      if (tokens[i].matches(WORD_REGEX))
      {
        wordCount++;
        wordsTotalLength += tokens[i].length();
      }
      if (tokens[i].endsWith(PERIOD_STRING)) 
      {
        // the last word was one letter shorter
        wordsTotalLength--;
      }
    }

    int averageWordLength = 0;
    if (wordCount > 0)
    {
      averageWordLength = wordsTotalLength / wordCount;
    }
    
    return averageWordLength;
  }
}

import junit.framework.TestCase;

public class TestHowEasy extends TestCase {

  /*
   * Test method for 'HowEasy.pointVal(String)'
   */
  public void testPointVal() throws InstantiationException, IllegalAccessException, ClassNotFoundException
  {
    testPointVal("ab ab.", 2, 250);
    testPointVal("abcd abcd.", 4, 500);
    testPointVal("abcde abcde.", 5, 500);
    testPointVal("abcdef abcdef.", 6, 1000);
    testPointVal("abcde abcdefg.", 6, 1000);
    testPointVal("a abcdefgbcde", 6, 1000);
    testPointVal("a abcdefgbcde as", 4, 500);
    testPointVal("a. abcdefgbcde", 6, 1000);

    //does it count speces right?
    testPointVal("ab  AB     ", 2, 250);

    testPointVal("ab.. a.b .ab a.b. a2b. .", 0, 250);

    testPointVal("This is a problem statement", 4, 500);
    
    testPointVal("532hi.", 0, 250);
    
    testPointVal("Implement a class H5 which contains some method.", 5, 500);
    
    testPointVal(" no9 . wor7ds he8re. hj..", 0, 250);
  }
  
  private void testPointVal(
    String problem, int expectedLength, int expectedValue) throws InstantiationException, IllegalAccessException, ClassNotFoundException
  {
    int avgLength = HowEasy.calcAverageLength(problem);
    assertEquals(expectedLength, avgLength);
    HowEasy a = (HowEasy) Class.forName("HowEasy").newInstance();
    int pointVal = new HowEasy().pointVal(problem);
    assertEquals(expectedValue, pointVal);
  }
}

Моё решение два:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public final class Prerequisites
{
  public String[] orderClasses(String[] classes)
  {
    try
    {
      initCourses(classes);
    }
    catch (BadCourseName e)
    {
      return new String[0];
    }   

    circutDependencies();

    if (coursesSelfDepend()) return new String[0];

    List sortedCourses = new ArrayList(courses.values());
    Collections.sort(sortedCourses);

    try
    {
      return getCoursesNames(sortedCourses);
    }
    catch (Exception e)
    {
      return new String[0];
    }
  }

  private String[] getCoursesNames(List sortedCourses) throws Exception
  {
    ArrayList names = new ArrayList();
    //for (int i = 0; i < sortedCourses.length; i++)
    for (Iterator i = sortedCourses.iterator(); i.hasNext();)
    {
      Course c = (Course) i.next();
      if (!c.needed) continue;
      if (!c.exists) throw new Exception();
      names.add(c.name);
    }

    String[] result = new String[names.size()];
    int i = 0;
    for (Iterator iter = names.iterator(); iter.hasNext();) {
      String name = (String) iter.next();
      result[i] = name;
      i++;
    }

    return result;
  }

  private class BadCourseName extends Exception
  {
  }

  private class Course implements Comparable
  {
    public Course(String name) throws BadCourseName
    {
      this.name = name;
      if (!name.matches("[A-Z]{3,4}[1-9][0-9][0-9]"))
        throw new BadCourseName();
      code = name.substring(0, name.length()-3);
      number = name.substring(code.length());
    }

    public String name;
    public String code;
    public String number;
    public boolean needed = false;
    public boolean exists = false;
    //public Course pre[] = new Course[0];
    public Map pre = new HashMap();
    
    public boolean directlyDepends(String nameOnto)
    {
      return pre.get(nameOnto) != null;
    }
    
    public void addDependant(Course c)
    {
      pre.put(c.name, c);
      if (needed) c.needed = true;
    }

    public int compareTo(Object obj)
    {
      if (!(obj instanceof Course)) return 1;
      Course c = (Course) obj;
      if (directlyDepends(c.name)) return 1;
      if (c.directlyDepends(name)) return -1;
      int numbersCompare = number.compareTo(c.number);
      if (numbersCompare != 0) return numbersCompare;
      return code.compareTo(c.code);
    }
  }

  private Map courses = new HashMap();

  private Course getCourse(String name) throws BadCourseName
  {
    Object course = courses.get(name);
    if (course != null) return (Course) course;

    Course newCourse = new Course(name);
    courses.put(name, newCourse);
    return newCourse;
  }

  private void initCourses(String[] classes) throws BadCourseName
  {
    for (int i = 0; i < classes.length; i++)
    {
      String[] s = classes[i].split(":", 2);
      String courseName = s[0];
      Course course = getCourse(courseName);
      course.needed = true;
      course.exists = true;

      if (s.length < 2) throw new BadCourseName();

      String[] courseDependencies = s[1].split(" ");
      // start with 1 to skip leading space after :
      for (int j = 1; j < courseDependencies.length; j++)
      {
        Course dependancy = getCourse(courseDependencies[j]);
        course.addDependant(dependancy);
      }
    }
  }
  
  /** Classic transitive circut on courses */
  private void circutDependencies()
  {
    for (Iterator i = courses.values().iterator(); i.hasNext(); )
    {
      Course c1 = (Course) i.next();
      for (Iterator j = courses.values().iterator(); j.hasNext(); )
      {
        Course c2 = (Course) j.next();
        for (Iterator k = courses.values().iterator(); k.hasNext(); )
        {
          Course c3 = (Course) k.next();
          if (c1.directlyDepends(c2.name) && c2.directlyDepends(c3.name))
          {
            c1.addDependant(c3);
          }
        }
      }
    }
  }
  
  private boolean coursesSelfDepend()
  {
    for (Iterator i = courses.values().iterator(); i.hasNext(); )
    {
      Course c = (Course) i.next();
      if (c.directlyDepends(c.name)) return true;
    }
    return false;
  }
}

import junit.framework.TestCase;

public class PrerequisitesTest extends TestCase {
  
  Prerequisites pre;

  protected void setUp() throws Exception {
    super.setUp();
    pre = new Prerequisites();
  }

  protected void tearDown() throws Exception {
    pre = null;
    super.tearDown();
  }

  public void testOrderClasses1()
  {
    String[] courses = { "CSE111: CSE110 MATH101", "CSE110:", "MATH101:" };
    String[] expected = { "MATH101", "CSE110", "CSE111" };
    String[] schedule = pre.orderClasses(courses);
    assertEquals(expected.length, schedule.length);
    assertEquals(expected[0], schedule[0]);
    assertEquals(expected[1], schedule[1]);
    assertEquals(expected[2], schedule[2]);
  }
    
  public void testOrderClasses2()
  {
    String[] c2 = { "CSE121: CSE110", "CSE110:", "MATH122:" };
    String[] e2 = { "CSE110", "CSE121", "MATH122" };
    String[] courses = c2;
    String[] expected = e2;
    String[] schedule = pre.orderClasses(courses);
    assertEquals(expected.length, schedule.length);
    assertEquals(expected[0], schedule[0]);
    assertEquals(expected[1], schedule[1]);
    assertEquals(expected[2], schedule[2]);
    
  }
  
  public void testOrderClasses3()
  {
    String[] c3 = {"ENGL111: ENGL110", "ENGL110: ENGL111" };
    String[] schedule = pre.orderClasses(c3);
    assertEquals(0, schedule.length);

  }
  
  public void testOrderClasses4()
  {
    String[] c4 = {"ENGL111: ENGL110" };
    String[] schedule = pre.orderClasses(c4);
    assertEquals(0, schedule.length);
  }
  
  public void testOrderClasses5()
  {
    String[] c5 = {
        "CSE258: CSE244 CSE243 INTR100",
        "CSE221: CSE254 INTR100",
        "CSE254: CSE111 MATH210 INTR100",
        "CSE244: CSE243 MATH210 INTR100",
        "MATH210: INTR100",
        "CSE101: INTR100",
        "CSE111: INTR100",
        "ECE201: CSE111 INTR100",
        "ECE111: INTR100",
        "CSE243: CSE254",
        "INTR100:"
        };
    String[] e5 = {"INTR100","CSE101","CSE111","ECE111","ECE201","MATH210",
        "CSE254","CSE221","CSE243","CSE244","CSE258"};
    String[] schedule = pre.orderClasses(c5);
    assertEquals(e5.length, schedule.length);
    assertEquals(e5[0], schedule[0]);

    assertEquals(e5[1], schedule[1]);
    assertEquals(e5[2], schedule[2]);
    assertEquals(e5[3], schedule[3]);
    assertEquals(e5[4], schedule[4]);
    assertEquals(e5[5], schedule[5]);
    assertEquals(e5[6], schedule[6]);
    assertEquals(e5[7], schedule[7]);
    assertEquals(e5[8], schedule[8]);
    assertEquals(e5[9], schedule[9]);
    assertEquals(e5[10], schedule[10]);
    //assertEquals(e5[11], schedule[11]);
  }
}

Comments

[dottedmag.livejournal.com]

В следующем контесте участвуешь?

[singalen]

Завтра в пять утра? Не уверен... попробую :)
18-го постараюсь.

[dottedmag.livejournal.com]

У меня - в восемь. Как раз на работу приеду =)

[rioman.livejournal.com]

Ты ручками расставляешь цвета или скрипт есть?

[singalen]

GNU source-highlight. Их таких дохренища, эта первая попавшаяся под винды.

[singalen]

Кстати, ошибочка в initCourses(). Нужно проверять, что первый courseDependencies — пустая строка, т.е. что после двоеточия шёл пробел.

[http://users.livejournal.com/_radiant_/]

Java?
Будет интересно посмотреть на решения профессионала.

А не собираетесь пользоваться плагинами?
Боюсь, на контесте не хватит времени _так_ выписывать ручками тесты :)

[singalen]

Пасип :) Не такой уж я джавовский проффесионал.
Контест - три часа? Это всё написано за три часа, считая минут 40 колупания из-за собственной бестолковости и незнания морды клиента.
Кстати, кто скажет, откуда скачать джавовый клиент? Не нашел линка ни на бинарь, ни на вебстарт.

[http://users.livejournal.com/_radiant_/]

Контест (кодинг-фаза) на час 15 минут :)

Ну, бинаря вроде нет, а ссылку на веб-старт можно посмотреть в FAQ:
http://www.topcoder.com/tc?module=Static&d1=help&d2=getStarted#howtorun

[singalen]

Да? Вот чёрт. Это на одну задачу, максимум две. Спасибо, что предупредили ;) Пошел перечитывать условия.
Мда, инерция мышления. Если не ссылка - то уже не замечаю...

[singalen]

Но вообще, тестовые классы сгенерены эклипсой, а тестовые данные переклеены из текста задания. Очень, очень экономит время. Рекомендую.

[alf-kadett.livejournal.com]

учитывая, что плагин тесты клепает сам - любая ручная работа будет медленней

[upstartn.livejournal.com]

Рекомендую пользоваться методом java.util.Arrays.equals(Object[],Object[]);
Он улучшает карму :)

[singalen]

Я же говорил, что не знаю джавы :)

[singalen]

Я решил, что здоровый детский сон важнее.
Как твои успехи?

[singalen]

Да? Хм, надо ставить... бо у меня этого плагина не было.

[singalen]

Но тогда дело становится тупым, потому что тесты охватывают почти весь диапазон возможных ошибок.

[dottedmag.livejournal.com]

0 :( Первый дивизион, плюс две задачи с floating-point, плюс задача на симуляцию.

[alf-kadett.livejournal.com]

Напоминаю:
1. У тебя 75 минут на 3 задачи.
2. В первом дивизионе частенько бывают задачи, которые я и за пару часов не решу.
3. Мысль о том, что примеры покрывают все - или хотя бы "почти все" граничные случаи - несколько наивна :)

[singalen]

Мда... видимо, это было так только в тренировочной комнате №1 :)
Сейчас поищу условия вашего первого дивизиона :)
А скажите вот что - сколько задач вы обычно успеваете решить, каких, и на сколько баллов? Хочу выработать тактику - брать одну на 1000, 250 и 500, или 1000 и 250?

[alf-kadett.livejournal.com]

Я пока во втором :) И "обычно" - это тоже не ко мне: я участвовал ровно в одном SRM-е (265), и во втором дивизионе.

Решил задачи на 250 и 500 (230 и 249 очков с учётом вычетов по времени), тысячную даже не пытался - оставалось меньше 10 минут, а (мне) там минут на 30 аккуратной работы.

Хитрость ещё и в том, что если ты возьмёшь 1000, и просидишь над ней час, то получишь очков 300. А быстро решённые задачи на 500 и 250 дадут лучший результат =)

А так - смотри статистику.