Glenforest Winter Open 2015 (Senior)

enter image description here


Beep... Boop.... Beep...

Butane has turned himself into a robot! Unfortunately, he is very badly programmed (by himself), so none of his intended functions work properly. Can you help debug ButaneBot?

Warning: The Senior contest is recommended for those who have knowledge of algorithms and data structures. Good luck :-).


The problem writers for this contest will be Awaykened and Butane


The contest consists of 5 questions with a 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 the problems will range from CCC Senior level to CCO level.

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.

Good luck!


Problems

Problem Points AC Rate Users
OR-deal 5p 28.4% 123
Soko-Boop 12p 21.4% 50
PalinDrone 12p 17.9% 105
Starry Nights 17p 18.1% 40
ORBOT 15p 18.2% 19

Comments


  • 0
    XIAOAGE  commented on Dec. 15, 2015, 7:26 a.m. edited

    When can i find the editorial? I m looking forward to reading it!!!!


    • 2
      awaykened  commented on Dec. 15, 2015, 7:34 a.m. edit 3

      Sorry, problem setters are a bit busy for the time being. Editorials will likely be released sometime Thursday :)

      Edit: here are some simple solution sketches for senior from our Facebook group:

      s1 - the answer only has '1's. how many '1's? go find out!

      s2 - BFS, state is (r, c) of player, (r, c) of box

      s3 - the answer does not change when N goes beyond a certain point due to mod 1e9, so simply calculating answers up to that N is all that is necessary.

      s4 - bitmask dp, realize that there are only 2745 "good" states that you can precompute, so your complexity is R2745^2 instead of R(2^C)^2

      s5 - if all array elements are positive, output the or sum of all elements in the array. if all array elements are negative, output the or sum of all elements in the array. otherwise, you want to take the maximum of the OR-sum of any contiguous POSITIVE subsequence of the the array. you can handle the last case using sets or smart implementation of segment trees.


      • 0
        XIAOAGE  commented on Dec. 15, 2015, 7:40 a.m.

        Thank u very much!!!!!!