natalina's blog

By natalina, 16 months ago, translation, In English

Hello, Codeforces!

On Jul/07/2023 17:35 (Moscow time) Codeforces Round 883 (Div. 3) will start.

You will be offered 8 problems, dedicated to the adventures of a restless mathematician, a programmer and just a funny character named Rudolf, and 2 hours 15 minutes to solve them. Problems have 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.

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. 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: vladmart, Sasha0738 and natalina.

We would like to thank:

  1. Vladosiya for coordinating the round.

  2. MikeMirzayanov for Polygon and Codeforces platforms.

  3. Sugar_fan for red testing.

  4. 74TrAkToR, zwezdinv,Sokol080808,senjougaharin, FEDIKUS, Lucina, vrintle for yellow testing.

  5. pavlekn, diskoteka, Phantom_Performer, bigDuck, Evirir for purple testing.

  6. KoT_OsKaR, HappyChau0v0, bugdone, Termii, t0rtik, Rudro25, O_E, jhorvat, sohelH for blue testing.

  7. ctraxxd, 666EGOR777, Guevara74, stefanbalaz2, jojonicho, hussein_auf for cyan testing.

Good luck!

UPD: Editorial is posted.

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

| Write comment?
»
16 months ago, # |
  Vote: I like it +48 Vote: I do not like it

