cry's blog

By cry, 2 months ago, In English

2037A - Twice

Problem Credits: cry
Analysis: cry

Solution
Code (Python)

2037B - Intercepted Inputs

Problem Credits: cry
Analysis: chromate00

Are you a python user and failing test 4?
Solution
Code (Python)

2037C - Superultra's Favorite Permutation

Problem Credits: sum
Analysis: chromate00

Solution
Code (Python)

2037D - Sharky Surfing

Problem Credits: cry
Analysis: chromate00

Solution
Code (Python)

2037E - Kachina's Favorite Binary String

Problem Credits: vgoofficial
Analysis: Intellegent

Solution
Code (Python)

2037F - Ardent Flames

Problem Credits: vgoofficial
Analysis: vgoofficial

Solution
Code (Python)

2037G - Natlan Exploring

Problem Credits: vgoofficial
Analysis: vgoofficial

Solution
Code (Python)
  • Vote: I like it
  • +128
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nice fast editorial

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

fast editorial !! thankYou

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

damn quick editorial

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Very Nice contest. :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

fast tutorial

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Damn! Ultra Fast editorial Great Contest. Very good problems, Thanks!

»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it
»
4 weeks ago, # |
Rev. 18   Vote: I like it 0 Vote: I do not like it

could anyone help me to figure out what is wrong here:292060911

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

yotta fast edito'

Thankkyou

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Hi everyone, I apologize for the statement for D being unavailable for ~15 minutes during the round. It turns out I misspelled \textbf which caused the PDF to not generate. :(

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For 2037F - Ardent Flames can you please explain which intervals are we talking about here? — sorting the events of intervals starting and ending by time and how are we trying to do binary search?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The intervals are possible $$$p$$$ such that $$$m-|p-x|\geq\lceil\frac{h_i}{q}\rceil$$$. You do binary search on the answer, and if such $$$p$$$ exists, you move the right bound to the mid; otherwise left bound.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

very cool round, thank u.

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I liked this contest, especially C exercise was interesting and pretty quirky at first :D Hope to see more div3 contests in the future

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone take a look at my implementation? (since below is my thinking for E which matches the tutorial exactly)

IMPOSSIBLE if and only if there exists no "01" substring, which is equal to querying the entire string and getting an answer of 0.

Otherwise, there is some "01", and we start querying all the prefixes [1, 2], [1, 3] ... [1, n]. Suppose the first one to give a non-zero answer is [1, i]. Let that answer be R. Then, since all prefixes before [1, i] gave 0 as an answer, the string over [0, i-1] is i-1-R 1's followed by R 0's. Also s[i] must be 1. To determine the suffix s[i+1, n], we query over the prefixes still [1, i+1], [1, i+2] ... [1, n], and, at each query, if the answer increases from the previous one, we have a 1 there, otherwise it is 0 there. In total, we take exactly 1 query for each char in s[2, n], meaning we require n-1 queries.

Implementation: https://mirror.codeforces.com/contest/2037/submission/292068546 (skip to very bottom, there is a bunch of template stuff at top)

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

    Bro you should return int in the function

    char(this should be int) interQuery(int a, int b) { std::cout << "? " << a << " " << b << endl; std::cout.flush();

    int r; cin >> r;
    return r;

    }

    Good luck Mate..!!

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      NOOOOO WTH, I didn't solve E due to that BS!!! :(((( This is genuinely heartbreaking -- the difference between being rank ~1500 and being rank ~500

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest, I was glad to participate) Thanks for explaining task G, I was very hesitant when I sent it and got a time limit exceeded on the 5th test

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

D felt like it would be hard problem at first but once u start solving it I found it easier than C

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I was waaay off for D. i was thinking graphs. Thanks for the learning.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

As a Pythonist participant, thanks for covering test 4 on Problem B that gives TLE verdict with dictionaries. I too got this verdict: Submission 291964656 Then, using set for tracking a prior occurrence worked on Submission 291974200 , instead of having to rely on the suggested collections.Counter().

