mesanu's blog

By mesanu, history, 11 months ago, In English

Thank you for participating!

1850A - To My Critics

Idea: mesanu

Tutorial
Solution

1850B - Ten Words of Wisdom

Idea: flamestorm

Tutorial
Solution

1850C - Word on the Paper

Idea: flamestorm

Tutorial
Solution

1850D - Balanced Round

Idea: SlavicG

Tutorial
Solution

1850E - Cardboard for Pictures

Idea: flamestorm

Tutorial
Solution

1850F - We Were Both Children

Idea: mesanu & SlavicG

Tutorial
Solution

1850G - The Morning Star

Idea: flamestorm

Tutorial
Solution

1850H - The Third Letter

Idea: SlavicG

Tutorial
Solution
  • Vote: I like it
  • +78
  • Vote: I do not like it

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

It feels like Problem A was directed at someone 😶

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

    It is easy to write verses

    When you have not what to tell,

    Stinging words and hollow phrases

    In a gangling doggerel.

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

Thanks to authors! The problemset was very cool

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

I enjoyed the problems

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

This competition is the best for me.

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

The best competition for me is this one.

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

For E wasn't it worth mentioning O(1) solution with quadratic formula if we ignore time for taking input

https://codeforces.com/contest/1850/submission/214907399 or https://codeforces.com/contest/1850/submission/214911845

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

    sqrt is log(n), so in fact there are no O(1) solutions

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

    can u explain how can i get 128 bit integers working on my local compiler?

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

      because your computer dose not have a 64-bit compiler.

      128-bit int works only on 64-bit compilers.

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

    calculating the sum takes O(N) time

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

    heh) I saw the problem and immediately thought about binary search and solving the equation. I decided to choose the second one and as a result I first wrote the code for pluses, and then for python (I never used int128)

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

    Hey, How come you have reached to this solution? Can you please explain about your quadratic formula approach

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

      A painting with side s_i requires a cardboard square with side (s_i + 2*w).

      The total area of the cardboard squares (the c input in the problem) is:

      sum (s_i + 2*w)^2 = c <=>
      
      sum (s_i^2 + 4*s_i*w + 4*w^2) = c <=>
      
      sum(s_i^2) - c + 4*sum(s_i)*w + 4*w^2*n = 0
      

      The last equation is quadratic in terms of w and we can solve it using the quadratic formula

      EDIT: Thanks for the correction aryang22

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

        Nice, using commutative and associative properties of sigma, but It didn't clicked to me. This proves how silly I am :(

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

        I guess there should be a bit of correction in the last line:

        sum(s_i^2) - c + 4*sum(s_i)*w + 4*w^2*n = 0
        

        Here, n = number of pictures. If you see this for 1st test case, 3 and 50 and {3,2,1}, so sum(s_i^2) = 14, c = 50, sum(s_i) = 6, and n = 3. If you put w = 1, it satisfies only if you consider n also, that is,

        LHS: 14-50+4*6*w+4*w^2*3 => 14-50+24*(1)+12(1)^2=>-36+36=>0 = RHS

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

          Yeah, absolutely. That should have read sum(4*w^2) which is just equal to 4*w^2*n as you point out, since it does not depend on the summation index.

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

        tried yours in mine, why does it gives compilation errorcode

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

          It will not compile on 64 bit system. It is using __int128 which is of 128 bit

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

          I used c++20

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

    I tried doing like that in C++ but didn't get around precision values

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

    That’s what i did, had problems with the output for large numbers tho, but it’s O(n), not O(1), instead of O(nlogn)

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

For anyone using JAVA , never ever use Arrays.sort even after shuffling the array, I got unnecessary TLE and rectified using Collections.sort. The tests were designed carefully.

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

    thanks

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

    Yes as Arrays.sort uses counting sort versus Collections.sort implements merge

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

      No, Arrays.sort uses dual pivot quick sort, whose worst time complexity can go O(n^2).

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

What is a failed test case for this solution for D?

214942704

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

    I make the same code and i do not know where is the wrong

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

Editorial published during open hacking phase?!

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