Here before the "Hope to reach expert this round" comments.

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

    Hope to reach expert this round! (Tho there's no way an unrated jumps all the way to expert)

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

    Weak TestCase Contest

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

    Can you speak Chinese

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

      Yes of course. Whenever I get a Chinese lobby in cs, I always greet them with 嗨,台湾是最伟大的国. I always end up getting kicked for some inexplicable reason though... maybe I need to work on my accent.

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

Looking at the post, i think that i should clarify that i identify as a bi-color tester

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

As a tester, help Rudolf solve those problems!

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

    You missed an opportunity to name him Rudeus (Greyrat) and have back-to-back anime rounds :'(

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

    In the problem B, why this case is valid?

    XXX
    XXX
    XXX

    in the problem statement it is mentioned that

    Rudolf has a 3×3 field — the result of the completed game.

    how can this test be result of the Game where one player is making all moves?

    Also, All the sample tests are maded in that way that one player is making move after another.

    If it is valid test then I think it was better not to introduce this problem as 3 player Tic-Tac-Toe game.

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

      Exaclty! My solution was hacked with the input:- . X . . X . . X . How can this be a valid input in the case of a completed game, if only one person is making the moves?

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

      You can get hacked with a case that follows standard tic tac toe rules such as

      OOO XX. ...

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

        well, if we consider 3 player Tic-Tac-Toe Game, here 3rd player is not moving at all and 1st player is moving 3 times. How this test can be valid test?
        can anyone clarify that?

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

          In their defense example 5 is also a "Violation of the classic rules". so, they mean classic rules in a weird way where people can skip turns. But I definitely agree with your point of the game not following "classic rules" as promised is something they should have looked at or provided some clarification in the problem statement.

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

            "It has classic rules, except for the third player who plays with pluses" does this mean only the 3rd player has different rules such as skipping turns or having more turns ?

            If this interpretation is correct, then the samples make sense. But it contradicts XXX ... ... as a valid test case

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

      yea even my solution also got hacked, how can i know for which test case my solution is failing

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

      Yeah. A player should not win more than once (have more than one winning sequence of cells). Very weak test cases, lots of solutions were hacked.

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

As a Blue Tester, Hope you will enjoy the falling of snowflakes.

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

    E2 hard, have no idea

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

      Idea1: for n<=1e16 do brute force mean check for every k from 2 to 1e6. Then for 1e6+1 to 1e18 do Binary search. Cause here no of element fixed 1+k+k^2 as k^3 >1e18..

      Idea2: You can fixed length . length can be maximum 60-65. then for each length do binary search just..

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

        if you fix length to >50 you will TLE in Java. Brute force for 2 to 1e6 and then binary search with fixed length of ~6 is correct though.

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

    I liked the problem, but something odd happened in the evaluation. I passed E1 and E2 during the contest, but in the post-validation got TLE in E1. It's such an odd thing to pass E2 and fail E1, and it is due to the fact that TLE strictness vary during and after the contest. Of course, if I had noticed this TLE, it would have been easy to submit the same program that had succeeded for E2...

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

      Weak testcase contest. Very Disappointed. If you get TLE or WA during contest atleast one can get a chance to think of a better or correct solution. The hack that caused TLE for most accepted submissions (for E1) shows how weak the testcases were in this contest.

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

As a tester, this problemset has some amazing problems!

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

Hope to reach close to "Cyan" after the round.

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

In the second query of the second test case of D, why the answer is $$$3$$$? It think it is $$$2$$$: $$$(3, 5)$$$ and $$$(2, 7)$$$.

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

Hope to be a balanced difficult round.

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

artworks-LRr8ct-FQy6hay-Qpu-h-Wq-Jmw-t500x500-1

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

Now div3 is my only hope after my div2 performance went for a toss :(

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

    Can relate

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

    lol, ur hopes got shattered

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

      Yup. Due to my stupidity only. I kept solving F without trying C and D for 1.5 hours and before I knew, contest was over. Later I upsolved C and D in 10 minutes each. Got a good lesson though

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

In c everyone just copies tries code form online, please check plagiarism.

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

    bro wrong blog this is upcoming div3 :skull: and copying code from online is allowed if it was there before contest

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

First unrated div3

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

As a tester, please join this round :)

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

Although I was unrated for this game, I still wanted to participate

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

Enjoy each competitions and get rating

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

First time to participate in DIV.3 .(just dropped the blue name yesterday) everyone come on !

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

I hope to solve A,B,C in this contest (:

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

Red Purple Blue Testing... Are the problems salty?

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

Personal question:

I've just started with 400 rating am I eligible for this round?

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

Hope to reach expert this round

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

Am I the only one who hates DIV 3 ? :)

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

Don't know what I am going to do with that information

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

mine worst contest till yet... waiting for the rating update to see how much delta negative it will!!!

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

    You can use this extension to predict delta even during contest, it is pretty accurate

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

    Actually it was my first contest...can you please tell me when will the ratings be updated?

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

      You can probably expect ratings to be updated within the next 24 hours.

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

So Rudolf and Rudolph are like brothers?

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

me after previous contest:

-hello, Specialist !

me after today contest:

-goodbye, Specialist !

i'm tooo slow)

Thank you for the amazing contest! I really liked it!

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

TIL I am not that good at geometry

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

was E2 a double binary search problem , first on k and second on the possible power of k ??

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

    I used quadratic formula to solve for potential cubes and then precomputed possible powers until 10.

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

      pretty neat , but was it intuition or somewhat a proof that we can achieve our output uptill 10 ?

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

        Not exactly, sorry for the confusion. You can also have powers larger than 10, I think. I just brute-forced to get all possible candidates that have powers less than 10. This makes the look-up for other potential values of k faster

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

          can you help in my E2 submission 212790410

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

            Product res can exceed limits of unsigned long long

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

              How can I solve that problem?

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

                I did something like this in 212650593

                ll calc(ll b, ll bits){
                	ll ans = 1;
                	for(ll i = 1; i < bits; i++){
                		if(ans * ((double) b) > 1e18)	return 1e18 + 1;
                		ans = ans * b + 1;
                	}
                	return ans;
                }
                
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Didn't Solve it.. But i think we don't need to do a binary search over k's powers we can check all of them "aka. brute force " as maximum possible power to have is p = 63 for k = 2 and p decreases with any increasement in k .

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

      was thinking the same that complexity could be max around O(log sqrt(N)* 63) in worst case if n is 10^18 and k is 2, kept on messing and crashing my compiler :'(

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

    So the goal of the problem is to find some k and l such that k^0 + k^1 .. k^l = n and l>=2. Notice that l can be at most around 63 ( when k is 2 ), and therefore, you can iterate on l and binary search on k, yielding a log(n) solution with a moderately large constant factor.

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

    2^64 ~ 3^41 ~ 10^19 ~ 250^8 ~ 7000^5 ...

    I brute forced the solutions for the first 1e5 values. For values above 1e5, I did 2 things.

    First: Fix the length of the formula between length 3 to 5.

    Second: After assuming a certain length is correct, lets say 4, you know the formula should look like this: k^0 + k^1 + k^2 + k^3 = n

    Since n is known, you can binary search for a k.

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

Can anyone help me why this submission of mine for the problem F is giving wrong answer? I think my logic is correct, maybe somewhere I am doing mistake with i/0.

https://codeforces.net/contest/1846/submission/212691145

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

Kinda MathForces round but Enjoyed solving A ~ E1 :D

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

can someone tell me how tf am i getting a WA test 5 on D where do I mess up Submission

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

    nvm i was using setprecision wrong. i will get negative delta for sure

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

My code was rounding off answer of problem D to next number can anybody help

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

    set precision to the answer.

    for c++, add this before printing answer "cout << setprecision(8) << fixed;"

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

      I have tried then also same problem it was fine for other but test case 4 it rounded to 200000

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

        Then maybe your logic is not correct. You can refer to my solution

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

          You subtracted area of small triangle from big. I solved by using area of rhombus. Let me try your method.

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

        Mine too rounded to 200000 but it gave correct answer. My Solution -> 212673768

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

          My answer also got accepted i should have submitted it during the contest 212710542 Thanks everyone for help

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

Hey can anybody share link resources for solving problems related to decimal points (faced difficulty today)!!

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

    same

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

    You misunderstood problem D. It wants you to be precise to the 6th decimal place. If you google "C++ float precision" or "C++ double precision" then you find out that both datatypes are accurate enough. Float is precise to the 7th decimal while double is precise to the 15th decimal.

    If you ever find yourself in the need of bigger datatypes, you may want to check out this: https://cp-algorithms.com/algebra/big-integer.html

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

.

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

E: n is valid if there exist k>=2, r>=2 such that 1+k+k^2+...+k^r==n. Since k^r<n we have r<log(n), so we can check for all values of r and find k by binary search, we can solve a single case in O(log(n)^3).

F: We remove no object for 1st and 2nd queries, and the mimic must change it's type during first 2 queries, so there will be exactly one t that the number of occurence of type t increased. Then we can remove all objects with type other than t in the 3rd query, then the types of all objects will be same, and mimic will not be removed. Then the mimic will change its type in the 4-th or 5-th query and we can find it easily.

G: We can build a graph with 2^n nodes (representing every possible subset of symptoms) and 2^n*m edges using bitmask, and solve the problem by dijkstra shortest path.

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

    optimization of E that I overlooked during the contest but turned out to be valid: The only possible candidate for $$$k$$$ is $$$\lfloor (n)^{(1/r)} \rfloor$$$. This is due to the fact that $$$x^r < (x^{(r+1)}-1)/(x-1) < (x+1)^r$$$. Look at the binomial expansions to find out why.

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

      unfortunately it is difficult to directly use this because of double value precision problems: my wrong code

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

        You can always adjust afterwards just like how you find the value of $$$\lfloor \sqrt x\rfloor$$$, just double check using values of $$$k^r$$$.

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

          it can exceed MAX long long

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

            Dude, trust me, I know that already. And also I know that if $$$k^r$$$ is safely contained in long long then $$$(k^{(r+1)}-1)/(k-1)$$$ is safely contained in unsigned long long as it is smaller than $$$2k^r$$$.

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

              not what is was saying. $$$(k+1) ^r $$$ can exceed max long long even though $$$k^r$$$ does not

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

                well then you can check if it exceeds the limit very easily? just use naive multiplication and check overflow using division in the process

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

        kingpin199 why do you use int instead of long long in your code?

        I also invented chromate00's optimization and implemented it https://codeforces.net/contest/1846/submission/212834179

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

          im defining int as long long int in the beginning of my code. im suprised why urs passes and mine dosent, any idea>

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

            Test: #13 test consists of large numbers

            I think the problem with types or overflow

            You can try to change double to long double

            Or generate a test with large numbers for debugging

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

      That's what I tried during the contest, even though I was just as sure that this approach is going to get hacked (unsurprisingly, it did), my submission: 212667440. Naively switching to long double doesn't help as well, is there some other way to make this solution work?

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

        well the safest approach in contest would be sacrificing a log factor and using naive multiplication + int128 (GCC) (of course you would need to adjust the value of the k-th root)

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

    In problem G, is it true that every medicine can be used multiple times? If not, how do you prevent multiple uses?

    • »
      »
      »
      16 months ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      That's why we're using dijkstra, do you ever comeback to the same node in dijkstra bfs ?? Use that analogy here, take days as edge weights

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

      there is no ban in using one medicine multiple times, so you can use it multiple times, but I think it doesn't make sense

      "how do you prevent multiple uses?" — in our graph we use edges as medicine(at least I used it as medicine) when u are doing dijkstra it is obvious that you will not use one edge multiple times, so we use one medicine at least once.

      my submission 212707666

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

        Am I correct that there are multiple edges in a graph associated with the same medicine? If that is the case and multiple use of the same medicine is forbidden then all such edges must be removed from a graph once we use one of those edges. It is not specified explicitly but examples suggest that every medicine on the path must be unique.

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

          I think in terms of logic choosing twice same medicine is not efficient, I can't prove how exactly dijkstra will choose unique medicines, but by definition dijkstra choose always shortest path, so it should choose unique medicines

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

        why downvotes ? am I wrong in something?

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

    I implement F the same idea as yours but getting WA. Any idea why?

    212701178

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

      You should output the index of the mimic directly after find it, instead of removing other objects and output 1.

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

    wait why is E $$$O(log^3(n))$$$ not $$$O(log^2(n))$$$?

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

      there are logn degrees of the polynomial, then you binary search leading to a second log, and your check function is also log

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

wtf was d?

»
16 months ago, # |
Rev. 6   Vote: I like it -11 Vote: I do not like it

good questions but the problem statements can be improved. All of them are so long AND confusing.

It's like a reading exam at this point.

G is literally dijkstra. There's nothing algorithmic about the last problem in this contest. The hard part was READING and parsing the bits. Wtf

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

I really liked G, excellent problem. E2 is also very nice.

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

    what did you like about these problems? G is very obvious and E2 is just stupid math.

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

      Nothing is obvious / standard in a div3/div4 round. People here are learning these topics. How could you say bit-mask + dijkstra problem is an obvious one for div 3? It was indeed a great problem

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

Thanks for preparing this amazing contest! I am delighted that I got 1st rank (excluding unofficial) before the hacking phase.

The last problem G is a masterpiece. It is picky to think about Dijkstra. But very good problem to show that modeling to graph can be good way to solve the problem.

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

The contest was good, but can testers do something about all these. telegrams, whatapp groups, and youtube channels uploaded the solutions before the end of the contest. I have seen some submissions that were directly copied from youtube uploads, and still no action was taken on them :(

  • »
    »
    16 months ago, # ^ |
    Rev. 4   Vote: I like it -15 Vote: I do not like it

    What do you think Codeforces can do? It happens every contest in Leetcode as well.

    This is more like an Indian problem that spreads everywhere in my opinion. There's nothing Codeforces or Leetcode can do if most of the Indian users lack integrity and consideration for other people.

    TLDR: Indians lack skills and talents so they cheat (low rating overall). Blame India for producing top cheaters instead of top geniuses in algorithm

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

      lgta H apki Indians se kuchha jayda hi dusmni h

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

      I’m indian too but gotta agree with you here :/

      Know many cheaters personally as well……. But still you shouldn’t equate it to a lack of skill among indians (ik i’m still a newbie but there are many genuine candidate masters and red coders from india as well)

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

      it's too racist.

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

    never mind,we solve this tasks for increasing our skill,not just for the points

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

what is wrong with this solution for C ? I found points and penalty for every contestant then iterated over them while incrementing cnt if anyone has better . Others seemed to have done the same

https://codeforces.net/contest/1846/submission/212638737

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

    I'm not experienced in Java, sorry, but I'm wondering if it's because hashmaps can't store multiple copies of the same object. Some participants can have the same scores and penalty.

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

      I think i used hm as variable name of arraylist which is a vector . It's okay , thanks for helping

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

    You are adding the same penalty multiple times.

    time+=(ar[j]+time); should be time+=sum

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

I tried to hack my C but I received an Unexpected Verdict. It seems that there is a solution on Polygon that use int but it was marked as AC.

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

nice contest (especially problem G), unfortunately spent an hour searching formula for D

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

question C runined the contest for me , i got the vector of pairs of {poins,penalty} then i thought i would need to sort it accordingly to find the position of first person , but god i don't know but i am not able to sort it accordinly with comparator functions , it became a mess , spent half time of contest on C , then in last 10 minutes it striked me that i do not need to sort , just count how many elements greater than first , damn could have got <2k rank but next time ig

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

Screencast of the round, I tried to explain my ideas, if someone needs that

https://www.youtube.com/watch?v=dvNKBeTtlY4

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

today's just not my day. started the contest 5 mins late and just failing on E2 miserably, just being very low in ranking :(

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

Managed to figure out right solution for D in the last minute, but forgot to cout << fixed; cout.precision(6); and got wrong submission. so sad :(

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

For those trying a binary search solution for E2, you need to set the upper bound appropriately so you do not overflow. (WA on test 7 or WA on test 11, etc)

Accepted code

WA code

Also, anyone know why this python code TLEs?

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

    change val to return (k**(it+1))//(k-1)

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

      Unfortunately, the improved code still TLE's. Probably a case of python being slow?

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

        Yeah, maybe. I had to use some weird brute force to pass instead of doing binary search.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    for i in range(2, 64):
    

    Had the same problem in Java, where searching for >52 range would TLE me. You don't have to search in such a big range if you precalculate some solutions.

    2^64 ~ 3^41 ~ 10^19 ~ 250^8 ~ 7000^5

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

I participated in this contest and I get TL in the interactive problem (F). I cannot understand why. Is the time limit too strict? Could someone please check my solution and explain?

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

Can someone please explain why 212706726 passes and 212706596 does not for E2.They're exactly the same code.

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

how to solve E1. I thought if a number can expressed as 1+a+a*a+a^3...upto n where a is an integer and n is an integer. and got stuck after.. Is this correct way to think or is it wrong.Thanks

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

    its correct. you know that k >= 2 from problem constrains and also that every graph of the described type must have at least 1 + k + k^2 nodes. You know everything, just precompute those values going up to 1 + k + k^2 + ... + k^m so that the total sum <= 1e6 and store them. If the given n is among those values ans = YES else NO.

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

i really liked the geometry behind problem d

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

is there a hack for this solution of problem G?

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

i did bruteforce in e2 try to hack my sol if you can :-https://codeforces.net/contest/1846/submission/212718777

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

Can anyone tell me why my solution for E2 gives TLE in c++17. Got ac using c++20.

c++17 submission

c++20 submission

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

    Since you're using long long instead of int in your code . It's getting faster execution with C++20(64bit) . Always use this compiler when you're working with long long . Hope it helps .

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

E2 was a nice question on binary search . Nice blend of Maths and Binary Search .

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

    I guess, I have an easier/optimal solution for E2:

    Link to my Submission : 212747366

    It runs in O(k*log(k)) where k is 60.

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

Can someone hack this 212683099 submission for G, it runs 100 iterations, and it seems to be enough, I don't know any test case that can hack it.

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

What is the importance of first 2 lines in the below python code for A question. Why am I getting T.L.E when trying to submit without the first 2 lines:

212712911

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

What is the Hack case in problem B?? So many Hacks!!!

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

    Not only for B. There are so many hacks, afraid...

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

What is wrong with my Problem C code ;) https://codeforces.net/contest/1846/submission/212661976

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

In C today the (overflow test) in the contest wasn't provided and a lot of people will get WA because of it. How this basic test not handled to aware us :(

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

    OMG...

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

      Can anyone hack my C now?Just overflow test

      UPD:it has already been hacked. Thanks

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

Hope to reach newbie this round.

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

Terribly weak tests for problem B

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

Why it was a great Div3 round :

  • Problem A & B : Naah, they don't teach a lot

  • Problem C : Teaches use of custom comparators

  • Problem D : Teaches to handle precision in floating point numbers and some geometry

  • Problem E : You've to be prepared for future "Math-forces" rounds to grow as a competitive programmer.

Problem F : Simple idea but teaches how to interact with the judge

Problem G : Shows the power of dijkstra and also bitmasks with it

Overall, great round covering so many topics that are pretty relevant to div 3. Congratulations to the authors.

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

    if u use python Problem D only teaches basic geometry

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

finally expert.... yayayy

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

    Good JOB my friend! Try to keep this rate and reach candidate then ;)

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

I have made a video editorial from A to E2 do check that out... https://www.youtube.com/watch?v=0paMs9FV_nk

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

Is there some problem with the validator of problem B, as many of the hacked solutions missed the case where more than one winner is possible, whereas it is clearly mentioned in the problem that multiple players cannot win the game.

Is this test valid?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really like this round. Nice problems

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

Hackforces anyone!?

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

Almost got hacked for C, my first submission was just using ints to keep track of the penalty which passed pretests. But then I remembered getting hacked for problems with calculations in the 100000^2 range and resubmitted with long longs shortly after.

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

what is the significance of trusted participants?

Does it affect rating by any way?

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

    trusted participants for div3 are the one whose rating is below 1600

    yes, while rating is considered only the trusted participants from standings are considered

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

      Wrong. Did you even read the blog?

      To qualify as a trusted participant of the third division and be shown in the official leaderboard, 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.

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

    Being a trusted participant does not affect your rating. Your rating gets updated if you have $$$< 1600$$$ rating regardless of if you're trusted or not.

    Being a trusted participant only affects if you're shown on the "official" leaderboard.

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

I faced an issue with problem C:

This was what worked as a custom compare function:

static bool compare(pair<int,pair<int,long long int>> p1, pair<int,pair<int,long long int>> p2){
    if(p1.second.first < p2.second.first) return true;
    else{
        if(p1.second.first==p2.second.first){
            if(p1.second.second <= p2.second.second) return false;
            else return true;
        }
        else return false;
    }
}

Whereas this one didn't work though they do the absolute same thing:

static bool compare(pair<int,pair<int,long long int>> p1, pair<int,pair<int,long long int>> p2){
    if(p1.second.first < p2.second.first) return true;
    else{
        if(p1.second.first==p2.second.first){
            if(p1.second.second < p2.second.second) return false;
            else return true;
        }
        else return false;
    }
}

I later discovered this after the contest was over, I was just trying to sort the values based off in increasing points in descending and same point value then ascending order for penalty here. But this one statement as if p1.second.second < p2.second.second didn't let me pass the time constraint even though essentially they have the same time complexity as using this as an if statement p1.second.second <= p2.second.second, essentially the complexity of my program is O(n*m*log(m)) and it should've passed through regardless but idk why it didn't...... you can check my submissions the older one didn't use long long int but I would've figured out regardless if I got WA but the TLE made me rethink my choice in logic and that defeated my morale hugely in the contest.... I wasn't able to do the other problems as I couldn't find an actual mistake here.... The test cases timings were too tight otherwise I really don't know what my mistake was in this scenario....

Here was my in-contest submission: 212701525

Here was what worked after it: 212708923

You can see there is almost no difference between the both except for the < and <= logic wise except for changing the penalty into long long int.... Please guys upvote and get it to the attention of the testers it if this was faced by others, because of this I couldn't perform as good as I potentially could've... as my logic was completely accurate but still failed regardless...

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

    Or you could have just used negative amount of solved problems and positive penalties for all the participants, so the standard sort would have worked just as well.

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

    Two problems here:

    1. If pen overflows then it becomes negative which will give a verdict of WA. Submission
    2. As for TLE, check out this amazing blog and also it's amazing comments. Can't explain better than this.
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

From the Russian version of this round's announcement:

We tried to create decent tests and will also be upset if many solutions are going to fail on hacks after the end of the round.

After this is over, the creators of the round are going to be real sad (basically swimming in their own tears), poor bastards.

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

Too many hacks...loving that hacks section..

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

Could somebody help me figure out why my output format is wrong for part F? Submission: 212739492

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

If someone could look at my submission of F 212740665. Why does it give IDLENESS error on the 2. test? I really appreciate it

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

eh another failure contest, terrible pretests for B, really long and confusing statements, B isnt really suitable problem for this platform, this cringey shit should be unrated

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

    Sounds like someone did poorly

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

      nah just the B part, its not even suitable for this platform, lmfao put the dumb b away, if u gon say u solved F i can say i solved E2 too? i left after E2 and would solve G now that i read it

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

        Dont make excuses for your own performance. Obviously, other people were able to perform well. Also, I fail to find what is so confusing about problem B, it is just tic tac toe with 3 people? Find if any of the 3 symbols make a straight line..

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

          nope not at all excuses, as i said it really wasnt a problem u would put on this platform, its not competitive programming at all, just some edge case shit which u could miss, thats what happened and thats it, and to be fair no, ACDE1E2 is a much better perf than ABCDE1

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

I successfully did 6 hacking attempts and 1 unsuccessful attempt on problem B. However, I do not know why but all my successful hacking attempts have been removed and it shows only the one unsuccessful hack. Can someone tell me why? This is the testcase I used to hack Problem B

1

OX.

.X.

OX.

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

    Same happened to me, I did 50 successful hacking attempts on E1 and now they all just disappeared. Seems to me that authors have added a few testcases in the pretests after the end of the round. I can't explain this phenomenon in other way..

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

      Ikr! It took me more than a hour doing so. Adding testcases is fine as this would ensure correctness of all submissions but bruh why to take credit from all those who wasted their precious time finding those corner cases which probably they failed to notice in the first place.

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

    may be someone could have hacked that solution, just before you

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

Such a bad statements.

problem C:

"It will be assumed that in case of a tie in points and penalty, Rudolf will take the best place."

This appeared in the last sentence of the problem, the author at least should've described this above with "in case of tie-in points the one with the lower penalty wins"

as there is no continuation for it, I assumed there is no tie-in penalty. Maybe some blame on me for not reading the whole problem but it's Div3C and the info should've appeared above

no pretest for it or the long long case ):