Will have to see if this get hacked or failed in any of the main test.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    As a Pythonist tester, happy to hear :)

    Edit: Looking at your Solution it is probably still hackable as set uses the same hash function as a dict, :(

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You've saved us an unexpected TLE! :clapping:

      Yes, it is also noted under the editorial for Problem B that Set and Dictionary uses same Hash function. But, my understanding is that as Set only stores a single occurrence of an element, there's only that single entry in that Set that will be subject to that collision with every matching hash attempt, unlike a Dictionary where that entry also buckets corresponding values to that key. Please do suggest if you have any such testcase which may fail this submission. I would have been amazed to see it getting hacked on this possibility too.

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

非常好的题目,使我大脑旋转:D

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

Help me with this please: 292083026

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to continue processing hurdles until the left bound of the current hurdle surpasses current power-up.

    For your code, consider:

    1
    4 2 100
    5 5
    7 7
    9 9
    11 20
    2 1
    10 20
    

    which your code gives $$$-1$$$ but the answer is $$$2$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please review my answer too : 292104008 , it also gives output -1 to the above testcase that you have provided and I have run my loop on hurdles not powerups, but I am unable to understand why the answer should be 2 for this testcase and not -1 because after the first hurdle {5 5} the power left should be zero so how will we reach to 10 and get +20 in power.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Jumping through a hurdle doesn't consume power. It only requires enough power.

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

      Thankyou

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to implement the Inclusion-Exclusion in G?

I knew about the principle and just did a bunch of for loops which at least look kinda cool :D 292061306 but I see others used other method.

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

    its essentially iterating through the masks, if the number of elements we're grabbing is even, subtract it, otherwise add it

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Respect the dedication of coding allat, the usual way of implementing the inclusion exclusion is with bitmasks, iterate from 0, having no elements in the set, to 2^n — 1, having everything in the set, when the i'th bit is 1, it means the i'th element is in the set, now u can notice for odd sizes u add for even sizes u subtract, after calculating the current contribution, if the number of set bits was odd add it otherwise subtract it

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain why you did this and what is val array achieving?

    for (int div : divs[x])
        {
            val[div] += dp[i];
            val[div] %= pmod;
        }
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i think it would be better to have G1 with lower constraint on $$$a_i <= 10^3$$$ to allow
$$$O(n*max(d(a_i)) ^ 2)$$$ solution as there are max 32 factors up to 1000, but anyways nice problems.
Thanks for the contest!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It would be solvable in O(nA), where A is maximal a[i] with dp[x] = # of paths ending at element x, so it would be too easy.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to understand why am i getting idleness time limit exceeded. — https://mirror.codeforces.com/contest/2037/submission/292077028. Please someone help.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try with following test case, it shows "!" as answer

    2
    01
    
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest some binary search problems like F (same or little higher difficulty) please.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi I have two doubts.

First, why in problem B, using dictionaries in Python give TLE, but AC in C++?

Second, what is wrong in my code for problem E? https://mirror.codeforces.com/contest/2037/submission/292049495

I query (1, i) for i from 1 to n, find the first point where this value is non zero, and if this value increases fill in 1, else 0.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with this solution for D. 292088654

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

292093110

can someone pls see why this gives a wrong ans and what do I need to change ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my solution for D? it gives tle(test-2). 292076200

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i=h[k].second and the following i=h[i].second are wrong. They're coordinates, not indices.

»
4 weeks ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

can somebody explain tourist code for problem G ? whats the mob array ?? whats the intuition behind the solution ?

291975854

or just simply explain whats the mobius function solution

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -6 Vote: I do not like it

    You can see the mobius function as the coefficients of the inclusive-exclusive solution

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    Mobius function $$$\mu(n) = (-1)^k \cdot [\alpha_1=\alpha_2=\dots=\alpha_k=1]$$$ where $$$n=\prod\limits_{i=1}^k p_i^{\alpha_i}$$$.

    Useful property of Mobius function is that $$$\sum\limits_{d|n}\mu(d)=[n=1]$$$.

    Consider $$$\texttt{dp}[i]$$$ is the number of paths from $$$1$$$ up to $$$i$$$ and $$$\texttt{sum}[i][x]=\sum\limits_{j=1}^{i}\texttt{dp}_j\cdot [a_j=x]$$$.

    We may calculate $$$\texttt{dp}[i]$$$ as $$$\sum\limits_{j=1}^{i-1}\texttt{dp}_j-\sum\limits_{x=1}^{10^6}\texttt{sum}[i-1][x]\cdot [\gcd(x, a_i)=1]$$$. Let us apply the property of Mobius function for $$$[\gcd(x, a_i)=1]$$$. So that:

    $$$ \begin{array}{rl} \texttt{dp[i]} &= \sum\limits_{j=1}^{i-1} \texttt{dp[j]} - \sum\limits_{x=1}^{10^6} \texttt{sum}[i-1][x] \cdot [\gcd(x, a_i) = 1] \\ &= \sum\limits_{j=1}^{i-1} \texttt{dp[j]}-\sum\limits_{x=1}^{10^6} \texttt{sum}[i-1][x] \sum\limits_{d|\gcd(x, a_i)}\mu(d) \\ &=\sum\limits_{j=1}^{i-1} \texttt{dp[j]}-\sum\limits_{x=1}^{10^6} \texttt{sum}[i-1][x] \sum\limits_{d=1}^{10^6}[d|x]\cdot [d|a_i]\cdot \mu(d) \\ &=\sum\limits_{j=1}^{i-1} \texttt{dp[j]}-\sum\limits_{d=1}^{10^6}[d|a_i]\cdot \mu(d)\sum\limits_{x=1}^{10^6}[d|x]\cdot \texttt{sum}[i-1][x] \end{array} $$$

    For each $$$d$$$ you may maintain $$$\sum\limits_{x=1}^{10^6}[d|x]\cdot \texttt{sum}[i-1][x]$$$ and $$$d$$$ is the divisor of $$$a_i$$$ what makes it possible to compute $$$\texttt{dp}[i]$$$ in $$$\mathcal{O}(\sqrt{a_i})$$$.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I loved problem F, any problems like it please? :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Submission

Using Counter still failed me in test case 4 for B (Or maybe there is a mistake in my implementation)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Testcase 4 provokes hash collisions in Python, you can either use a Wrapper to avoid them or use an apporach without hashing.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am aware but the Editorial mentioned using Counter to avoid TLE

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, well it technially works if you do it with strings, but at that point you could just us normal set or dict. To my knowledge Counter uses the same hash function anyways.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My bad, I wrote the note and I'm not really familiar with python. You'd have to use a frequency array of length $$$n$$$.

»
4 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

cry would be blessed if you also post the C++ code rather than just the 3 lines of the explanation in which you think everyone should understand how to solve the problem. Not everyone is a genius like you.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I would've ACed D if I used multiset instead of set. That was the only change I made for my code to AC after the contest... :(

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

292066305 292064554 gpt guy solve g in 3 minutes

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can we solve D problem using dp approach,with two cases only selecting a particular power or ignoring it

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that will be correct but very slow , O(n^2) when seeing high constraints like 1e6. Try thinking greedy

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

One easy way of preventing tle with sets in Python for B is to just move all the factors of k-2 into another map or set and do the same thing.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I don't know why my binary search solution fails. If you could help me with this that would amazin ^-^ thanksss

https://mirror.codeforces.com/contest/2037/submission/292111215

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

Nice contest, as expected from cry! Btw in problem E, were the constraints on $$$n$$$ reduced from $$$10^5$$$ to $$$10^4$$$? I used 32-bit integer during the contest and realized later on that my solution could get hacked...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    In fact, in testing, several testers got WA verdict with n<=10^5 because of overflow. Since its an interactive problem and the query limit is the hard part of the problem (as opposed to the time limit) we decided just to make n<=10^4 so nobody can overflow.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is there a runtime Error for this submission?

https://mirror.codeforces.com/contest/2037/submission/292195133

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The length of counter is not enough. Consider $$$[2,2,1,1,1,1]$$$, your code visits counter[4] and crashes.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

great contest::)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