G Problem is kind of impossible with python

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

    Even if we forget the fact that there are workarounds to the hash hack in python, we can still solve the problem using python quite easily.

    Instead of using maps/dictionaries, we can just store all values of $$$x$$$, $$$y$$$, $$$x + y$$$ and $$$x - y$$$ in four separate arrays, sort each of them and check the number of equal elements that way. And as far as I know, there is no hack for sorting in python (unlike in java).

    Code (pls forgive me for horrible python): 214952260

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

    i got hacked on G (tle) because for some reason i thought i had to sort the points in order to get the intersection with y = x+c and y = -x + c lines.

    It turns out this is unnecessary and you can solve the question with linear time O(N).

    HACKED submission O(Nlog(N))

    O(N) submission

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

    That is (quite obivously) code obfuscation, which is not allowed. Hopefully they'll get skipped for breaking rules.

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

      what does code obfuscation mean?

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

        If only there was some magical place where you could just type the words "what does obfuscation mean" and you'd get an answer instantly...

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

          But how many defines is code obfuscation then? Some c++ solutions are absolutely unreadable even though their authors had no intention to muddle their code.

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

            I don't think there are any specific numbers I can give; I think the more important part is intention:

            If the author didn't intend to make the code unreadable (and they can read it themselves), I wouldn't call it obfuscation.

            If the author deliberately made the code unreadable (possibly using automated help), I would definitely call it obfuscation.

            I think it should be clear that the aforementioned code falls under the second case.

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

              Unfortunately I saw a lot of solutions with defines like this that make the code unreadable. But I don't really know what to do with that as I haven't found any flag/signal. button yet.

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

            I think the only reason you said this is because you cheated.

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

    Please ban him MikeMirzayanov

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

    Of course, this is an obvious violation of the rules, and the user will be punished.

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

    What the hell lol.. he seems too scared of being hacked

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

Hello! This is my first contest and I submitted the problem A. I was registered but I do not see an increase in my rating, can someone tell me when will I get them?

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

can someone try to hack my solutions?

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

I used binary search for problem-E but it has some error which I am unable to figure out. Can anyone please help me find error in my binary search logic for my submission 214950555. ? edit : when i set r = 1e10 the sample test-cases passed but on submission it fails again on some test case.

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

    it looks like the res function might overflow, I had that problem and dealt with it as explained in the editorial. you can also use __int128 instead of long long to avoid overflow.

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

    try r=sqrt(c) , it's the smallest value of r that can be valid

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

Thanks for this round. The round was very enjoyable!

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

Why this solution TLE in problem F because It does unnecessary work when we have more occurrences of one elment. I think the TC Is exactly the same as the one proposed by the editorial in the end. Also if we have the test case 1,2,3....,2e5. The solution posted does the same number of operations as the one of the editorial. Am I wrong thinking that this has the same TC as editorial?

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

    If all n values of ai are equal to 2, each one will need n/2 iterations, in total n*n/2 operations.

    Therefore it is necessary to treat together the array values that are equal.

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

maybe f can be hacked, consider case {1,1,1...} * 10^5

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

    We keep in cnt_i how many frogs we have for each hop distance.

    this prevents it.

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

i think E problem's optimal solution O(N) my submission

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

I liked problem H . Before reading editorial, i didn't though it will turn that easy.

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

can someone explain why my E solution is accepted here:
https://codeforces.com/contest/1850/submission/214991383

but it is failing here:
https://codeforces.com/contest/1850/submission/214991353

the only difference is in my accepted version, i did (sizes[i] + w * 2) * (sizes[i] + w * 2)
but in the failing version, i did pow((sizes[i] + w * 2), 2)

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

Can someone help me understand why my solution for G got hacked? I have written same code as tutorial. https://codeforces.com/contest/1850/submission/214891422

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

Really a very good, balanced, and learning contest for beginners.

Thanks to the Author.

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

In this contest can my E be WA, G be TL?

My submission in E in contest: 214829184. I don't know how it's passed pretests. In code wrongly I did: x = s[i] + 2 * md + 1 and printed l but x should be s[i] + 2 * md and printed l — 1. Like this code: 214997775 which I submitted after contest. Please let me know if it's hackable.

My submission in G in contest: 214869824. Can it be TL or ML? It passed pretests with 1668 ms 76900 KB(Time limit is 2s). After contest I optimized it (removed set) and passed pretests with 904 ms 39300 KB(214997753). Please let me know it's hackable.

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

Very good problem set. Thanks to all the people who were involved in organizing this round.

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

can you guys pls explain to me how not to get integer overflow in my submission?

https://codeforces.com/contest/1850/submission/215016417

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

    Someone suggested me to use long double and it worked. While printing the value, typecast it into long long to get the desired format

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

I was wondering if someone used Newton Raphson method for solving E?

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

During the contest,I misunderstand Problem F,I think each second we can place a trap,so in this case,can we also calculate the maximum number of the frogs we can catch?I need help,thanks.

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

Nice round , I hope all next rounds(div4) will be on this level

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

Hello, during the contest I submitted this code which got accepted, but after that my code go from accepted to "In queue", can anyone explain? Thank you