Problem E is hard to determine what you want exactly.

it took me some time just to understand the problem, I thought 1 + k then whatever

but 1 + k + k * k then whatever? it took me some time to understand ): It's not well explained

even F and A need some improvements I see there are a lot of testers, did they all approve on these statements!!

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

    Yeah A's statement was terrible. How did 10k people understand it in the first 10min?

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

      What was the problem with A's statement? Just wanna know.

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

        It was just very unclear to me. Maybe I'm just stupid but I wasn't able to figure out which direction the ropes went in. Eventually I just guessed something that vaguely made sense and got AC.

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

          Do you understand how ropes work in real life? If the candy is connected to a nail at height $$$h$$$ with a rope of length $$$l$$$, the height of the candy must be in the interval $$$[h - l, h + l]$$$. Every nail and rope gives one of these intervals in which the candy must lie. The position of the candy must satisfy all of these intervals and because the candy is affected by gravity, it must lie at the lowest allowed point.

          Does this make sense to you?

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

            It makes sense, and I did think of this as I was trying to solve A, but then I ignored it because I figured, "It's a div3a, it's gotta be something really simple". In hindsight, it actually was, and it was entirely my fault for failing to interpret the description. I take back my original statement.

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

      By guessing

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

Am I the only one who did not use long long in C and got hacked? Like There should be test cases of long long in the pretests, or I don't know my code miraculously worked on them even though everything was int.

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

