SashaT9's blog

By SashaT9, history, 7 months ago, In English

1857A - Array Coloring

Author: SashaT9, prepared: SashaT9, Skillful_Wanderer

Tutorial
Code C++
Code Python
Rate the problem

1857B - Maximum Rounding

Author: SashaT9, prepared: FBI, Skillful_Wanderer

Tutorial
Code C++
Code Python
Rate the problem

1857C - Assembly via Minimums

Author: SashaT9, prepared: SashaT9, Skillful_Wanderer

Tutorial
Code C++
Code Python
Rate the problem

1857D - Strong Vertices

Author: Pa_sha, prepared: SashaT9, Skillful_Wanderer

Tutorial
Code C++
Code Python
Rate the problem

1857E - Power of Points

Author: SashaT9, prepared: SashaT9, Skillful_Wanderer

Tutorial
Code C++
Code Python
Rate the problem

1857F - Sum and Product

Author: Pa_sha, prepared: Pa_sha, Skillful_Wanderer

Tutorial
Code C++
Code Python
Rate the problem

1857G - Counting Graphs

Author: SashaT9, prepared: SashaT9, Skillful_Wanderer

Tutorial
Code C++
Code Python
Rate the problem
  • Vote: I like it
  • +95
  • Vote: I do not like it

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

Thanks for the editorial!

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

In problem F (also in general), you can use sqrtl(x) for a precise square root function.

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

    I failed test 10 with sqrtl though 217692816

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

      Do you know why?

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

      You are not printing anything when y%sol1 != 0 or when y%sol2 != 0.

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

      if (sol1 == 0 || y%sol1 != 0) continue; the result not printed for this case so you should to handle it. check your solution again. Also this line....

      if (sol2 == 0 || y%sol2 != 0) continue;

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

In problem B ,how the iterations are done.

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

Can you attach this editorial to the contest's materials? UPD: I can see it now. Nice contest:D

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

This round was one of the most interesting divs for me. I spent most of the round trying to solve A. I never got it, but I really liked it (usually I think the opposite about unsolved problems :))

In general, thanks for the round, it was really cool

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

    well in A it can be observed that since sum of both color would be of diffrent parity which implies (even,odd or odd,even) sum for both color and if we add even sum with odd sum it would always give odd value (even + odd = odd) hence sum should always be odd.

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

There is an even simpler solution to A. If the sum is even then, on any colouring, the parity of the two colour sets must be the same; if it is odd then they must be different. Hence one can simply sum the array and check the parity of the sum.

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

E can also be solved with DP: 217832098 so sad during contest i didn't have enough time to remember about case with one point

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

It was a great contest with thought-provoking problems. I am hoping to get pupil through the results of this one, and I'm so glad to finally make it to 1200 after 3 months of trying ^^

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

Mathforces!

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

    As for me, mathematics was only in two problems

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

Alternate and hopefully more intuitive solution for E:

We shall work based on adding and subtracting segment lengths.

  1. Let us shift the elements in the array such that the minimum point starts at 1, and then sort that array. We should also maintain a dictionary to keep track of array value -> computed value.
  2. Notice that sum(arr) = s will give the first points answer.
  3. After moving on to the next segment, s will increase by seg_len * (-(n-i-1) + (i-1)) for the ith segment. So we can compute this over all remaining segments from 1 to n-1
  4. In the case of duplicates, we can just skip over computing that guy.
  5. Use the dictionary to map our computed answers back to the correct order of output.

Submission: https://codeforces.com/contest/1857/submission/217837318

I found this easier than working with prefixes and suffixes, and also than the formula given in the editorial. It felt more intuitive to just slide over next segments to compute them, adding and subtracting segment lengths accordingly

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

Thanks for the round, it was great. The only problem I didn't like was B, since it was heavy implementation, and probably a little too hard for div3B. And I think F is just too easy if you know quadratic equations, and very hard if you don't (except if there is a solution not depending on that that I'm unaware of). Overall the round was great :)

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

    I do not remember asking for ur opinion of the problems.

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

      You know, I don't remember my E failing during the round, especially since it cost you the promotion to expert ;)

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

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

        Tell me that u are strange person without actually telling me

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

          Tell me that you don't understand the idea of memes without actually telling me.

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

            Tell me that u dont have life without actually telling me(your stats on cf last year :)))))))

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

I tried the problem A in C++ yesterday (the first time I used it in a competitive programming contest) and for some reason the code was returning completely random results with different builds despite the same exact code, which is why I can't solve it even though I can :(

For problem A, my approach was to use prefix sum array, then for a for loop from 1 to n with i as the variable, we consider the sum of elements from [1..i] and the sum of elements from [i+1..n]. If both sums are odd or even then we find the answer.

