DMOPC '14 May Contest

Welcome to the eighth Don Mills Open Programming Competition of the school year!

The problem writers this time are Xyene, FatalEagle, and nullptr.

This round will be rated for all participants.

The theme for this month's contest is Cross Ange.


Before the contest date, you may wish to check out the tips and help pages.

The contest consists of 6 questions with a wide range of difficulties, and you can get partial marks for partial solutions in the form of subtasks. If you cannot solve a problem fully, we encourage you to go for these partial marks. The difficulty of a problem may be anywhere from CCC Junior to CCO level. You will have 3 hours to complete the contest. Check when the contest begins in your timezone here.

After joining the contest, you proceed to the Problems tab to begin. You can also go to Users if you wish to see the rankings.

We have listed below some advice as well as contest strategies:

  • Start from the beginning. Ties will be broken by the sum of times used to solve the problems starting from the beginning of the contest. The last submission time of your highest score will be used.
  • It is strongly advised to run your code on your own computer with the sample input we provide before submitting. It's faster to find and fix mistakes at this stage rather than submitting and waiting only to find out that your solution doesn't compile.
  • Remove all extra debugging code and/or input prompts from your code before submitting. The judge is very strict — most of the time, it requires your output to match exactly.
  • Do not pause program execution at the end. The judging process is automated. You should use stdin / stdout to perform input / output, respectively.
  • Just because your program works with the sample input doesn’t guarantee that it will earn full points. Read the problem statement very carefully to look for things you may have missed on the first read-through. It is not forbidden — in fact, even encouraged to make your own test cases to debug your program on.
  • The test data is guaranteed to fit within the constraints given. You do not have to perform any extra checks to make sure of this fact.
  • Do not just print out a hardcoded answer. There will be preliminary tests (pretests) to prevent such behavior. These pretests will generally be small enough to solve with almost any algorithm and will not contain any tricky corner cases. They are there to test for a basic understanding of a problem. The sample input will always be included as the first few pretests.
  • It is guaranteed that all the problems will be solvable with C++.

At the end of the contest, you may comment below to appeal a judging verdict. In the case of appeals, the decision(s) of DMOJ staff is final.

After the contest finishes, we'll have a optional feedback form we would like you to fill out.

Good luck!



