Vladosiya's blog

By Vladosiya, history, 5 months ago, translation, In English

Hello! Codeforces Round 903 (Div. 3) will start at Oct/12/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by our team: myav, Gornak40, senjougaharin and Vladosiya.

We would like to thank:

  1. MikeMirzayanov for Polygon and Codeforces platforms.

  2. SomethingNew, rniya, zwezdinv for red testing.

  3. makrav, snowysecret, AlexanderL, KseniaShk, pavlekn for yellow testing.

  4. gigabuffoon, EgorUlin, KerakTelor, Pa_sha, I_love_geom, petyb, MinaRagy06, toniskrijelj, FynjyBath for purple testing.

  5. Abo_Samrah, dan_dolmatov, pedrosorio, ezdp, azureglow, Chrisedyong, Apachee, arseny2606 for blue testing.

  6. t0rtik, Sergey140146659, hader239, Modern for cyan testing.

  7. mkshh, petertromso for green testing.

Good luck!

UPD: Editorial

  • Vote: I like it
  • +243
  • Vote: I do not like it

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

Waiting for that round. Hopefully, It will be a great round for me. Best of luck to all contestants :)

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

I hope This contest to be my promotion contest, I wish (:

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

As a green tester I can ensure green participants that they will enjoy this round!

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

Why's this not on the home page yet?

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

As a tester I hope, that contest will be very interesting for all participants!

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

good luck! >.<

remember to read all problem statements

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

As a tester, I hope that this contest will be enjoyed by all participants. Read all problems and good luck! ฅ^•ﻌ•^ฅ

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

Deleted

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

sory i can`t get a think in line 11 you sed"do not have a point of 1900 or higher in the rating." but in line below it you say "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." so is that contest rated for experts or not ?

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

    i guess thay can

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

    It's not, it's just people who at least once reached 1900 will not get in the official standings(though if their current rating is below 1600, the round still will be rated for them).

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

Ez Expert for me

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

At least we know that there will be no bitset problems :)

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

Waiting eagerly. Best of luck to everyone :)

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

I'm not welcome for Div.4 anymore so I must bring out my best in Div.3!

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

is this contest postponed??

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

Hoping to become an expert this round.

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

    Your graph looks exactly like mine!!!! OMG :)

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

      Do you guys give contests together? /s

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

        what do you mean? I am from lebanon, bro is from india...

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

Waiting for this round...! Best of luck for everyone >_<

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

Good luck guys, Never give up......

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

what is the open hacks/hacking phase? pls explain

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

Need more div.2 rounds

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

As a tester, I hope the problems will be enjoyable for you!

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

For the life of me, I will never understand why a Div3 contest has 4 times the Expert+ testers as cyan/green testers. Who are these contests even aimed for?

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

    Probably because someone who consistently solves ABCDE in Div 3. will be an expert. I am guessing a candidate who performs at a performance that lets them stay in the upper end of Div 3. will only solve ABCD (fairly quickly), and solve E occasionally, so that leaves the hardest 3 problems not testable by people who are below experts.

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

Anyone else who just saw a message that the contest has started right now?

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

Good luck everyone!

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

As a late "as a tester comment", I beg for contribution

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

Hope it will be a great contest!

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

i'm not a tester :'0

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

Going to become Expert.

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

    hack like 20 people and it is very possible predictor says you are 3 points short

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

Never felt dumber with a div3C.

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

First time to solve till F, my best performance in div3 :)

Guess which problem took my time most
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No promotion in sight again this time.

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

    it's okey , we will make it sooner or later Bro

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

How to solve D ?

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

    Prime factorize every number and count all the primes. if all the prime count is divisible by n then yes

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

      How did u come up with this? Is there any reference?

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

        You can see that if we do the operation a[i] /= x and a[j]*=x then we are just moving one prime number to another number. so if we want to make all of the number same we have to have prime number count that are multiples of n.

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

        Think in such a way that every prime factor can be distributed over n blocks(size of array) and that too equally.

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

        Note that over any operation, product of all numbers is invariant. Thus, if the final state of all numbers is $$$g$$$, then $$$\prod_{i=1}^na_i = g^n$$$. Thus, for the final state to be achieved, product of all numbers must be a perfect $$$n$$$-th power. Turns out this is sufficient as well. (Why? Hint: Think of how primes will be distributed)

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

      would clarify the relation between N and number of all primes ?

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

        You can find out all primes no more than N in O(N) using Euler sieve.

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

    Find the prime factors of each element and count the total number of occurrences of each prime factor. If all the total number can be divisible by n, then output YES.

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

operation codeforces

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

Anyone found the A,B,C much annoying problems.. this div3 contest must have focussed on the problems D,E,F ... rather than keeping the participants to got stuck at A,B,C these days...!

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

C was so annoying , D < C

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

D, E, F were interesting but i found A a little difficult for div3 A unless there is a trick that i couldn't see. Edit: Thanks got it.

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

    A was just bruteforce, that is usually the case, you can just add s to itself a few times until you get to a fairly big size where you are sure the substr won't appear again and use .find() to check if m is a substring. The strings can only get to like 100 so checking till 200 does the trick.

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

    You could just naively check for at most $$$12$$$ operations or so. Time complexity would be $$$O(2^{12}nm)$$$ which is definitely not optimal, but anyways there are not too many testcases so it can't hurt to try too much

    UPD: $$$k=12$$$ got hacked, maybe try something smaller like $$$k=6$$$

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

      I took leap of faith with $$$O(2^{10}nm)$$$ and it worked

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

    I only checked for 5 steps thats it.

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

Any Hints for F? I was finding max and smax ( max and smax will be maximum and second maximun marked node from children ) and considering maximum distance from a node will be max( max distance from children (max) , distance from parent + 1 (max+1 or smax+1) ).

  • »
    »
    5 months ago, # ^ |
    Rev. 27   Vote: I like it +8 Vote: I do not like it

    Problem F

    Hint

    Claim

    You don't need to calculate distance from every marked vertex. Just calculate distance from the two marked vertices x and y, such that distance(x, y) >= distance(i, j) for all pairs i and j where 1 <= i, j <= n' and 'i ≠ j. This is sufficient.

    Proof

    Let's assume that x and y are the two marked vertices with the maximum distance between them.

    Now, suppose there exists pair of vertices v and z in the tree such that distance(v, z) > max{distance(v, x), distance(v, y)}.

    We can claim that: max{distance(z, y), distance(z, x)} == distance(z, v) + max{distance(v, x), distance(v, y)} > distance(x, y).

    However, this statement contradicts the fact that x and y are the pair of marked vertices with the maximum distance between them. That means there's no such z and v.

    So, you only need to calculate distances from vertices x and y to satisfy the given condition.

    Formula

    $$$f(i) = max(distance(i, x), distance(i, y))$$$ where $$$(1 \le i \le n)$$$ and $$$(x, y)$$$ are the two marked vertices with the maximum distance between them.

    Time complexity: O(n) at most 4 tree traversal. two for finding (x, y). two for calculating distances.

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

What is the level of complexity of problem E in terms of rating? Is it like the 1600 problem?

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

Many of F solutions have been done using some segtree, or dp....
But mine i just did tree trimming....

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

i feel E tests are weak (check my solution)

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

Can someone please explain what's wrong with this submission for question C — perfect square?

for 3rd test case I am getting 179 (instead of 181) as the minimum number of operations but the 90-degrees clockwise rotation of the changed matrix is giving true, can someone please tell me what is wrong with my code?

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

    You got the basic idea right, but you failed to account for the fact that the increase operation might be cyclic. Try doing the 2*2 case by hand to get the idea.

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

    I had similar solution and for elif case you may change traversed elements, so try to repeat the cycle and it worked out for me

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

      Ya, same thought just crossed my mind, "for how may times should we cycle through it?"

      I mean time complexity wise, how should we calculate the upper bound, mathematically?

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

        2 times will be enough, so complexity is the same

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

          but how did you decide that 2 times will be enough, like how do we know that there's no third order alphabet lingering around?

          I mean, I am looking for more concrete approach or proof then just hit and try method.

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

            you cant change from B->A, so you reverse all cases like that on first cycle and on second cycle it will become A->B problem

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

Hi can anyone help me check my solution for D why it WA3? I had to change the loop to a get prime factorial function but I don't see where this one goes wrong. Thanks in advance https://codeforces.com/contest/1881/submission/227896125

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

    you should write clear code and use different variables , your loop conditions might get altered because of value of n.

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

    You're only storing the factors which are <=1000. But there maybe factors >1000 for the given constraints. Try as an example [2182, 2186], the output should be NO, but your code gives YES.

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

It is very sad to say that I have solved B and C, which is normal for a 'pupil', BUT I couldn't pass A :(

Can someone tell me which test case can spoil my code ? 227915244

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

    most probably try larger value of i, like 5 or 10.

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

      I have tried after the contest and got wrong answer. 227927816

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

      Can you try this?

      My Code

      Also please note, it's a logarithmic function.

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

        Yeah! I replaced my check function with

        bool check(string s1, string s2) {
            if (s1.find(s2) != string::npos)
                return true;
            return false;
        }
        

        And I got accepted. Thank you

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

    If x="abc", s="cabcab", your code will get a wrong answer.

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

      Isn't the answer 2 ?

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

        Sorry, I gave a wrong example. I think you should modify your check function. Once s1[i]!=s2[j] and j!=0, maybe you should change i to i-j+1.

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

          I tried to use this:

          bool check(string s1, string s2) {
              if (s1.find(s2) != string::npos)
                  return true;
              return false;
          }
          

          And it works. I am so sad for what I did. It is a silly mistake :( I hope I don't turn to grey again.

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

        For example, if x="abcabcabd", s="abcabd", your check will fail when i=5, j=5, and then you only change j to 0, but i is still 5, which makes you can't find the right match: i=3.

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

          Oh okay, Thank you for your illustration sir

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

    How did you solve B >_<

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

      Your goal is to make all values similar to the smallest value in the given array. This makes you use less steps otherwise, you need to use more than 3 steps for sure. Let's call the smallest value in the array ('mn'). Also you have to make sure that all values in the array are divisible by 'mn'

      Check my code 227853520

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

        Can you please explain this test case 4 4 12

        How can we break 12 into {4,4,4}? If we are dividing into equal parts 12 should be broke into {6,6} not {8,4}.

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

          I got it; they never told we have to divide it into equal parts. I just got confused by the first example 5 into {2,3}, hence was doing {n/2, (n+1)/2}.

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

    I usually solve problems in order, but I couldn't solve A at first too, solved B and C first, then in the last 10 minutes, I made some changes and was able to submit A. It completely fucked up my penalty time though. More than triple of what it usually is.

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

is the contest not rated for div4? made account on cf few weeks back and still a newbie, though i solved 2 problems but my rating didn't change

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

    ratings update is tmrw

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

    It doesn't change instantly, you should wait for the testing phase firstly, and hacking phase secondly, then you should wait for some while maybe for 0 to 72 hours to get the rank updated.

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

Can't you speak English?Is your questions translated by AI?

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

A — Annoying.

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

balanced contest overall. it's disappointing i wasn't able to solve E because i haven't learned dp yet :(

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

Can problem F using bfs many source?. I can't implement it during the contest

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

    Multi source bfs gives nearest red vextex not farthest

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

I felt that today's E was similar (in terms of statement, not solution) to 1798E.

Also, great problemset!

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

Is there a more elegant way to solve F than some very annoying-to-implement tree DP? (Check my submission for my details)

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

How to solve C?

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

    let ip= n-i-1 , jp = n-j-1. cells with indices (i,j) , (j,ip) , (ip,jp) , (jp,i) should be equal for each 0 <= i, j < n

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

      can you tell what is wrong is here:

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

        Update, solved the issue:

        Spoiler
»
5 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can anyone tell me the 371st test for test case 2 in Problem G?

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

If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.
Here is my live Screencast of solving problems [A -> E] (with detailed commentary in Hindi language).

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

Why are there so many hacks on A? What is the hack?

Also: https://codeforces.com/contest/1881/submission/227851818

This looks kinda sus, to escape plagiarism checker?

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

      tried random tests using that logic but it hit file size limit and smaller tests aren't hitting time limit but had 3 hacks using the smaller one

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

    He's definitely a cheater, I see no point int having an infinite while loop with a break statement.

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

Is my solution for problem A hackable

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

Nice ProblemSet :)

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

Maximum possible answer in problem A can be log2(m)+1 . Isn't it?

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

A,B,C,D were tougher than usual div3.

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

Code for generating a testcase to check TLE for problem A

https://ideone.com/c8Rs0m

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

Is using unordered_map in D correct? Shouldn't it give tle? https://codeforces.com/contest/1881/submission/227902139

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

    It's fine. Input constraints guarantee there are at most $$$10^4$$$ values, each less than or equal to $$$10^6$$$, which means up to 20 factors per value ($$$2^{20} > 10^6$$$), so a total of ~200,000 prime factors to add to the map.

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

does hacking reduce points in this round?

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

I think problem F is to find the spanning tree connecting the selected vertices and then get the diameter r->(r+1)/2 as the result but I don't know how to code it. is my idea correct??

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

    Yes, the idea is correct. Maybe you can use the fact that on the smallest tree spanning the marked vertices, every leaf node MUST be a marked vertex. So, root the tree on some arbitrary marked vertex, and trim the leaf nodes until all leaf nodes are marked vertices.

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

I had the idea for the problem F but ran into a bug and ended up wasting my time :3

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

A friendly contest to beginners! Although my B FST... :|

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

nvm i got it

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

everyone seems to be overcomplicating B observation: we can divide a, b, c each into threads of size equal to the greatest common divisor of a, b, c. this will always be optimal therefore, the number of operations would be equal to: ceil((a + b + c) / gcd(a, gcd(b, c)) / 2) (it only takes 1 operations to split into 2 equal threads

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

Hello everyone, I am in bit trouble, I have tried to solve the first question of the contest but I am unable to debug it up. If anyone can help me, I will be very thankful. Thanks My submission

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

    Actually, you're missing out on one index in this for loop,

    for(int i=0;i<x.size()-s.size();i++){

    The variable i should go upto x.size()-s.size(), so the for loop condition should be i<=x.size()-s.size()

    Corrected: https://codeforces.com/contest/1881/submission/227970028

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

      Oh yes. So I need to check the just last substring of size s.size() which I was thinking I have covered in my loop.

      Thanks a lot

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

Why this code always work for Problem D?


void solve() { double n; cin >> n; double m = 1; double s = 1.0 / n; f(i, 0, n) { int x; cin >> x; m *= pow(x, s); } // cnl(m); double a = ceil(m), b = floor(m); if (abs(m - a) < 1e-6 || abs(m - b) < 1e-6) cnl("YES"); else cnl("NO"); }
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's doing the same thing as other's have mentioned above. If the answer is yes, m will be an integer the way it is being calculated

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

Question A: What data can be used for hack

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    cout<<10000<<"\n";
      for(int i=1;i<=10000;i++)
      { cout<<"5 5\n";
        cout<<"abcde\nabcdr\n";
    
      }
    

    ^ This could TLE the ones with already high execution times because they concatenate "abcde" with itself a large number of times along with using a string.find() for a substring with lots of partial matches.

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

Hello, how do I solve 1881G - Anya and the Mysterious String with Segment tree using Lazy propogation? This is what I've done 227967016, I haven't used Lazy propogation and it's TLE.

Thank you in advance.

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

Hackforces again ;)

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

problem A was very bad for div3.

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

Can anyone check this i am getting wrong answer in test case 4 for Problem G

here's my submission : 227971449

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

Problem C was interesting.

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

My rating is 369 and i participated in round903div3 contest. i solved question A but it didnt increased my ratings also the contest history is showing me in unrated section of my profile. Why this round was not rated for me?

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

    Its a bug, it will be updated in a few hours.

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

      Its not updated yet?!! What to do now! My rating is remaining unaffected.

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

        Usually its not this late. Just check the contest tab of other participants, If they got rating for the contest but you didnt, then you should make a new thread about it.

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

My solution was hacked yesterday, again I submitted the same solution and it got accepted. Do the test cases used in hacking not get added to the main test-case?

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

    they will get added after the hacking phase is finished, at the time of system testing.

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

    yes/...after the hacking phase is finished...might take same hours as well.

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

problem F is really beautiful and educational; Approach : 1) run dfs from any arbitrary node to find node(say node1) which is marked + at max depth; 2) run dfs considering node1 as root and find max possible depth(say d) for a marked node; 3) ans = ceil(d/2) or simply (d + 1) / 2

227980372

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

can anyone tell me was this contest rated for newbies too , bcoz i don't see any change in my ratings ???

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

    Yes it is rated for people with rating under 1600. Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

    By the way I am also waiting for the rating changes(not my best div3).

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

Can someone please explain E. Block Sequence as dp states please and also suggest similar problems

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

    Let $$$dp[i]$$$ denote the minimum number of deletions for the suffix starting on the $$$i$$$-th element: $$$a[i..n]$$$. Base case will be $$$dp[n + 1] = 0$$$.

    For $$$dp[i]$$$, we can either delete or take it. If we delete it then $$$dp[i] = dp[i + 1] + 1$$$. If we take it, then the problem reduces to the suffix starting on the $$$j = (i + a[i] + 1)$$$-th element: $$$a[j..n]$$$. So $$$dp[i] = dp[i + a[i] + 1]$$$. We take the minimum.

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

Can anybody help me figure out why there is TLE in this solution (Problem D)?

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

    you're re-intitialising your 'facts' array for every test case. it would be the same every time.

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

      Why so? The prime factors would be different for every test case(In 'facts' I am storing the count of every prime factor, which has to be different for every test case). However, the prime factors would be the same up to 1e6 which I have already pre-computed.

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

    Ignoring TLE, your solution is wrong. For the test case $$$[7, 13]$$$, it outputs "YES" when it should be "NO".

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

      Yes, I figured out the reason for the wrong solution. I am checking up to n(size of the input array), while I should be doing it up to 1e6. However, still, I am getting TLE solution

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

        You're going to be doing that for every testcase though. So it'll require at least $$$2e9$$$ operations when $$$t = 2000$$$. You can use map/hashmap to keep count of the primes factors.

        Ignore below, it does work.

        Though even then, I'm not convinced you won't TLE in later testcases.

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

THIS CONTEST REALLY MADE ME TERRIFIED TO CONTINUE COMPETITVE PROGRAMMING

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

    Then the other ones in the future will make you motivated. Cheer up and keep going bro!

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

Your prayers for Gaza :(

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

It was a nice contest , i have a lot of silly mistakes , but still it was a quality contest

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

Where is my rating? How could you ignore a beautiful oily man with avatar girl!

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

What's up with the rating? System testing got completed hours ago?

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

why this round is unrated but the annnouncement said it's rated?

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

My current rating is 656, I participated in this round and solved 3 problems, as my rating is below 1600 this round should be rated for me, but when I check the graph in profile, it shows as unrated, can someone please explain why it is so, Am I missing some condition here?

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

    From my point of view and experience with codeforces I would say that the ratings are not ready yet.

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

    For every rated contest, until the ratings are given, the contest shows up in unrated tab.

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

I realised there can be only one or none prime factors greater than sqrt of that number!

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

The problem F of this round was a subproblem of this problem https://lightoj.com/problem/farthest-nodes-in-a-tree-ii. So finding diameter is a common problem and many of us know the solution for finding diameter. It was just finding the minimum distance among the maximum distances from those colored vertices. So if a diameter finding solution coincides with another person's solution how this will called a plag?

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

    Please check the above circumstances and reconsider the issue of plagiarism. It was not my fault.

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

Hello Codeforces, I had a message few minutes ago which says that "Your solution 227917247 for the problem 1881C significantly coincides with solutions 2020331050/227912904, dingD0ng/227917247" & "Your solution 227916835 for the problem 1881B significantly coincides with solutions 2020331050/227869923, dingD0ng/227916835" & "Your solution 227916500 for the problem 1881A significantly coincides with solutions 2020331050/227872918, dingD0ng/227916500". First of all I want to apologize as I was completely unaware of the rules and guidelines. I confirm that both of the accounts are mine and I made the same submissions during the "Codeforces Round #903(Div. 3)" contest for both of the accounts. Sorry for my action. This kind of act will never happen again in the upcoming days.

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

Hello Codeforces, I had a message few minutes ago which says that "Your solution 227917247 for the problem 1881C significantly coincides with solutions 2020331050/227912904, dingD0ng/227917247" & "Your solution 227916835 for the problem 1881B significantly coincides with solutions 2020331050/227869923, dingD0ng/227916835" & "Your solution 227916500 for the problem 1881A significantly coincides with solutions 2020331050/227872918, dingD0ng/227916500". First of all I want to apologize as I was completely unaware of the rules and guidelines. I confirm that both of the accounts are mine and I made the same submissions during the "Codeforces Round #903(Div. 3)" contest for both of the accounts. Sorry for my action. This kind of act will never happen again in the upcoming days.

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

Dear Codeforces Support Team,

I hope this message finds you well. I am writing to address a matter regarding my Codeforces account, specifically concerning the alleged code matching with multiple accounts. I would like to request a reevaluation of the situation and kindly ask for your understanding in this matter.

I understand that my solutions to certain problems have coincidentally matched with the following accounts: gjbbezzatihaiyaar/227857690, under_coverR/227890206, ambrosedean351/227901106, tester70/227901152, omarAsem/227902674, aman30/227902964, Xeroc/227905146, Sandi03/227905202, gaurav_4859/227905957, baburao_apte/227907553, aswer03/227910416, realshady105/227911556, mastercheif/227913841, jamesbonr123/227914312, abhi_0804/227918471, zozozrabbit/227921240, Bkapil1234/227922870, soumasingh41/227923532, legolas12/227924461.

I wish to clarify that the code matching with the account zozozrabbit/227921240 is due to a mistake on my part. This is alternative account that I use for practice, and I inadvertently submitted the same code from my original account, kumar.adit456/227921671, during a contest to avoid penalties. The matching of the code with these accounts was not intended and is purely coincidental.

I would like to emphasize that the similarity in the code is mere coincidental as i have a unique boilerplate that I commonly use for problem-solving. I did not engage in any form of plagiarism or misconduct intentionally. My intention has always been to uphold the integrity of the Codeforces platform and to learn and grow as a programmer.

I kindly request that you reconsider the situation and, if possible, reevaluate the matching of my code with the other accounts mentioned above. I hope you will understand that this was an unintended error and allow me to continue participating in contests and maintain my original rating on my main account, kumar.adit456/227921671.

I am committed to adhering to the rules and guidelines of Codeforces and ensuring such errors do not happen in the future. Your understanding and support in this matter would be greatly appreciated.

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

Dear Codeforces Team

I am writing to address a recent issue that has arisen on the Codeforces platform. My username on Codeforces is "Basecat," and I would like to clarify that I am also the owner of the account with the username "Bkapil1234."

During a recent contest, I made an unfortunate mistake where I accidentally submitted the same code on both my accounts, "Basecat" and "Bkapil1234." This has led to an accusation of code plagiarism from the account "Basecat." However, I want to emphasize that both accounts belong to me, and there was no intention to copy or plagiarize any code from other participants.

The match of solution to problem E with other users is a coincidence and i didn't intentionally copy the code from any other user.

I understand that the Codeforces community takes plagiarism and cheating very seriously, and I, as a Codeforces user, fully support the principles of fair competition and integrity. I would like to apologize for this accidental double submission, which has led to confusion and concern within the community.

I kindly request that you review the situation and consider my explanation. I hope that you can clear any misunderstandings and confirm that there was no malicious intent involved. I assure you that I am committed to upholding the highest standards of fairness and ethics on the Codeforces platform.

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

Hello Codeforces Suppot, Yesterday I got a message for the support team which goes:- Attention!

Your solution 227918471 for the problem 1881E significantly coincides with solutions gjbbezzatihaiyaar/227857690, under_coverR/227890206, ambrosedean351/227901106, tester70/227901152, omarAsem/227902674, aman30/227902964, Xeroc/227905146, Sandi03/227905202, gaurav_4859/227905957, baburao_apte/227907553, aswer03/227910416, realshady105/227911556, mastercheif/227913841, jamesbonr123/227914312, abhi_0804/227918471, zozozrabbit/227921240, kumar.adit456/227921671, Bkapil1234/227922870, soumasingh41/227923532, legolas12/227924461.

Firstly I want to apologize that such thing got up , but is a clear coincidence of code matching since the implementation of the E problem based on DP was so short and merely of 15 lines code having standard approach hence having a high probability of the approach being followed by others too And that too if the approach may closely ressemble with those of others the style of writing the code of mine is different(cna be clearly seen by seeing the submissions of the other account mentioned int the message above)

i know codeforces is a platform/community of coders which is against plagrism and I too support that the contest must be fair . hence I plea the codeforces support to kindly consider the plea(as a mere coincidence) . Hoping for a positive revert

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

@MikeMirzayanov

I received this message yesterday.

Attention!

Your solution 227895218 for the problem 1881F significantly coincides with solutions ShattajiT_/227895218, slim_vai/227902843. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

The problem F of this round was a subproblem of this problem https://lightoj.com/problem/farthest-nodes-in-a-tree-ii. Here is the solution of this problem https://pastebin.com/gQGWF7kG . My solution for this contest's problem F is quite similar, I just changed some conditions and took minimum of those maximum calculated distances. Here is the solution: https://codeforces.com/contest/1881/submission/227895218. So finding diameter is a common problem and many of us know the solution for finding diameter. It was just finding the minimum distance among the maximum distances from those colored vertices. So if a diameter finding solution coincides with another person's solution how this will called a plag? I participated in so many Codeforces's contests. I know the rules of violation. I didn't use ideone in contest time. Please check the above circumstances and reconsider the issue of plagiarism. I have been trying for so many days to improve my ratings and it will be frustrating for me if you revoke my rating for this contest. Count on it.

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

Waiting