In problem C the given note for test case 4 is wrong as Rudolf will be able to solve all 3 questions. Am I right?

  • »
    »
    16 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    3 2 27
    8 9
    10 7
    10 8
    

    are you talking about this test case? If so then there are 2 questions, and the note for this is correct.

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

How to solve D? Actually I can not figure out how to calculate the area of the overlapping portion of a triangle. Yes, height can be calculated easily (difference between previous triangle height and current triangle height) But what's about the base? How to come up with a formula for that?

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

hackforces ngl

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

The pretest of this competion is too weak, not longlong, algorithm analysis errors can pass the pretest

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

    I agree with you (since I got my C hacked, not much painful since it was unrated) but there is something I would like to add (my opinions), I think that the problem setters were new, They had less experience of doing this job. But they made good problems (not all, did not like A, B), but of course a problem setter need more than just creating a good problem. Creating test cases is also part of it (which I think is a hard job), But this was there first time (I think) so they will get experience from this and I hope they will create their next round in a better way. Thank you for the contest.

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

      I say this is not malicious, because I use a trumpet, just hope that the questioner can create more rigorous data in the future, C does not have longlong data even if it is counted, B question and even the wrong algorithm can pass pretest, of course, it is undeniable that I think the quality of this topic is good, but pretest is difficult to say

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

    Yes, so true. My code for C was hacked as I used int instead of long long. If the pretests had one of that case, my delta would have been positive. Never thought that there would be a contest with pretests not having overflow case.

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