For problem B, I basically implemented the problem's requirements. Didn't get it right on time because of burn out from problem A, so I don't solve it either.

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

    did your solution to A got AC?

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

      No, unfortunately.

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

        yea thought that it wouldn't because your are only dividing the array into 2 subarrays while its possible to taking 2 different subsequences of the array that can would satisfy the parity requirement.

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

          I actually just considered that LOL. I did thought of the possibility of inputs solvable using subsequences at the time of solving it, but didn't think deep enough to realize the problem.

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

            does happen with me all the time :) one small tip, when ever there is parity remember this even + even = even , even + odd = odd , odd + odd = even , helped be many a times :) though I still suck a coding

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

    Can you send a link to your submission?

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

i think B,C need to be easier with clear statement as this div is for low rated contestants

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

G was cute :)

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

Can anyone please suggest a platform or a discord server where we can interact with people about Competitive Programming ? Please , I haven't any community like this , help a brother out .

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

I have one doubt in F a[i] + a[j] = x => (a[i] + a[j])^2 = x^2 => a[i]^2 + a[j]^2 + 2a[i].a[j] = x^2

=> a[i]^2 + a[j]^2 = x^2-2y (as a[i].a[j] = y)

so this way we get a[i]^2 + a[j]^2 = x^2-2y this equation so is there a way to prove that for this equation there are only two values of a[i] and a[j] that satisfy this equation? as mentioned in the tutorial

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

    The fundamental theorem of algebra says a polynomial of degree $$$n$$$ has $$$n$$$ roots (they can be not distinct).

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

    You know, Vieta theorem was proven eons ago), it has either 2 distinct roots, 2 equal roots, or no roots

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

      Why can't I submit code..still showing system testing 100 %

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

    Substitute $$$a_i = x - a_j$$$ or the other way around and you get a quadratic equation with one variable since $$$x$$$ and $$$y$$$ are constant. Of course, it has at most two distinct solutions.

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

      oh yeah Thank you

      for the above replies earlier I was actually not looking for the proof, that a polynomial of degree 2 has 2 roots, I was just asking for that using my approach is it possible to prove that it has just two values of a[i] and a[j], as I wasn't able to get the hint that during the actual content that we can make a polynomial equation using that, but this idea clicked me.

      but thanks to all of u

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

Math Problems,and in my opinion,F is a little easy.

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

What a good contest! the problems were really easy to understand! thank you for this contest!!!

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

Why is the contest frozen for so long MikeMirzayanov

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

Can someone suggest some good problem around G to practice .

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

Don't forget to stop sys testing

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

why am i getting TLE on Problem F at test case 41 ?217727479

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

The fourth test of C. I hope I can get some help. "Runtime error" 217874350

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

The fourth test of C. I hope I can get some help. "Runtime error" 217874350

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

Is it for me only or anyone else also faced the difficulty in understanding the problem B statement?

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

    Just you must get max digit that you can with some round operations(may be zero)

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

for(int i=0;i<m;i+=--n)cout<<b[i]<<' '; cout<<"1000000000\n"; can anyone please tell me what actually done here, In problem B Code

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    for(int i=0;i<m;i+=--n)cout<<b[i]<<' ';
    cout<<"1000000000\n";
    

    If you don't understand the part with i+=--n, than it is the same as

    for(int i=0;i<m;i+=n)
    {
         cout<<b[i]<<' ';
         n--;
    }
    

    meaning that we output $$$b[0],b[n-1],b[n+n-2],b[n+n+n-3],\dots$$$

    At last we output $$$10^9$$$ because we can't determine the max element from $$$a$$$, and $$$10^9$$$ is the "neutral" one. All the elements in the array $$$b$$$ are not greater than $$$10^9$$$.

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

Problem B, in my opinion, has a solution easier than in the author's. It was enough to turn string into an vector int, where each element is a digit of a number, and comparison and rounding is much more pleasant in terms of implementing the solution.

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

My solution for problem F : https://codeforces.com/contest/1857/submission/217713950 got hacked during the contest. I used a map instead of a umap and it passed testing. Why did that happen?

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

Reading the editorial of E, I can't understand how to pass from the first line of the formulae to the second one. I'm sorry, but my last courses of maths are 30 years ago! Thanks in advance

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

    the $$$n$$$ in the second line is the sum of all the $$$'1's$$$ in the first line. Since the $$$s$$$ is a fixed value,so we can extract $$$s$$$ from the two $$$\sum \quad$$$,which are $$$s \cdot i$$$ and $$$-s \cdot (n-i)$$$

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

      Thanks, I forgot to consider s as a fixed value.

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

In problem F i run a loop for checking it is perfect square root or not. https://codeforces.com/contest/1857/submission/217941678 Loop is from (s-1) to (s+1) so at max 3 times it will run , but is giving TLE on Test case 65, same code i just checked by if else condition for these 3 values i got AC. https://codeforces.com/contest/1857/submission/217941713