Here's the link to the code: https://codeforces.com/contest/1850/submission/214905784

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

Can anyone help me my code has resulted in TLE in system testing?, it is having similar complexity as of author O(nlogn)

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

MikeMirzayanov Unlike the original contests/exams in real life,can I get assistance from external websites while doing a contest? I mean it's quite easy,I have seen it. I am doubting a lot

please answer my question

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

The solution of F was already available on geeks for geeks and other various websites , seems to be a quite popular problem

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

how does my morning star submission got hacked I did the same thing said in the tutorial lol

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

I used an unordered map on F. I will never use an unordered map again.

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

Why does that give TLE if unordered_map is used instead of the normal map in C++? Can anyone tell me when to use unordered_map and normal map?

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

Can anyone explaine how Wrapper function works? This is my hacked submission: https://codeforces.com/contest/1850/submission/214906792 And then i fixed it by Wrapper function which make my submisson accept https://codeforces.com/contest/1850/submission/214984466 *sorry for bad english

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

can someone tell why Question 'G' Fails for an Unordered map, but runs absolutely fine for ordered map

void mr_kamran(){

ll n; cin>>n; ll ans = 0; unordered_map<ll,ll>m1,m2,m3,m4; for(int i = 0;i<n;++i) { ll x,y; cin>>x>>y; m1[x]++; m2[y]++; m3[y-x]++; m4[y+x]++; } for(auto it : m1) { ans+=(it.second*(it.second-1)); } for(auto it : m2) { ans+=(it.second*(it.second-1)); } for(auto it : m3) { ans+=(it.second*(it.second-1));
} for(auto it : m4) { ans+=(it.second*(it.second-1)); } cout<<ans<<an;

}

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

COULD ANYONE PLEASE EXPLAIN WHY USE OF THE QUADRATIC FORMULA IS NOT WORKING IN E PROBLEM?

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

can someone help me to optimize this solution for G problem:

https://codeforces.com/contest/1850/submission/215083504

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

Regarding Maths solution for E problem

Why I get compilation error for this solution: https://codeforces.com/contest/1850/submission/215091151

but this other solution works: https://codeforces.com/contest/1850/submission/214911845

im going crazy, literally same thing

Pleasse help someone

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

Solved problem H using Union Find.

215052919

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

Hello, guys, could you share some useful resources about harmonic series, especially how it can be used in solving cp problems?

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

is it possible to solve problem G with dp ?

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

can anyone tell me how this code doesn't work problem E https://codeforces.com/contest/1850/submission/215107429

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

why my solution isn't working on 2 test case in problem B. code

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    int ans = v[0].second;
    int mx = 0;

    Consider the case when first pair was 11 and INF . your answer won't get updated

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

      isn't that what the problem wants, not to get updated if > 10 is first value

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

        well , you are assuming that the v[0].first will not be greater than 10.

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

          well, i am using &&(AND) so it should'nt get updated

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

            You gave the variable mx value 0 before even checking v[0].first is less than 11 or not . Change both ans and mx to -1 and it should pass

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

              it worked. Thanks, learnt the lesson.

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

1850E - Картон для картин

Can someone Explain Why my code gives WA? For Some Test Cases it the While Loop Breaks and prints 1 which I used for Checking.

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

    in your predicate function (s) 'ans' variable is overflowing.

    to combat this return ans as soon as it becomes larger than c

    ll s(ll md, vector &v) { ll ans = 0; for (ll i = 0; i < v.size(); i++) { ans += ((v[i] + 2 * md) * (v[i] + 2 * md)); if(ans>c) return ans; } return ans; }

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

      Thanks, It worked!!

      How did you spot it?

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

        like md is 1e9 now you square it becomes 1e18

        now you are adding it a maximum of 1e5 times

        so 1e18 X 1e5 will give you 1e23 — overflow

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

Problem E was headache for beginners. Handling large int values...ahhh!

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

why F is nlog(n)? if there are 2e5 1 than is n*n

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

    hash the count of each number

    so even is there are 1e5 1s the answer will run in n

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

      I don't think they say that in this problem .Is there a hint here? It is guaranteed that the sum of n over all test cases does not exceed 2⋅105

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

        i did not get your point sorry lol

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

          the problem f isn't say hash the count of each number.

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

            you just have(can ig) to do it in order to solve it lol

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

              sorry ig our views differ due to our solutions

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

              but i also n't understand

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

                In the case {1,1,1,1,1,1 } You only need to consider the number 1 only 1 time. So basically what you do is that you store the frequency of 1 (6 in this case), and then loop only one time instead of 6. After each iteration, you add 6 to all the factors of 1, denoting that 1 will visit position i 6 times.

                Hope you got the idea.

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

    It looks like n*n but it's not. the time complexity is n+n/2+n/3+n/4+n/5 +... We can factor out n and it becomes n(1+1/2+1/3+1/4 + .... + 1/n) which you should be familiar with if you have taken calculus. It's called the harmonic series. If you aren't familiar with calculus, all you need to know is that 1+1/2+1/3+1/4 + ... + 1/n is approximately equal to log(n) where n is the number of terms

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