Comments


  • 4
    bobhob314  commented on June 12, 2015, 6:02 p.m.

    Hello DMCI members,

    Is there going to be no DMOPC '15 June? I have grown to love these contests over the months and hope that they will be continued.

    Thanks!


  • 6
    belowthebelt  commented on May 6, 2015, 12:57 a.m.

    I managed to solve the first 4 out of the 6 problems completely. I liked the problems which I managed to solve. Though, I wasted a lot of time debugging the fourth one, and then had to go away for a while to submit a report so as to fail to not find time to pick up partial points in the 5th or the 6th problem. Anyway.

    1. Flare
    My solution is basically this:

      print input()*2.0/(9.8)

    Given the value v, we have to find the value t such that the value of y is equal to zero. So, we rearrange the equation, and thus, it changes to vt = 0.5*(gt<sup>2</sup>) - since g had a negative sign. After which, when the t is canceled, the equation reduces to 2v = gt, which further reduces to: t = 2v/g which is our answer.

    2. Tides
    This question was also simple, but had a lot of cases to deal with. I got 70/100 only initially, because I was not considering the case where the high tide ends up occurring before the low tide, which according to the problem statement (If you read carefully!) is also not a valid case.

    Depending on the language you choose to code this one in, it's just an implementation based problem. Checking if the sequence is an increasing one between low-tide and high-tide values is easy.

    n = int(raw_input())
    l = map(int, raw_input().split())
    mn, mx = min(l), max(l)
    mni, mxi = l.index(mn), l.index(mx)
    flag = True
    if mni>mxi:
        flag = False
    for i in xrange(mni,mxi):
        if l[i]>l[i+1]:
            flag = False
    if flag == True:
        print mx-mn
    else:
        print "unknown"

    3. Globally Unique Shells
    This problem like its name is actually ends up being a problem forcing you to think for a while, if you don't look at the constraints properly. For a while, I didn't realize that the value for the shells can range till 999999, I thought it was till N. So, I made a hash table till 60,000+1 for the value of N, which obviously resulted in a WA.

    Here's what I did:

    • I found the total number of the shells which were given to us.
    • I created a list with the union of the two halves, which thus reduced the total number of shells.
    • This number of shells reduced from the total which were given to us, if subtracted from n, gave me the number of shells which were incomplete.
    • Since the ones which are given to me are not completed anyway, and I just counted the number of ones which got completed.

    What are the other ways in which people solved this one?

    n = int(raw_input())
    ans = 0
    a, b = map(int, raw_input().split())
    c = a + b
    A = map(int, raw_input().split())
    B = map(int, raw_input().split())
    un = list(set(A) | set(B)) #Union of two lists.
    print n - ( c - len(un))

    4. Sand Triangle
    For a long while, my solution kept passing the smaller constraint case, while consistently failing on the larger one because of a silly mistake I was doing. (Counted the number of 9s in my code wrongly - shame on me!)

    I guess the general ideas, which I guess would have been used by people in this problem could be: pre-computation of certain values, then binary searching them, then finding out the required answer.

    • I calculated the starting point of all the levels of the triangle till 99999+1, because that'll be the last level to take care of 10<sup>9</sup>.
    • Then, using simple linear search, I found out the level a number was in.
    • We can already see that the number of elements in a level is the number of level itself.
    • Once I got the level a number is situated at, I had already pre-calculated all the sums for the levels till 10<sup>5</sup>, so I could just print the required value.

    Definitely the best problem I solved in this contest, required thinking, and making me use pen and paper.

    Here's my code:

    n = int(raw_input())
    l, x, y = [], 0, 99999+1
    
    for i in xrange(1,y):
        l.append(1 + i*(i-1)/2)
    
    for i in xrange(len(l)):
        if l[i]<=n:
            x = i + 1
        else:
            break
    ans = 0
    
    hashed = [0]*y
    hashed[1] = 1
    hashed[2] = 5
    for i in xrange(3,len(hashed)):
        hashed[i] = hashed[i-1] + i*(i-1) + 1 + (i*(i-1))/2
    
    print hashed[x]

    General Feedback:
    The contest in general was pretty good. The timings for me, in India were pretty odd, though. It started at 1 am and ended up at 4 am. I was sleepy by the end of it. Not that I mind. :) I would love to take part in more contests like this, and improve my level and skills. And I'm now expert: 1346. Which is the TopCoder equivalent of Division 1 in my first contest, which is... good, I suppose?

    Also, quick question to the admins: is there a way by which I could set up questions / test them / write editorials for the judge?

    Keep up the good work, guys!


    • 0
      FatalEagle  commented on May 6, 2015, 9:28 a.m.

      Yes, you can set problems and write editorials and put them on DM::Solutions. Give us a email at [email protected] for more details.


      • 0
        belowthebelt  commented on May 6, 2015, 11:35 a.m.

        Thanks, FatalEagle. I'll mail you guys. Thanks!


    • 0
      BMP  commented on May 6, 2015, 8:30 a.m.

      Interesting


  • 7
    nullptr  commented on May 5, 2015, 6:48 p.m.

    http://ideone.com/1vT6q7

    Editorial coming later


  • 5
    BMP  commented on May 5, 2015, 6:18 p.m.

    14'? Have we traveled back in time?


    • 3
      Sentient  commented on May 5, 2015, 6:33 p.m.

      DMOPC'14 represents the 2014-15 school year.


      • 1
        BMP  commented on May 5, 2015, 6:34 p.m. edited

        Oh, I see.


  • 0
    kobortor  commented on May 5, 2015, 3:29 p.m.

    TSS IS READY


  • 2
    pyrexshorts  commented on April 30, 2015, 11:35 p.m.

    Can this start at 4:30 or some time around that? Some schools end later, and it's hard to compete when there's one hour less for some contestants.


    • 1
      Xyene  commented on May 1, 2015, 6:15 p.m. edited

      This is the last contest of the school year. In the summer months, it is possible (and perhaps likely) that we'll run the DMOPC as a virtual contest.


    • 0
      bobhob314  commented on May 1, 2015, 11:34 a.m.

      This question is asked about once every DMOPC. Unfortunately, there are good reasons for the starting time and it will not be changed.