What can be possible resons as Time complexity will increase 3 times so from 500ms --> 1500ms but is over more then 4s

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

    ll int s=sqrtl(d)

    The variable s is long long here.

    for(int i=max(0LL,s-1);i<=(s+1);i++)

    Meanwhile the variable i is int here, although max(0LL,s-1) will return the number greater than or equal to 0 but the convert from long long to int may give negative number because of the overflow, the for here may loop in a huge range (for example -1e9 to 1e9) that can cause the TLE.

    You can declare i as long long and submit again.

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

Thanks for this round! All the questions are good.And the ways to solve the problems are interesting!!

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

Why hash collisions can't be done for officials Python solution for problem F

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

    In Python 3.x, the result of hashing the string will be different across code invocations, but integer hashing is always the same. So, it is impossible to come up with a test against random hashing.

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

Dude i just try try reach pupil!

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

I understand that in tutorial problem G, you can put (s — w + 1) weights into the edge, but the required is only one MST, so you cannot put the weight w, but the formula (s — w + 1) remains because of the possibility of not choosing that edge. I don't know am I wrong?

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

The official Python solution to problem F writes the answers to the queries one per line, rather than all on the same line (as specified in the problem) yet passes the tests. Does the checker not check the layout of the results?

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

The provided Python solution to problem F converts the values in the array to strings before counting them, rather than simply counting the number of instances of each value as an integer. I did some experiments and this seems to be necessary to get the required performance (in particular to pass test 30), but I have no idea why this should be faster. Can anybody suggest why this should improve things?

Note that the official C++ solution doesn't do this.

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

    In Python, structures such as set, dict, defaultdict and Counter are implemented as hash tables. The analogue of Python dict in c++ is unordered_map, and as you know, this structure is very popular for hacking using anti-hash-table tests. Test 30 is exactly the anti-hash-table test for Python, which increases the time complexity of finding an element by key from O(1) to O(n). To prevent the Python code from being hacked, commonly people use a custom randomized hash function (the code can be found here). Now about provided solution, in Python hashing of int type always happens in the same way, but str is hashed differently each time the code is run, so it's convenient to just convert int to str. Since the hashing will be different every time, it will be impossible to come up with a test against it. This method turned out to be even faster than using your own randomised hash function.

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

I am wondering why in Question F (Sum and Product), when I used unordered_map, I gdt TLE for test 29? Once I changed it to map, my answer got accepted? but generally speaking, unordered_map is faster. I know that in the worst case, it takes O(n) time for unordered_map, but I want to know which one I should use when I am faced with another contest.

By the way, here is my code 218194298

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

Really good round. Very interesting problems. Not too hard, not too easy. It's ideally balanced, as I think.

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

Why does below code give TLE @test30? ~~~~~

import math
from collections import Counter
for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    g=Counter(arr)
    q=int(input())
    final=[]

    for _ in range(q):
        s,p=map(int,input().split())
        try:
            t1=(s+math.sqrt(s*s-4*p))/2
            t2=(s-math.sqrt(s*s-4*p))/2
            if t1!=t2:
                print(g[t1]*g[t2])
            else:
                print((g[t1]*(g[t1]-1))//2)
        except:
            print(0)

~~~~~

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

Any idea on why my submission is failing https://codeforces.com/contest/1857/submission/218296798, i kind of did the same thing as in the editorial.

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

Problem C, "In case there are multiple elements bi in array b that satisfy the condition for a particular ai, we choose the smallest bi. This greedy approach works, because we are constructing a in non-decreasing order." (a statement from C tutorial). What does this mean? Can someone explain with an example?

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

Can Anyone Tell me why my code is failing in Question F on test case 13?

https://codeforces.com/contest/1857/submission/218490697

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

i think for problem A all you need to do is count the sum of elements in array if it is even then yes because the sum of two sequences with the same parity will always give even at the end.

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

G is a good problem.

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

Hi there! My code is causing a TIME_LIMIT_EXCEEDED error when executed on large test cases. Here's my code:

Solution (Question B): 219333614

Could you help me how to improve my code to avoid this error? Thanks!

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

problem F is one of the best problems I have ever done on codeforces.

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

Guys I want some friends with whom I can do cp, So, if any one who loves problem solving we could somehow connect.

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

Problem D requires the output to be sorted, but that is never mentioned in the problem! that caused me several WAs on the 3rd test.

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

    Output

    For each test case, output two lines: in the first line, output the number of strong vertices, and in the second line, output all strong vertices in ascending order.

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

G can be solved (dumber way) by $$$O(n log^2n)$$$ centroid decomposition, although it barely fits in time limit

235049670