11224 - Let's swim!

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mario
New poster
Posts: 5
Joined: Sat Jul 07, 2007 4:46 pm

Post by mario » Mon Jul 23, 2007 4:17 am

It turned out that there was a hole in my algorithm. Actually two of them :D
Last input that TimeString posted helped me find one. The other hole was at the time to find what medal would get Gustavo in the finals. Well thanks for the help you guys.

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11224 - Let's Swim!

Post by sith » Tue Jul 03, 2012 2:56 pm

Hello
I'we got WA :(

My solution works properly for all cases from this thread. But I am getting WA :(

Code: Select all

import java.io.*;
import java.util.*;

class Main {

     public static void main(String[] args) {

         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

         BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
         Scanner scanner = new Scanner(reader);

         try {

             int cases = scanner.nextInt();
             for (int i = 1; i <= cases; i++) {
                 int competitors = scanner.nextInt();
                 int rank = scanner.nextInt();
                 Set<Competitor> competitorSet = new TreeSet<Competitor>();
                 List<Competitor> competitorList = new ArrayList<Competitor>();

                 Integer[] timesArray = new Integer[competitors-1];

                 IntegerComparator comparator = new IntegerComparator();
                 PriorityQueue<Integer> times = new PriorityQueue<Integer>(competitors, comparator);


                 for (int j = 0; j < competitors - 1; j++) {
                     Competitor e = new Competitor(scanner.nextInt(), scanner.nextLine());

                     timesArray[j] = e.time;
                     competitorList.add(e);


                 }



                 int timeSize = timesArray.length;
                 if (timeSize>7) {
                     timeSize = 7;
                 }

                 Arrays.sort(timesArray,comparator);
                 times.addAll(Arrays.asList(timesArray).subList(0, timeSize));
                 Collections.sort(competitorList);
                 competitorList.subList(0, timeSize);

                 if (rank==1) {

                     if (competitorList.get(timeSize -1).time -competitorList.get(timeSize -2).time==1) {
                         times.add(competitorList.get(timeSize - 1).time + 1);
                     }

                 }

                 competitorSet.addAll(competitorList);


                 Result result = new Result();
                 while (times.size() > 0) {

                     Integer gustavoTime = times.poll();
                     Competitor gustavo = new Competitor(rank, gustavoTime);
                     competitorSet.add(gustavo);
                     Result tmp = checkTime(competitorSet, gustavo, rank);


                     result = getNewResult(result, tmp);

                     if (result.semifinalResult<=8&&result.finalResult <= 3 && rank > 3) {
                         break;
                     }

                     Integer nextTime = times.peek();
                     if (nextTime == null) {
                         continue;
                     }
                     if (gustavoTime - nextTime > 1) {
                         gustavo.time--;
                         competitorSet.remove(gustavo);
                         competitorSet.add(gustavo);

                         tmp = checkTime(competitorSet, gustavo, rank);

                         result = getNewResult(result, tmp);


                         if (result.semifinalResult<=8&&result.finalResult <= 3 && rank > 3) {
                             break;
                         }

                         competitorSet.remove(gustavo);
                     }


                 }

                 writer.write("Case #" + i + ":\n");
                 writer.write("Gustavo should be #" + result.semifinalResult + " during the qualification to achieve position #" + result.finalResult + " in the final.\n");


             }

             writer.flush();
         } catch (IOException e) {
             e.printStackTrace();
         }


     }

    private static Result getNewResult(Result result, Result tmp) {

        if (tmp.finalResult<result.finalResult) {

            result = tmp;

        }
        return result;
    }

    private static Result checkTime(Set<Competitor> competitorSet, Competitor gustavo, int rank) {
        Result tmp=new Result(0,0);

        int lastMedalRank=0;
        for (Competitor competitor : competitorSet) {

            if (competitor.equals(gustavo)) {
                if (tmp.finalResult < 3 && competitor.rank <= 3) {

                    switch (tmp.finalResult) {
                        case 0:
                            tmp.finalResult = 1;
                            break;
                        case 2:
                            tmp.finalResult = gustavo.rank;
                            break;
                        default:
                            tmp.finalResult = gustavo.rank < lastMedalRank ? 1 : 2;

                    }


                } else {
                    tmp.finalResult++;

                }

                tmp.semifinalResult++;

                break;
            }


            if (competitor.rank < rank) {
                lastMedalRank = competitor.rank;
                tmp.finalResult++;
            }
            tmp.semifinalResult++;

        }
        return tmp;
    }


    static class Competitor implements Comparable<Competitor>{
        int rank, time;

        Competitor(int rank, String time) {
            this.rank = rank;
            StringTokenizer tokenizer = new StringTokenizer(time,": ");
            this.time = Integer.parseInt(tokenizer.nextToken())*60*100+Integer.parseInt(tokenizer.nextToken())*100+Integer.parseInt(tokenizer.nextToken());
        }

        public Competitor(int rank, Integer time) {
            this.rank = rank;
            this.time = time;
        }

        @Override
        public int compareTo(Competitor o) {
            int compare = time - o.time;
            if (compare==0) {
                return rank - o.rank;
            }
            return compare;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Competitor that = (Competitor) o;

            if (rank != that.rank) return false;

            return true;
        }

        @Override
        public int hashCode() {
            return rank;
        }

        @Override
        public String toString() {
            return "Competitor{" +
                    "rank=" + rank +
                    ", time=" + time +
                    '}';
        }
    }
    static class Result   {
        int semifinalResult = Integer.MIN_VALUE;
        int finalResult= Integer.MAX_VALUE;

        Result() {
        }

        Result(int semifinalResult, int finalResult) {
            this.semifinalResult = semifinalResult;
            this.finalResult = finalResult;
        }

        @Override
        public String toString() {
            return "Result{" +
                    "semifinalResult=" + semifinalResult +
                    ", finalResult=" + finalResult +
                    '}';
        }
    }
    private static class IntegerComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11224 - Let's Swim!

Post by brianfry713 » Fri Jul 06, 2012 1:55 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 112 (11200-11299)”