I participated in div 3 yesterday but i have received no rating so far. Can anyone help? It shows the contest in unrated section for me but it was definitely rated.

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

    There is a 12 hour open hacking phase that ends in an hour and a half, then it takes a few hours after that for the rating to update.

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

      Could you please explain what this hacking thing on codeforces is? I couldnt find any answers on google. I am very new to all this.

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

        Sure, look here: https://codeforces.net/blog/entry/6249

        In short, the open hacking phase is the (12-hour) period after some contests where people try to break other's solutions for more points. If your solution is absolutely correct, you won't have to worry about being hacked. On the other hand, is there is a subtle bug in the program, someone might want to exploit it to break your program for extra points.

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

          Oh my god! So other people can exploit my code too. So can i also hack other people's code when the contest gets over?

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

            It depends on the contest but for this one, you have only 20 mins left to try.

            Also note that if you unsuccessfully hack the code there might be a penalty, so only do it if you're sure the defender's code is truly exploitable.

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

              There are no penalty for unsuccesfulls hacks neither extra points for succesfulls ones

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

Too weak testdata. How can 4000 codes be hacked in one round?

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

The hack mechanism became an excuse for the proposer to perfunctorily provide data, so this round became hackforces.

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

Why my submission https://codeforces.net/contest/1846/submission/212766857 for E2 is giving TLE. Can anyone tell what could be the reason and how can I resolve it.Thanks

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

