I_love_natalia's blog

Samara Interacademic Programming Contest Gym
By I_love_natalia, 12 years ago, translation, In English

On March 18 Samara Interacademic Programming Contest was held. It is one of two Collegiate Programming contests, which are organized in Samara every year.

Everyone can take part in this contest as a Codeforces Gym contest. Like any train, this contest uses ACM ICPC rules.

Problem writers are Alexey Dergunov(dalex), Nikita Glashenko (Hohol), Pavel Semushin (craus) and Andrey Gaidel (Shlakoblock). Testers are Natalia Bondarenko (natalia) and me (I_love_natalia).

Contest will be most interesting for participants with color from green to orange (Difficulty is 3 stars). Red participant most probably will spend much less time than 5 hours for solving all problems (both of testers finished it in about 3 hours).

Train will be held on Saturday at 16:00 MSK. Everyone is welcome to participate.

Please, do not use any prewritten code and any internet materials in token of respect to ghost participants who will compete with you ;)

Upd. Time was changed to 16:00 (MSK, UTC+4).

Upd2. Don't forget to use input.txt and output.txt files instead of stdin/stdout.

Upd3. Do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Comments Comments (31)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not a rated contest?

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

    It's a training, not even a contest (created with Codeforces::Gyms). And yes, it'll be unrated.

    → Reply
»
12 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Handlers of 2 testers look alike :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    I just wonder...Who is the girl in the photo of your profile? She is so cute...

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      His younger sister, I guess... Yours is also cute :x

      → Reply
»
12 years ago, # |
  Vote: I like it +33 Vote: I do not like it

interesting to see natalia and i_love_natalia to be tester team :D

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Registration is opened.

Please note that you must read from file input.txt, not from stdin, and write to file output.txt, not to stdout.

If you use GNU C/C++ compiler, don't use %lld to read or write 64-bit integers. Use %I64d or cin/cout.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem K, Does the problem ask "Deleting the minimal number of digits such that the string "13" won't appear as a substring?" If so, I suggest a better problem description next time, especially for non-Russian readers like me. I really hate figuring out what to do in such kind of problems.

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

    > Does the problem ask “Deleting the minimal number of digits such that the string ”13“ won’t appear as a substring?”

    Yes, it does. It was clearly written in the output format. Many people, and non-Russians too, understood the statement and solved it — I don't know why you couldn't do the same.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Could you point out which sentence including this? I was confused at the beginning, then decided to search the problem's title on Google and got its meaning.

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

        Well, it doesn't explicitly say it, but it says that Kostya is afraid of the page's number, and it is written on the page between 12 and 14, labeled "!#". This is what made it clear to me.

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

        Legend:

        he is afraid of this page's number

        Output format:

        minimal number of symbols that should be removed from the text such that Kostya's unpleasant number will not occur in it as a substring

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

          "Kostya is sick of triskaidekaphobia , i.e. he is afraid of this page’s number." This is what I can read from English statement and I still can't recognize any "13" in it.

          It's not a big deal to me, yet making the statement clearer would be better I think :)

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            Any PDF reader says that the page's number is 13 :)

            → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Sorry, that was entirely my fault. However, I'm not sure if Kostya had nightmare in his dream or not, but I'm sure I had nightmare for wasting 3.5 hours just reading this problem and didn't know what to do until I looked up at the page number (only now did I know that the page number was abnormal :( )

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        And my Foxit PDF reader doesn't show the page number until I drag to the end of the page, which I have never done before :(. I always use my keyboard to scroll up/down or turn the page, which doesn't show the page number. Maybe next time I should prepare against Russian joke.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Hm, my Foxit Reader shows "13/14" at the bottom panel. Anyway, it is not so hard to calculate the page's number by yourself.

          → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an editorial of the problems that we can read somewhere for the ones we didn't solve?

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

    We didn't write the editorial, especially in English; maybe you better ask your questions here? I think many people can answer.

    And if someone writes the editorial, we will very grateful to him :)

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

      Thanks, I just didn't want to bother everyone with too many questions. What was the intended solution for A? I know you would need cycles that would have an LCM of k, but I couldn't figure out how to factor k since it could be so large.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        Usually, when you factor a number, you check all divisors up to square root of this number. In this problem you need only check divisors not greater than 105 — because if factorization of K contains prime number greater than 105, sum of numbers in factorization is surely too large.

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

          Ahh of course, thank you! It seems so obvious now.. Any hints on L?

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            It is obvious that the best amount to donate is some b[i]. Lets sort a and b and precalc sums a[i]+...+a[n-1]. Then for every b[i] we find with binsearch number Ab — how many a[j] are bigger than b[i]. Let Bl be the number of b[j] less than b[i]. So the number of money we get is precalc[n — Ab]+b[i]*(n-Ab-Bl).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Why is the best amount to donate some b[i]? I had to assume that when I solved the problem, but really didn't get that fully. Any hint? :)

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

                If p is not one of b[i], increase it by 1, and sum will not become less than before.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                  ← Rev. 2   Vote: I like it +8 Vote: I do not like it

                  D'oh. You are right! Thank you all, guys!

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it +6 Vote: I do not like it

                If p ≠ bi, we can increment p by 1 and the total sum doesn't decrease.

                too late :(

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 3   Vote: I like it +1 Vote: I do not like it

                If not, we can always increase p until it reaches the first b[i] and this surely gives a more optimal result.

                Edit: too too late :((

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it +1 Vote: I do not like it

                Let x be the best amount to donate. If x is not some b[i] lets look at x+1. We cannot get less money then we got at x because no interval ends at x. So we can get the same amount if there is no i such as a[i]<=x<=b[i] and more money otherwise. So b[i] is the best choice.

                too too too late =)

                → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Obviously, optimal value of p is equal to one of bi. So let's find answer for all of them and get maximum.

            Solution is sweep line. Sort all events (ends of segments) in increasing order and process them in this order. In any position X you should know two values: cnt — number of currently opened segments, and curSum — sum of ai which are greater then X. Initialization: cnt = 0, curSum = sum of all ai. In any event update this values: if this is start point: cnt++, curSum -= X. If end point: cnt-- and find answer for X — it equals to cnt*X + curSum.

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

            You can also implement the solution with 2 fenwick trees.

            One of them you will know how many intervals are open at each point, and on the other how much money you get from intervals that start above that point. pretty simple to update and read.. and for the answer you just go through every data read and get the best !

            ops: don't forget to compress coordenates because 10^9 is too big for memory..

            → Reply