why in problem G it gives TLE error if we use unordered_map<int,int> instead of map<int,int>. The time complexity of unordered_map is O(1) whereas operations on map take O(log n) time.

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

problemset was so cool but i think the "word on the paper" problem was too easy for problem C

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

For problem H dfs gives me runtime error, and

sol2 sol is getting accepted, Can someone explain me why??

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

Hey guys! Can somebody help me please why in task E — Cardboard for Pictures we should use mid = l + (r — l) / 2? I am new at this and would appreciate any answer)

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

    It's same as mid=(l+r)/2 but it's recommended to use mid=l+(r—l)/2 to avoid overflow.

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

In H if there is a cycle can one of the 2 paths give us correct coordinates and another one not.Like can this be a case?

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

How to approach problem F if condition would have been that we place one new trap each second unitl game conitnues. Thanks In advance

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

Nice problems but i got minus xD

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

easy problem

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

SlavicG Can you explain why u also pushed negative edges in the last problem

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

G — The Morning Star: In this problem, I received a "Time Limit Exceeded" error while using unordered_map, but it was accepted when I used map. However, I believe that unordered_map is faster than map, so why did the opposite happen here?

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

I wrote this code in C for problem F 216397398 It shows [Time limit exceeded on test 9]. I can't figure out the problem. Can someone please tell me the problem and how to solve it?

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

Can we solve H using different approach?: For all loops found in graph, I check if "cnt" of the loop is equal to 0. "cnt" of the loop is sum of all (-d)s for all adjacent vertexes in the loop. For example, if we have loop

(a, b, d)

1 2 1

2 3 2

3 1 -3

cnt of this loop is 0. (-1-2-(-3) = 0). If cnt of the loop is not zero, it means that every soldier in the loop belongs to 2 different camps. My code gives WA3: 216588864

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

can someone explain how time complexity in problem F came out to be O(nlogn).

this is how i am calculating. for each i — we run the nested loop (n/i) times. so O(i)*O(n/i) = O(n).

where am i wrong here ?

PS: got it.

it should be sum_(i goes from 1 to ) (n / i) = n/1+n/2+n/3+...+n/n = n(1+1/2+1/3...+1/n) = nlogn

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

can we do F by checking for cycle ?

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

Comment on G implementation

If you want to calculate $$$n(n-1)$$$, you can instead calculate $$$2(1+2+...+(n-1))$$$.

By using this, you can avoid the second calculation pass and have a cleaner solution (https://codeforces.com/contest/1850/submission/221488328)

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

I want to ask why I'm using python3 runtimeerror in test 30,https://codeforces.com/contest/1850/submission/221637571 this is my code

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

can anybody please tell me a counter test case for F problem according to my code? please

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

I have no idea why B problem (case 2) isn't passing. Here's my code https://pastebin.com/31yfYzrV

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

For part E, f(x) = sum of squares of s + 4*w*(w*n+sum of s). You can verify this by expanding each bracket in f(x). Both the sum of squares of sum and the sum of s can be computed in O(n) time only once, and then used to calculate f(x) in each binary search iteration in O(1). So in total, you perform one O(n) operation and one O(log n) operation. If you want, you can view my submission at code 239192984.

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

I wonder why the G question times out with unordered_map

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

Solved F

What a beautiful problem!

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

can Anyone SlavicG please tell why my solution for problem H is giving TLE
258450042

I have doubt on using map<pair<ll,ll>,ll> me;

I have been searching on codeforces blog for what may be the problem but unable to find

I tried searching for constant factor TLE blogs but unable to find so can anyone kindly tell what is wrong

According to me time complexity is O(nlogn) where n= m (the number of conditions given in problem)

I think my solution logic may be wrong but then also want to know what thing is the leading to TLE as I have encountered similar TLE problem previously in some different question also

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

Interestingly in G, if you were to make a map of ints and do diag1 [y-x]++, it will give you wrong answer at test case 12, but the same with diag1 [x-y]++ gives an accepted solution. Note that both these cases work when you make a map of long long.