When the final testing will Start?

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

Can someone clarify why it is allowed to have less than 3 players for the B problem. The problem statement states "Either exactly one of the three players won or it ended in a draw", which implies 3 players every game.

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

    i have a feeling that "draw" doesn't always mean draw. it might also means either the game ends prematurely or the sequence of playing is arbitrary which means there is a chance a player doesn't get the chance to play

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

      They mention classic rules in the question, so sequence of playing cannot be arbitrary.

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

        The testcases don't fit the statement. I pointed that out when testing, but it went mostly ignored (except for the fact that more example testcases have been added.)

        A part of my feedback:

        "No complete game can ever have more than 2 dots. Some testcases do, though.

        Improvement options: Personally, I would remove all games from the test cases that have more than 2 empty cells. If you feel lazy, you could also change the problem description, so that it is clear some games have not been finished. Maybe add an example that shows a mostly empty board in that case."

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

Am I the only one that thought he had his best div3 contest just to get hacked on 3 problems xD?

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

    Feel for you...you were 10 rating short of actually escaping the contest

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

      The predictor after the contest said I would get +50 now -100 xD

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

        Can you provide link to that predictor?

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

          It's the codeforces carrot extension on chrome

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

Did anyone use bitmask dp for G? I understood the Dijkstra approach

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

    Problem G hasn't got the precondiction of using bitmask dp, cause the order of using medicine does affect the result. And if you multiply the number of medicine for twice, then work the dp, you'll find you cannot control whether some medicine is used for exatly one time.

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

The following testcase is not possible in tic-tac-toe game and in problem(C) it says it has classic rules.

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

In the problem B, why this case is valid?

XXX XXX XXX

in the problem statement it is mentioned that

Rudolf has a 3×3 field — the result of the completed game.

how can this test be result of the Game where one player is making all moves?

Also, All the sample tests are maded in that way that one player is making move after another.

If it is valid test then I think it was better not to introduce this problem as 3 player Tic-Tac-Toe gam

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

    Yes. The even mentioned one of the three players in the problem statement.

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

In the problem C, a lot of people get hacked by testcase 10 ( including me ), But Why ? My Problem C Code

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

    overflow

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1
    20 1 200000
    

    ~Give input 20 "1"s and your code gives 11 as output. but the output should be 1.

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

can someone help me with this submission, I don't know what I'm doing wrong here. 212786771

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

    res = (res*x)%p sometimes can't detect overflow. I have a problem with overflow in E2 too and still don't know how I can fix it.

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

      already did the overflow check before every multiplication though. ill put a check on sum as well

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