damn, fast tutorial! nice contest

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will anyone explain how to do G with mobius inversion?

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

Thanks for the contest!
I like to share some lessons I learned during this contest.
With only 30 minutes left, once a tempting idea occurred to me for problem E (do f(1,2), if 0 then impossible, otherwise, do f(1,i) for each i in [2,n])
I rushed into this idea without any checking or some sort of a proof.
It was only when I got WA that I prompted my mind to think about the underlying assumptions in this solution. And I immediately realized, it's possible to do f(n-1,n), same idea. then I rushed again, now lost all the time. and couldn't solve the problem.

Upsolving this task, I realized that if there any "01" substring in s, then it's possible with enough queries to locate this substring and construct the rest. Now, I had another idea, this time, it was not easy at least for me to find the bug, but there was another very strong indication that this cannot be the way. The solution was 150+ lines of ugly troublesome problematic error-prone code. lots of if-else if, lots of ++, +=2, -=2 and shit.. That should have been more than enough to discard this whole idea from the beginning.
But I discovered the problem, after 1 hour, I knew it's not working.

The interesting thing is once I prompted my mind to think again a different solution, I quickly found the right idea, this time it was so convincing and I can see the code is reasonable and elegant.

So, 1. test and challenge your idea, you don't have to have a rigorous proof, but at least some argument, and the min is to see what assumptions you're making
2. if the solution is so long and complicated, with unreasonable amount of cases, it's likely not the intended solution. and if it is, then love yourself and just discard this problem.

