Back to School '18

It's that time of the (school) year again, and to celebrate, we present the Back to School '18 contest! Get back into your tip top programming shape and start the school year with a new rating!

The problem writers of this contest are Ninjaclasher, richardyi25, Beautiful_Times, and insignificant.

Back to School '18 will consist of 8 problems, with difficulty ranging between CCC Junior to IOI level. The contest questions have a wide range of difficulty, 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.

Contestants can participate in any 4 hour window between Friday, September 7, 3PM EDT to Sunday, September 9, 11:59PM EDT. Once you enter the contest, you will be able to submit until 4 hours from when you started, or until the hard deadline (September 9, 11:59:59PM EDT), whichever comes first.

Of course, it is forbidden to use multiple accounts to participate, and it is also forbidden to discuss the problems and/or their solutions with other people during the entire contest period.

Due to the large contest time window, we will be using a pretest/systest format in order to prevent cheating. On problems 5-8, when you submit, you will receive your result on some of the test data, called preliminary tests (pretests). After the contest, we will rejudge all solutions on the complete set of test data, and that will determine your final score. Note that getting AC on pretests does not ensure that you will pass system testing.

The pretests may be weak, so be sure to check the correctness and complexity of your solutions! You might also want to constant optimize to prevent TLEing by a small margin. In particular, non-AC submissions on the pretests will likely result in a score of 0 on the systests.

This contest will be rated for contestants with at least one submission.

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

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.
  • 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. It is guaranteed that all the problems will be solvable with C++ and Java.
  • Read carefully, and try to attempt all the problems. They may not be as hard as they seem and you may get partial points!

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

Problems

Problem Points AC Rate Users Editorials
Back To School '18: Harambe 3 23.1% 400
Back To School '18: Letter Frequency 7p 19.1% 580
Back To School '18: Making Friends 7p 18.3% 146
Back To School '18: Beautiful Trees 10p 15.0% 106 Editorial
Back To School '18: An FFT Problem 10p 26.2% 114 Editorial
Back To School '18: The Golden Porcupine 15p 33.0% 214 Editorial
Back To School '18: Trucking Troubles II 20p 29.9% 32
Back To School '18: Function Maximization 25p 13.8% 33 Editorial

Comments


  • -5
    BaturaDima  commented on Sept. 10, 2018, 5:37 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -2
      kingW3  commented on Sept. 10, 2018, 8:35 p.m. ← edit 2

      I assume that \log(N) queries are needed, perhaps by using some sort of Fenwick tree (or perhaps not I'm a newb)


      • 8
        bqi343  commented on Sept. 10, 2018, 10:04 p.m. ← edit 2

        You can use segment tree and lazy propagation with bitset to do updates and queries in O\left(\frac{5000\log N}{\text{bitset constant}}\right).


        • -2
          BaturaDima  commented on Sept. 12, 2018, 3:03 p.m.

          As I've understood we split original array into 5000 subsequnces, and doing queries independently. And for this new subsequnces we must use bitsets for speeding-up. How we can do it?


        • 3
          Beautiful_Times  commented on Sept. 11, 2018, 1:38 a.m.

          You also need either a segmented sieve or miller rabin to determine the large primes.


          • -2
            BaturaDima  commented on Sept. 12, 2018, 10:46 a.m. ← edited

            Doesn't segmented sieve have not \mathcal{O}(N) time, and only less memory ? Maybe you mean another segmented sieve ?


            • 2
              Beautiful_Times  commented on Sept. 12, 2018, 3:24 p.m.

              It's the same technique used in this question to generate the valid primes

              https://dmoj.ca/problem/phantom3


              • -2
                BaturaDima  commented on Sept. 12, 2018, 4:37 p.m.

                I've understood at last that we can apply only for necessary interval :) It is a pity that there are no editorials at DMOJ, and even solutions of another participants closed for watching.