So amazing that my problem C is hacked because I wrote int,not long long.

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

I cannot possibly believe that the setters put no testcase against integer overflow in problem C. At this point we might just as well have no tests at all during the contests and let everything be decided by hack testcases. Whether this be a terrible oversight by the authors or a conscious decision to join in with the recent trend of pointlessly weak pretests, I want to say (having being robbed of at least 200 rating points by dumb FSTs) that this ruins the fun for everyone and, in my opinion, has made the quality of codeforces rounds plummet in the last few months.

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

    i think if you want to get higher rating, you should be able to estimate that 2*1e5 * 1e6 > int

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

      Which is why I said it was a dumb mistake, which should have cost me 10 minutes of penalty, not +144 instead of +215 rating points. It has never been the point of competitive programming not to let the contestants have feedback on their solution.

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

My submission of problem E1 got hacked because of tle when I had submitted in C++ 20, but when I made the same submission in C++ 14 it got accepted. Please look into this, as many people using C++ 14 would have their submissions accepted. Submission- 212621824

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

G is definitely a good problem

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

Layman trick for E2 I found right after contest ended ! —

For i <= 10^6: brute force similar to E1.
For 10^ < i < 10^9: it can only branch out one time before the result goes over 10^18

So the geometric series can only be of the form 1 + i + i^2 = n (remaining terms would make the sum exceed the constraint on n)
Now it remains to find an i for which 1 + i + i^2 == n. and we have to do it quickly. so after modifying the above equation it becomes (n-1) = i*(i+1) which can be evaluated quickly by taking square root of n-1, say k and checking if k*(k+1) is equal to n-1

solution link — https://codeforces.net/contest/1846/submission/212697488

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

    did same but got tle pls check this solution https://codeforces.net/contest/1846/submission/212799364

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

      Check the dp part of my solution You are probably TLE-ing for cases where n is below 10^6
      In my solution I have precomputed all the valid results for these

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

    my code failed for 1048575 . OJ says answer is yes. But it is greater than 10^6 . it's root is 1023. Multiplying it 1024 does not give n-1 .

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

      the sqrt trick applies to 10^6 < i < 10^9
      and for these cases n would have to be close to 10^12 (1 + 10^6 + 10^12)

      n=1048575 is added by i=2 which my solution is checking by brute force

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

Can someone please make me understand this: in E2 the constraint on N was 1e18 even if I get O(1) approach for each value of N then also the solution would be O(N) and the time limit asks us to find a solution in multiple of 2*1e6 (because 1 second mean 1e6 operations) so how is the solution possible ?

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

    how will be O(N) if you are doing it in O(1) it will just be O(TC)

»
16 months ago, # |
  Vote: I like it -15 Vote: I do not like it

this is not fair, my C got accepted in contest time but in system testing it got failed. This is not my error.

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

    Your code was not correct for all testcases

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

      It's failed due to integer overflow, but in contest time it got accepted

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

        System testing includes running your code on some new testcases, it is your duty to make sure that integer overflow don't happen given the constraints.It's frustrating but happens with most of us sometime.

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

          It's too frustrating, like if we get this wrong in contest time itself, then may be we correct it. But let it go. Thanks

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

During the competition I submitted the first 4 problems and got green on them but today two of them are red. Can somebody please help me understand what's going on? I am really confused right now

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

    System testing is going on. All submissions are being rejudged based on successful hacks testcases. But as I can see, your solution for problem C has failed the system test and D one is waiting to be judged.

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

wow, amazing FST round. Some problem's pretest are weakly.I hope you will pay attention to strengthening pretest in your next round.

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

weak pretest make this round worse

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

7.7:rank:4000 7.8:rank:2000

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

WeakTestContest

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

The main character clearly has an identity crisis — sometimes he's Rudolf, and then other times he's Rudolph. :)

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

Is there a way to challenge a problem? Question B clearly states that the game follows the classical rules but with 3 people instead of 2 yet some test cases have the same player winning multiple times. This never happens in regular tic tac toe. With this my code did not work:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) {
        vector<string> vc;
        bool ans=0;
        for (int i=0; i<3; i++){
            string s; cin >> s;
            vc.push_back(s);
        }
        for (int i=0; i<3; i++){
            if (vc[i][0]==vc[i][1] && vc[i][1]==vc[i][2] && vc[i][0]!='.'){
                ans=1; cout << vc[i][0]<< endl; break;
            }
            if (vc[0][i]==vc[1][i] && vc[1][i]==vc[2][i] && vc[0][i]!='.'){
                ans=1; cout << vc[0][i] << endl; break;
            }
        }
        if (vc[0][0]==vc[1][1] && vc[1][1]==vc[2][2] && vc[0][0]!='.'){
            ans=1; cout << vc[0][0] <<endl;
        }
        if (vc[0][2]==vc[1][1] && vc[1][1]==vc[2][0] && vc[0][2]!='.'){
            ans=1; cout << vc[0][2] << endl;
        }
        if (!ans) cout << "DRAW\n";
    }
}

If I had put return statements in each if statement this would have been right. This question was worded absolutely horribly.

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

    But even in samples was an example of game, which can't be obtained by standard way.

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

Where are the rating changes

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

Weak testcases ruining my rating

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

Does anyone know what B test 25 line 52 is? My solution was accepted during contest but now its rejected and I can't see what's wrong

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

    You made the same mistake as me my friend. It turns out that a player can have multiple "3 in a rows" in the table. You must have had two outputs for one test.

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

      oh man thats really unlucky how were we supposed to know that was a valid input LOL i assumed all inputs were valid tictactoe boards

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