This is common sense but sometimes, one forget common sense esp. during contest pressure. I made similar mistake with problem C. I think it will really benefit to write down some tips next time and read before the contest.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the D Question, I was confused that if the jump power is used for particular jump then same cannot be used by it again for eg. jump_power = {1,3,5}, hurdle= {-6, -6} ,then I thought the answer would be -1, since the 5, 3 would be used for first jump and it cannot be reused later. sorry, but can some one please help me find which part of the sentence indicated that we can reuse it twice.thank you

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    "When she is at position x with a jump power of k, she can jump to any integer position in the interval [x,x+k]."

    It is clear that there is not a limit which stop Mualani jumping twice with the same distance.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you, sorry my bad I made a wrong assumption that after jump it decreases/loses its power

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder why G < F? I think the solution of greedy is easy to come out.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

we can also do 2nd by binary search.

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

can somebody explain me why we have to output 2 3 instead of 3 2 in example output? (B problem) my code btw: 292481770 edit: well i just found my code problem (fixing it)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why this is true for G:

Note that we don't actually care what the greatest common factor is, since the only requirement is that the greatest common factor is not 1. This also means that repeat appearances of the same prime number in the factorization of ai doesn't matter at all — we can assume each prime factor occurs exactly once.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's first add the count values from all prime factors, then subtract the count values from all factors with two prime factors, then add the count values from all factors with three prime factors, and so on. It can be seen that actually, the value is only counted one time now.

Can someone explain why this works?

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

For E,

I tried to make the string from left to right (? i n ) ,and in between if a 0 is encountered the remaining following sequence has to be (1111...1000...0)

For the input 2 01 its getting passed in test case 2 but when the same input comes in test case 3 its getting wrong answer!

Could someone please help me out!

Submission: 293642176

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

294078854 Hi, I got a negative output in test 6, can someone please help me to see what's wrong with my code?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem D: testcase 1:

2 5 50 7 14 30 40 2 2 3 1 3 5 18 2 22 32

after taking 4th power-up my total power is 11, but to jump the 2nd hurdle I need a power-up of atleast 12 right? Why is the answer 4 then? shouldn't it be 5?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You skip the 4th powerup at $$$x_i = 18$$$ and take the one at $$$x_i = 22$$$ instead