Блог пользователя O--O

Автор O--O, история, 14 месяцев назад, По-английски

Hello, Codeforces!!

We are happy to invite you to TheForces Round #7 (ClassicForces), which will take place on [contest_time:430673]

You will have 2 hours to solve 6 problems

Discord Group

Contests' archive

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

»
14 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

You guys are doing a fantastic job. Thank you for organizing such contests.

»
14 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

great

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

Few things to add as the problemsetter.

Recently some of my peers opened/reopened a Coding Club in my college. I had prepared this contest to inaugurate that event, to make more people in and around my college be more interested in CP, so that they try out the thrill and beauty of this sport. This is the first time I tried preparing problems, so you might find problems very classical, or similar to some other problem you have solved in the past. Also the target audience was mostly people new to coding, so problems will be around Div 3-4.

I would like to thank the testers (and good problemsetters themselves):
blitztage for being the first person to be willing to test the problems
Newtech66 for helping and supporting me with problem preparation
Psychotic_D for discussing these and several other problems with me
O--O for deciding to publicise this contest

Lastly, I hope you participate and enjoy the round. Also, I would love to hear some feedback from you guys so that I can improve myself.
Upd: I hope you liked the problems. Any feedback or scope for improvement? (apart from the time limit for E which wasn't very helpful for participants using py)

»
14 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Is contest rated?????

»
14 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I'm so glad that we could create such rounds with the help of each other, And huge thanks to merlin_ for preparing these problems, I hope our official codeforces round gets reviewed by some coordinator soon, And then we'll have a great surprise for you.

»
14 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Why you do not organize an official round? You create so many problems and more people could solve them.

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Can you check the discord link, its showing invalid at my end

UPD: the link is working now

»
14 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

excited less gooo

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

5 mins delay > _ <!

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    by binary searching on the segment tree.

  • »
    »
    14 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    No need of a segtree. You want to find for every i, the max j less than i such that dp[j] + prefix_sum[j] <= prefix_sum[i]. You can maintain this in a vector by push and pop.

    https://pastebin.pl/view/2817a620

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How are you maintaining increasing subarray things? Can you explain a bit!

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        I am popping the last element till it is bigger than the cirrent value. You can see that in the paste

  • »
    »
    14 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    I did it using a segment tree (which could be avoided),

    You have calculated minimum $$${S_m}$$$ till the $$${(i - 1)^{th}}$$$ index and now you are on $$${i^{th}}$$$ index, assume that the answer for this index is the subarray from $$${[a_j,..a_i]}$$$ so for this to satisfy the non-decreasing condition, the following should hold

    • $$${P_i - P_{j - 1} >= dp[j - 1]}$$$,

    here $$${dp[j - 1]}$$$ is the answer till the prefix of length $$${(j - 1)}$$$ satisfying the condition mentioned in the question, we now just need to see whether the condition holds for the last subarray as well.

    • $$${P_i >= dp[j - 1] + P_{j - 1}}$$$

    Now, you need the last index less than $$${i}$$$ where this condition holds, we can store the right side term for each index in the segment tree and Binary search ($$${as\ function\ is\ monotonic}$$$) for the last index, this can be done in $$${O(Nlog(N))}$$$ or $$${O(Nlog^2(N))}$$$.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did dp + bs + segtree

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem E is a dp problem. I always get stuck in dp problems and am close to the solution but not enough to get AC...

My solution for the example test case:

15
256
653180378

It fails in large inputs (the last one).

Can anyone spot the bug?

Code
  • »
    »
    14 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    Ok, my first approach got MLE (dp[i][val][prev], space complexity $$$O(n^3)$$$) but a nice observation is that we only need the previous 2 values only (dp[2][val][prev], space complexity $$$O(n^2)$$$).

»
14 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Problem D

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Solve each quadrant separately. Sort all points about their slope. Your answer is number of distinct slopes. For slope comparator use integer multiplication only. Annoying edge case when (0,0) is present in array.

    https://pastebin.pl/view/d6a3be9c

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks Can you give the solution of Problem C

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Your edit may confuse people since earlier you asked for a solution of D. Better make a separate comment for C.

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      You could actually just divide the x and y coordinates by the gcd of their absolute values and count the number of distinct pairs. This separates them into the right quadrants automatically.[submission:196421985]

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Problem C

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Min is the max value — min value. Max is just the sum of any group of n-1 points of the maximum difference it can have with another point. This works because the first and last points will be always connected with this setup and the other nodes will cover the largest distance they can possibly cover.

»
14 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Hi, some things i liked about todays round :

  • B and C are good problems

  • E is good dp practise and F has a good idea too.

Some criticims :

  • i assume n^3 is intended in E, however my solution barely passed in TL only after optimizing constant factor, could you raise the TL/lower n in the future

  • another TL related issue on D, if you tried to calculate inverse tan of angles

  • D had quite a few cases for myself tbh, but perhaps my solution could be improved, i would have loved to see x, y>0, it doesnt reduce the level of idea needed to solve, just makes it more pleasant.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    You can avoid floating point operation altogether in D. TL could be intended for that.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Thank you for your feedback, and also for participating. I honestly did not expect so many of you would be willing to solve my problems.

    E was O(n^3), and I didn't realize TL would be that tight. My java soln takes the same time as ur c++ one. Still, I will try to set a more lenient TL in future.

    D's intended soln was involving mapping slopes of lines. I had figured 2-3 solutions using floating point numbers, and failed all of them.
    Brief history, this is actually the first problem I ever came up with (no 2nd, umnik rejected a binary search problem I proposed on codechef 2/3yrs back). I had first thought of x,y>0 only, then I extended the problem to add some casework. I guess I just wanted people to think/spend time on my first problem, even though they got the idea right away.

    I hope I can come up with a better problemset in future, which you would enjoy solving more.

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E was nice

»
14 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

don't ever use Python in TheForces

Problem E will beat u to axx