awoo's blog

By awoo, history, 3 months ago, translation, In English

1476A - K-divisible Sum

Idea: vovuh

Tutorial
Solution (adedalic)

1476B - Inflation

Idea: adedalic

Tutorial
Solution (adedalic)

1476C - Longest Simple Cycle

Idea: adedalic

Tutorial
Solution (adedalic)

1476D - Journey

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (BledDest)

1476E - Pattern Matching

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1476F - Lanterns

Idea: BledDest

Tutorial
Solution (BledDest)

1476G - Minimum Difference

Idea: Neon

Tutorial
Solution (Neon)
 
 
 
 
  • Vote: I like it
  • +143
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Problem E was beautiful! Thanks :D

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Finally a contest with less ad-hoc!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

past 2 contests have realised me that i'm more noob at maths than programming :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest! Thanks

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Too many Hacks for problem A . My solution was also hacked .

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great contest. life is loop.

»
3 months ago, # |
  Vote: I like it +89 Vote: I do not like it

contest is good but statement of E was awful

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isnt problem D much easier than problem C?

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem C , How the value of the following test case will be 6? please explain..

input
3
2 4 2 
-1 2 4 
-1 2 1 
output
6
»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I think Problem D is simpler to use the Disjoint-set. Am I right?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It can be done simply by moving from current city to Right to find the largest pattern of RL...RL or RL...RLR and similarly on left from current city to left as LR...LR or LR...LRL and length of both the patterns + 1 will be the max cities visited from current city

    You can see my solution : https://codeforces.com/contest/1476/submission/106090614

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the exact same thing.. but my solution didn't work. Any edge cases I might be missing? My code

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This was a very nice contest after a while. Kudos to the authors, each and every problem in the contest that I solved / up-solved taught me something new. Hope for more such rounds :)

»
3 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Can someone help me figure out the error of code for submission below? My Code Here is my code for problem F. It gets wrong answer on test 5, case 1259. However, I can't get that sample.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone tell me how to solve question D recursively and doing memoization?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not by recursive dp, but Errichto explained the iterative dp approach in his yesterday's stream

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No like I am asking like can we solve it that way(recursive dp) like I am stuck and unable to move forward in my approach.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can solve it by recursion just reverse the starting position

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For B, can anyone explain why there's a k-1 added to 100ll * p[i] - k * pSum?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It is basically done to take ceil of the value.

    Let me make it more clear — Ceil(a/b) == (a+(b-1))/b

    You can check this by taking two cases -

    1. a = k*b. Both functions return k

    2. a = k*b + x (0<x<b). Both functions return k+1;

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but in editorial he didn't mention the ceil thing i understand it from the code but i dont understand the purpose of it, if u can explain please

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is mentioned in the editorial that -

        $$$x \ge \left\lceil \frac{100 \cdot p_j - k \cdot (p_0 + \dots + p_{j - 1})}{k} \right\rceil$$$

        Notice the bracket, that is for denoting ceil function.

        Now the next question is why do we even need that — because x is a non negative integer and right hand side acc. to maths will return a floating value (which may not be integer).

        Let's take an example — You know x is an integer and after solving RHS you get -

        $$$x \geq 1.2 $$$

        So definitely you know you should pick next integer (ceil value) as answer i.e. x = 2.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why we need to take the ceil.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for clarifying that. However, when I use ceil(100ll * p[i] - k * pSum), it says Wrong Answer. What is the reason for this? Also no one has used the in-built ceil function in their code. Please clarify if possible.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

A constant optimization for 1476G - Minimum Difference -- observing that the upper bound of value $$$c$$$ always equals to the lower bound of $$$(c + 1)$$$, we can store only the lower bounds (but not both as in the model solution),

You can see my submission 106048247 for the detail.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    There is no need of segment trees for 1476F - Lanterns. We need only two operations:

    • The one is to query $$$\max\{(j + p_j), \dots, (i + p_i)\}$$$ for increasing $$$i$$$.
    • The other one is to find the minimum $$$j$$$ where $$$\mathrm{dp}[j] \geq i - p_i - 1$$$.

    The two operations can be supported by two standard (monotonic) stack and std::lower_bound.

    My submission 106219219.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -39 Vote: I do not like it

      forget about this stupid problem is your profile photo-real ??

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sure. What's your point?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -53 Vote: I do not like it

          First of all, I have to wait for 10 minutes to comment, and second, you are cute (are you interested in unrated guys ??)

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it -10 Vote: I do not like it

            Can ya bitches stop being creepy to random ladies over the internet?

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it -38 Vote: I do not like it

              you created an account just to comment on this. I respect that.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in the numerator why x = max(x, (100ll * p[i] — k * pSum + k — 1) / k); k-1

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, why can't I topsort it?

»
2 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

BledDest problem E : can there be a pattern which matches non of given string?i meant redundant pattern.

Edit : yup!! that was silly,

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

In E you can also find a match converting the string to integer. The number of possible strings is $$$27^k$$$, so every pattern can be indexed.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

couldn't you also have used two pointers in problem D (journey)?

using two other pointers to find the longest distance you can travel to the left/right, and calculating if you are able to travel in the direction or not.

the answer would be one plus the distance you can travel to the right and the distance you can travel to the left, as you would be able to travel back in any point in time

my solution

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Question for problem E

Input

  • 4 4 4
  • aaaa
  • aaaa
  • aaaa
  • aaaa
  • aaaa 2
  • aaaa 2
  • aaaa 2
  • aaaa 2

The solution's output is "NO", but I think 2 1 3 4 is right, do I understand the problem wrong?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Your input is not correct. All patterns should be pairwise distinct.