c4cheats's blog

By c4cheats, history, 9 years ago, In English

I wanted to contribute to the community with my solutions and my thought process on each problem. During the contest, I only solved two problems, however, this was in the middle of doing life (putting a toddler down for a nap, getting lunch, and taking care of phone calls). That is normally how I do the three contests that I have done.

Being a high school computer science teacher, I have a class that competed in this competition as an assignment. We just started the year, so most of them answered problem A. To help them, I wrote out my thought process in solving A and C. I think I have solved B in my head, and I just need to write it out. I will edit this post when that is done.

I have posted them on my team page, and I am going to link to them. If this is against any rules, please let me know. I will copy my write-ups here. Hopefully, they will help someone learn something new.

I would like to warn you that I did post my code on the site as well. So if you do not want to see code, you may not want to click the links, or you can try to ignore them.

Write Ups

  • Vote: I like it
  • +40
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very interesting. You teach APCS, I'm guessing?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I do.

    I have over 100 students taking Programming 1, about 20 taking Programming 2 or 3, 72 APCS students and 15 taking a programming competition course.

    I know that was more than you probably wanted to know. Have a great day!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solving A is really good! This is a great AP CS class! On today's contest, it took me three attempts to solve A. Maybe you can translate them into Java and explain my solution to them?

12746212 (WA pretest 4) (strict equality is needed) 12746358 (WA pretest 5) (you have to take away from the maximum always) submission:12748500 (This is a correct solution, following your explanation)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Thank you. My AP CS students will get to this sort of stuff towards the end of the year. Most of my APCS students just wrote their first program this week. I am not a Hello World fan, so they started with Applets last Monday. I have a specialized competition course. We use these competitions as training for the local high school competitions that offer scholarships and prizes.

    They will most likely see your solutions too.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by c4cheats (previous revision, new revision, compare).

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

As far as I see, you are sorting votes every time when you decrease current 'leader'. But let's say that constraints are bigger, and doing O(nlogn) every time when you decrease something will be too much. So, you can implement priority queue. It will do O(2logn) which is actually O(logn) operations per decreasing. And for storing starting state you need O(nlogn) operations, of course. It saves time.

12765146

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are right. I didn't think about using a priority queue during the contest. All I was thinking was I needed a way to find the largest value quickly.

    Thank you posting your solution. I will spend a time and rewrite mine for my students as a better solution.