I wonder if they made the test data using their feet.

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

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

why my submission is giving TLE on updated testcase. submission:https://codeforces.net/contest/1846/submission/212665339, please help

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

    Because of Python

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

      This is so bad, if the setters would have given a testcase, i would have coded in C++, such an awful contest Edit: I modified taking input by sys.stdin.readline() to make it faster and got Accepted.

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

        This is not the problemsetters' fault, you should be aware that Python is much slower than C++.

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

          You did not use fast input. Either way, it will also get TLE with fast input, I tried it. In Python, Sometimes an optimisation from O(N log N) to O(N) can be the difference between TLE and AC

          935ms / 1s isnt a good runtime for an accepted solution. It can get TLE sometimes when submitting

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

So, I got WA30 because of integer overflow. The way to easily fix this is adding __int128 but for some reason it was not available to do so (when I submitted my code in test system it got CE). If someone knows which compiler to choose to avoid those issues, let me know

To fix the issues with overflow I simply used the following convenient functions: __builtin_smulll_overflow, __builtin_saddll_overflow

Here is how I used it to pass tests (after my initial solution failed miserably)

    auto check = [&] (int M, int deg) {
        int pM = 1;
        int sum = 1;
        for (int i = 1; i <= deg; ++i) {
            if (__builtin_smulll_overflow(pM, M, &pM) || __builtin_saddll_overflow(sum, pM, &sum)) {
                return false;
            }
            if (sum >= n) return false;
        }
        return true;
    };

Hope it helps someone!

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

My E1 solution didn't give TLE on C++ 20 but it gave TLE on C++ 17 which I submited during the contest, what is the reason? Can anything be done now :(

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

    Can code be rejudged for C++ 20 compiler?

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

    Using long long with a 32 bit compiler will be slower than with a 64 bit compiler, if you had selected C++17 (64bit) it would probably have been accepted.

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

      should not even then it should be slower by 2 times only , c++ 20 code runs at 600 ms while c++ 17 gives TLE at 2000ms , which is more than 3 times difference

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

        should not even then it should be slower by 2 times only

        I don't know how much slower it "should" be, where did you get the 2x from? It depends how much of the operations your program does are on long long, and the operations themselves of course make a difference, whether it's loading/multiplying/etc.

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

Just wondering, when will the editorial be released?

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

Idk whats going on with this contest, after hacking phase already over and final standings were released, it automatically changed to wrong answer in E1, can they change the test cases or what not even after the final standings?

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

    That means your solution E1 was hacked

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

      After the hacking phase was over it still showed accepted, abrupty after some hours now it shows wrong answer on test 10 ,not even hacked

      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it
        • During system testing, Hack test cases are merged with the system's and the solutions are re-evaluated.
        • That means, someone made up a test case and hacked someone's solution. And your solution gives wrong answer to that testcase as well.
        • Hence, failed in system test.
»
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

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

There E2 limitations and overflowing got me some headache =)))

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

 Looks like I get to do another div3 lol

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

Hope my next contest will be greater ._.

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

Why Wrong answer on test 31 in E2?

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

    I am pretty sure that it happens due to floating point arithmetics. I would rather recommend you to come up with the approach that doesn't use it (but I do believe that there is a way to find a workaround).

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

    Try to test numbers manually, finding acceptable k and max_power.

    64000008000003
    64000008000001
    9999799901001001
    9999799901001000
    9999999900000001
    9999799901001002
    

    Finally I wrote a script to generate all acceptable N numbers. That file weights 17GB and all my tests run about 4 minutes:) But I receive AC today after debugging a rare uint64 overflow case in C++ solution while the same PyPy solution gets TL.

    Good luck!

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

can someone please explain the solution and thought process behind problem G, I find it hard to imagine how we will construct the graph and please link some practice problems based on Dijkstra from CF.

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

    There are at most 2^10 = 1024 different symptom combinations (states). You start with your initial symptoms, apply all possible medicines and see which different symptom states you can get to in one ‘move’. Put all these new states in a priority queue and pick the next state to explore as the state from the queue that a) you have not explored yet and b) that you can get to in the least number of days (hence the priority queue). For the next state, you once more apply all medicines, and so on. You do this until you reach the state without any symptoms or the queue is empty in which case there is no solution.

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

Weakforces

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

I think the test case XXX XXX XXX should be invalid. According to the problem statement, this test case is invalid, because it means that the same player is taking consecutive turns.... in my opinion it should not be considered as a valid input

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

Hi, I Have question regarding this contest. In b question it was stated that classical rules are applied. But the test case on which my code was hacked is .+x .+o .+x which can never exist with classical rules. Please clear my doubt.. If it cannot exist with classical rules why it is considered for test case?

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

I am very confused, I just feel like my G should not be a correct solution. Can anyone give me a testcase that my code gives a wrong answer??

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

Can anyone tell me why my code on problem C fails? Thank you.

In my solution...
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Most Likely a case of integer overflow(my solution also failed system testing on test case 6). Change p.first.second to long long and it should work fine

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

    It is because you are accumulating the sum into 0, which is an integer. I changed 0 to 0ll to avoid overflow, and now your solution passes. 212883277

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

Can you speak Chinese

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

    Don't post meaningless messages here. You can speak Chinese in "Talks" module.

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

    it seems that you played too much genshin impact. here is my suggestion:

    • stop playing genshin impact, go and solve some problems, learn how to use binary search.
»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

This contest taught me to take all the possible precautions and not necessarily trust the problem statement.

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

please update problem ratings.

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

Is this round unrated? The ratings I received from this round had been disappeared.