EJIC_B_KEDAX's blog

By EJIC_B_KEDAX, 4 months ago, In English

Hello, Codeforces!

I am pleased to invite you to participate in Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2), which will be held at Jul/18/2024 17:35 (Moscow time). You will be given 8 problems and 2 hours to solve them. It will be rated for all participants.

The theme of the round is computer games!

Tasks for the round were prepared by EJIC_B_KEDAX, zwezdinv, green_gold_dog, molney, azureglow and Sokol080808.

We would like to thank everyone who assisted in the preparation of this round:

  1. Our coordinator 74TrAkToR for his useful advices and help in preparing the tasks!

  2. Qwerty1232 for red interest in testing the round.

  3. turmax for the red-black testing.

  4. makrav, arbuzick, Anonymous_Noob, Hyperbolic for red testing.

  5. ivan.alexeev, alenenok, Kihihihi, azureglow, pakhomovee, plagues, IzhtskiyTimofey, FelixArg, XaRDKoDblCH, meowcneil, AndreyPavlov, djm03178, MylnikovNikolay for yellow testing.

  6. Mr_Ell, krigare, marzipan, TimVen74, coder8080, MichsSS, PieArmy, tvladm, Vladosiya, bashem for purple testing.

  7. Algolagon, PoDuReMaN, zarubin, IgorA, leoper, kovir_aleksey_korroy, Kosya, Vamperox for blue testing.

  8. MakGeoKar, viteli for cyan testing.

  9. Sonya_2009, ishaandas1 for green testing.

  10. MikeMirzayanov for the excellent Codeforces and Polygon systems.

I also congratulate green_gold_dog on his birthday and wish him good luck on IOI.

This round is supported by NEAR!

NEAR was founded in 2017 by Illia Polosukhin, one of the creators of Transformers, and Alex Skidanov as an attempt to build an artificial system capable of solving competitive programming problems. You can read more about that attempt here.

Ultimately, NEAR pivoted into building a blockchain protocol, which it launched in 2020.

This year, NEAR started NEAR.AI, a new lab with a mission to build AI systems that are open and available to everyone, instead of being controlled by a few mega-corporations.

One of the areas of focus is making models capable of reasoning reliably, and for that, competitive programming problems provide a great environment. To help us build it, we invite all members of the Codeforces community with a rating of Specialist or higher (1400+) to help us annotate step-by-step explanations of solutions to competitive programming problems. We want to annotate a very large set of problems of all difficulty levels, and pay relatively high rewards in NEAR per annotation. You can join the system following this: https://codeforces.net/settings/near-connect-account

Thanks to NEAR for providing the following prizes to the contestants:

  • 1st place: 512 Ⓝ;
  • 2nd and 3rd places: 256 Ⓝ each;
  • 4th to 7th places: 128 Ⓝ each;
  • and so on;
  • 512th to 1023th places: 1 Ⓝ each.

Score distribution: $$$500-1000-1250-2000-2000-2500-2750-3750$$$

Good luck!

UPD: Editorial

UPD2: Congratulations for the winners:

  1. tourist

  2. ecnerwala

  3. orzdevinwang

  4. Egor

  5. jiangly

  • Vote: I like it
  • -247
  • Vote: I do not like it

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

I hope to become expert after this contest ^_^

Good luck everyone and have fun <3

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

Seeing 74TrAkToR as coordinator is quite scary, change my mind.

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

praying for 1434 rating

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

Finally not 3h Div1 but 9 tasks in 150min, I hope the round is not too speedrun.

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

    8 tasks in 120 min

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

      It changed, I saw it was 9 tasks yesterday.

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

        Actually now it's more speedrun than original (personally, I feel that 74 likes 8 tasks/2 hours combined round)

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

Hello, I am writing this comment, possibly hoping for officials at NEAR to see.

Recently people on Baekjoon Online Judge (BOJ) have seen many DMs on Codeforces, apparently related to the payout for NEAR.AI. They have been asking for solutions (assumably they annotated the tasks themselves but did not have solutions) to many tasks on BOJ. I am gently asking you to remove the BOJ platform from the automated payouts for the AI. Here are a few reasons why.

The BOJ Rules state this is bannable offense.

Through investigation, the users at BOJ had found out that the BOJ account sahera5474 is related to verifying the solution for the payout (though, we did not know exactly what kind of service it was at that time). This kind of automation, not only is condemned by the users, but is also bannable offense according to the rules.

The following is part of what is stated on the rules of the platform (link):

...

Cheating: Cheating states of the behaviour of submitting code that one did not write.

The code that is considered cheating is removed from the site, and according sanctions follow the following rules.

  • User A submits copied code on task B: User A's submissions on task B are removed entirely
  • User A commits repeated cheating: All of User A's submissions are removed entirely

The user reported for cheating is penalized accordingly.

  • First case: 7 day submission ban
  • Second case: 31 day submission ban
  • Third case: 2,147,483,647 second submission ban

...

Clearly, this kind of behaviour is considered cheating on the platform, and is bannable offense.

Most tasks on Baekjoon are not worth any payout for solutions, as they have the solutions publicly available.

For whoever does not know how the Baekjoon platform is maintained, the website contains the following kinds of tasks.

  1. Tasks from user contests/local contests (mostly by Korean people)
  2. Tasks from any other contest apart from the platform (OI, ICPC, foreign local contest, etc)
  3. Personal task contribution (also mostly by Korean people)

For case 1, most such contests contain official editorials, so the solutions are publicly available. For case 2 it is almost the same as case 1, but you will likely have to search outside the platform for the publicly available solution. Most cases where the solutions are not publicly available belong to case 3, but recently case 3 appears much less than case 1 or 2 in quantity. Therefore, an automated payout for training the AI on tasks of case 1 or 2 would make no sense.

Conclusion

Even if one suggests the two points above might not hold for this specific case, it is common sense to consider the DMs from the payout assignees to be considered as fraudulent use of both the Baekjoon platform and your payouts. Therefore, I am publicly asking to remove the BOJ platform from automated payouts and possibly the training data.

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

    Hi, it's not the solutions, but the step-by-step way people solve them that we are after.

    Apologies for violating your ToS, as of right now all the integrations with Baekjoon that we have are turned off, there should hopefully be no folks reaching out to you going forward.

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

      Thank you for the reply! I have outlined in your DMs what could be possibly done to fix the issues in the long term. If you don't mind, please give it a look and tell how you think about it.

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

[user:ivan. alexeev]

seems markdown is not working

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

In NEAR, orange is yellow!

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

Hope to reach 1800 in this round

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

Hope the competition goes smoothly! :)

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

Do I really need coderforces-near-connect-account setting? It is tooooo complicated. Built-in wallet doesnt work and I even need certificate from goverment for proving where I live!

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

As a tester, I

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

Hope it's a good round with strong pretests!

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

I also congratulate green_gold_dog on his birthday and wish him good luck on IOI.

Happy birthday green_gold_dog!

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

As a tester, I hope that everyone will enjoy solving the contest and find a wonderful problems. I wish everyone good luck)

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

Scoring distribution when?

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

sigmaforces

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

As a tester, I can say that problems are very interesting and I wish everyone good luck

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

What is N currency?

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

Why is there no number for this round? Sequential Codeforces Round numbering would be more convenient in many ways. Also, there can be numbering for NEAR rounds since this is not the first round sponsored by this company.

Update: the round has number 959 now. Okay.

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

Hope it doesn't become a speedforces :3

9 problems for 150 minutes ???

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

Is there any reason why most of the contests score distribution follows GCD(score distribution)=50 or 100??

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

    Actually, the GCD is always $$$250 k$$$ ( $$$k$$$ is a positive integer ) because of the rule.
    On CF, if you solve a task during $$$k$$$-th segment of the round when the round is equally seperated into $$$120$$$ segments, you got (max points for the task) $$$\times$$$ $$$( 1 - \frac{k-1}{250})$$$ points (minus, Wrong Answer penalties), therefore, to make the score integer, the max score must be a multiple of $$$250$$$.
    For further details, look at this page (just above of "Hacks") and this comment.

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

As a tester, I was expert when I tested so participate in the contest.

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

    PieArmy can you explain more about your statement ? how does testing of a contest work , is it rated when you test?

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

Good luck everyone.

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

How to change my account because I lose it

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

    If you are referring to NEAR account, send me a DM. I'd need more details to be helpful here.

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

When would the rating rollback happen for the previous rounds?

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

As a participant, I hope cheaters don't ruin the contest. Let's ensure that everything is fair and done correctly.

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

I'm excited!

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

What are the score distributions for the problems?

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

As a tester, I can say that problems are very interesting and I wish everyone good luck

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

Hopefully I get back the rating I lost in last rounds

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

"Dear God, I come to you with a heavy heart, seeking your guidance and wisdom for those who resort to cheating in coding contests. Grant them the insight to understand the value of honesty and integrity, and the humility to seek success through their own efforts. May they realize that true achievement comes from diligence and skill, and may your wisdom guide them to choose the path of integrity in all their endeavors. Amen."

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

please give me positive delta

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

Good Luck!

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

I hope to not become pupil again. I wish the problems to be interesting. I wish there were a round based on specific games and the problems have a story of the game. (Imagine, "Kratos has brought n deers and Atreus wants to eat them with maximum weight first...would be so awesome xDxDxD)

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

    any tips to reach specialist like you? I mean you havent solved that many questions of range >1200/ 1300 but still you are a good specialist

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

      build logic as fast as possible. moreover, i had done 230 questions on my previous id but had to stop it and made this new one. i was solving for quite a time but only from last year or so i started giving contests seriously. trust me problems <2000 are not hard. i strictly believe that you should try your best from your id only as you will be fooling urself. try to stay thinking fast, learning concepts, seeing code of top ones etc. have a zeal to learn. don't give up. choose discipline, not motivation. peace.

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

cout <<" GOOD LUCK EVERYONE "<< endl;

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

Two and a half hours is too short for round 1,2

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

What is "512 Ⓝ" mean? It's name of money type ?

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

another speedforces?

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

    yes

    I think if you solve A B C fast you will get expert performance

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

The number of problems changed from 9 to 8... So it is going to be speedforces (?) :(

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

    Okay, I'm not fast enough :(. Solved ABCDF but ranked lower than 70% of the ABCDE solvers.

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

Hope @74TrAkTor doesn't spoil the contest

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

surely i wont throw this time

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

nvm

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

i hope to become newbie after this contest, after long time.

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

hope to reach 1900 today

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

I'm 909 rating should I join or I will lost alot rating ?

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

    Join bro, let's lose rating together, don't worry about it, it doesn't matter, what matters is attempting & working on problems, if/when we get stronger, the rating will come. Enjoy.

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

      best piece of words i heard on cp

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

      Thank you for your suggestion I was going to increase the rating because thank God I solved b but unfortunately wrong answer in a

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

      Lord Krishna had said , You have a right to perform your prescribed duties, but you are not entitled to the fruits of your actions. Never consider yourself to be the cause of the results of your activities, nor be attached to inaction.

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

hoping to get under 1k

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

Congratulations, Codeforces checked that I am human in just 5 minutes!

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

bad D

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

Problem C , statement's input is written The first line of each test case contains three integers n , x (1≤n≤2⋅105,1≤x≤109) — the number of mushrooms and the maximum toxicity level. But three integers are not there are just 2, is this a mistake or am i trippin?

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

There is penalties for wa on test1 ???

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

There's no way, I fumbled on B and got humbled by C.

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

The fact that I could straight up ignore the tree structure in E is the funniest thing I've seen in a while hehe.

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

Very very good set of problems! Thank you!

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

C : Hungry Games is a simple application of the famous interview problem Jump Game. I created a video editorial for today's C.

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

    There is also a linear solution: for every l find first r such that $$$\sum\limits_{i=l}^{r} a_i > x$$$ (you can do it with 2 pointers), then calculate a $$$dp[i]$$$: number of segments with i as left border such that game on these segments will end with some none-zero score. $$$dp[i] = (right[i] - i) + dp[right[i] +1]$$$.

    You can add a fictive $$$+\infty$$$ element to the end of array, also $$$dp[right[i] +1]$$$ should be added if only $$$right[i] < n$$$ (numeration from 1).

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

      Can we do the same by going from $$$1$$$ to $$$N$$$ and calculating number of segments with i as right border?

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

        Yeah, sure

        Just keep in mind that array $$$right$$$ can not be easily transformed into $$$left$$$ (with analogical meaning), you need to find $$$left[i]$$$ explicilty with 2 pointers going from $$$n-1$$$ to $$$0$$$.

        The rest actions are completely symmetrical.

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

how to be good at problem like C

I'm going down green again 💩

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

Just thought about Pigeonhole principle in problem D at the last minute of the contest.

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

    explain please

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

      Also thought of it, but couldn't code it in time. The basic idea is that you have n-1 operations at most, but n elements in the array. Hence, no matter what operation, it is guaranteed you get two elements which are divisible by the operation number. I couldn't really prove that this will extend from any operation to all operations, so a proof of that will be nice.

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

      For each $$$x$$$, it's easy to see that we only can pick two vertices $$$u$$$ and $$$v$$$ when they have the same modulo $$$x$$$. So what we can do after knowing this? Suppose we solve this problem in the reverse order of $$$x$$$, i.e iterate $$$x$$$ from $$$n - 1$$$ to $$$1$$$. Then we can blindly pick any two vertex $$$u$$$ and $$$v$$$ such that they are not picked in the previous steps and have the same modulo with the current $$$x$$$, and we are done. And the fact that this problem always have the answer $$$YES$$$.

      So why does it work? Let's consider the first iteration when $$$x = n - 1$$$. Then, when we modulo all $$$a_i$$$ with $$$x$$$, we will have at most $$$n - 1$$$ different outcomes. And according to the Pigeonhole principle, if we have $$$n$$$ elements and $$$n - 1$$$ outcomes, there will be at least two $$$u$$$ and $$$v$$$ have the same modulo, so we choose those two $$$u$$$ and $$$v$$$. And the same procedure could be applied in the next iteration, as after the previous iteration, we will care about $$$n - 1$$$ vertices so we could apply the Pigeonhole principle again until $$$x = 1$$$.

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

        Damn that's actually crazy. Thanks for writing this.

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

what was D?

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

    At each stage i, take A[j] mod i for each j. Vertices with the same remainders can be connected by an edge. Pigeon hole principle guarantees that you can always find an edge that doesn't create a cycle.

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

      I got the first part, but what is the pigeon hole principle? And how would you go about finding those edges?

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

        Ok I forgot to mention that you have to reverse the process and add edges starting from stage $$$i = N - 1$$$.

        When stage $$$i$$$ begins, you currently have $$$N - i - 1$$$ edges added. Let $$$rem[k]$$$ be a length $$$i$$$ array denoting the number of vertices that falls into the remainder of $$$k$$$. So clearly the sum of $$$rem[k]$$$ is equal to $$$N$$$. Now for contradiction, suppose that adding any valid edge to the DSU will create a cycle. This implies that for each group of vertices that falls into remainder $$$k$$$ bucket, these vertices form a connected component. This implies that there are $$$\sum_{k = 0}^{i - 1} rem[k] - 1 = N - i$$$ edges currently part of the DSU. but This is clearly a contradiction, as we started out with an assumption that there are currently $$$N - i - 1$$$ edges in DSU.

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

        And for finding those edges, well, you just have to find two vertices within each remainder group that have different roots of the DSU.

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

    Pigeonhole Theorem.

    For any $$$m$$$ numbers, there exist at least two numbers with the same value modulo $$$m-1$$$.

    So the answer is always yes.

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

      I got this, but how to show that the 2 nodes with same modulo also weren't connected via some previous set of edges?

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

        Suppose currently we have $$$k$$$ elements, and $$$x = k - 1$$$. After we choose two vertices $$$u$$$ and $$$v$$$ in the current iteration, then in the next iteration, we will only need to care about $$$k - 1$$$ elements as we can ignore $$$u$$$ or $$$v$$$, and the Pigeonhole Theorem could be applied again.

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

        Do it backwards: start with stage $$$n-1$$$ and keep going until $$$1$$$, then reverse the answer later. At stage $$$x$$$, let's say vertices $$$a$$$ and $$$b$$$ are the same mod $$$x$$$. Connect $$$a$$$ and $$$b$$$, then erase one of them (i.e. ignore it for the rest of the problem). This way we are sure that the same set is not connected twice. At each stage we remove one element, and we start with an extra element ($$$n$$$ elements at stage $$$n-1$$$). So this means that at every stage we have an extra element. Hence, pigeonhole guarantees the existence of two elements with same mod in every stage.

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

Was D a variation of Hall's Marriage Theorem where there are more nodes on one part of the bipartite graph? I didn't have enough time for it, seems like a fun problem though :(

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

    no it was just observing php

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

      Yeah, I was searching for a way to do a pairing between the diffs and the nums from $$$1$$$ to $$$N-1$$$, but it seems you cannot go wrong with it...

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

I actually saw F before: https://codeforces.net/gym/101879/problem/C

Something something traktor bad something something

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

d hint?

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

    I am not sure but I was trying with DSU and thought today's contest was 2.5hrs long :)

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

Are pretests = sys tests? I'm 90% sure that my solution for problem D is bs, but somehow it passed 30 pretests.

Actually the solution was fine, for $$$n$$$ numbers and $$$x = n - 1$$$ at least two numbers will always be equal modulo $$$x$$$, by removing 1 number then we get $$$n - 1$$$ numbers left and $$$x - 1$$$, so pigeonhole principle repeats itself.

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

    I hope so, I am pretty sure my solution can be TLEd, but it passed pretests as well...

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

The most speedrun round I have participated. I feel they are too classic for D1.

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

Tags for D??

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

How come there are so less submissions for C?

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

How do you think and come up with the solution for B?

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

    If $$$s$$$ only has 0, you cannot modify anything. Otherwise, every index from the first 1 to beyond can be modified at will.

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

    Once we simplify operation, we understand that in one operation, first $$$x$$$ elements of $$$s$$$ we can XOR with first any substring of $$$x$$$ elements in $$$s$$$, for any $$$x$$$ we chose..

    Now if the first bit in $$$s$$$ is 1, we can clearly make any string $$$t$$$. (Remember that XOR with 1 flips a bit, and XOR with 0, it remains the same.)

    Now if the first bit in s is 0, but second bit is 1, we can make any string $$$t$$$ whose first bit is also 0.

    And so on.. So the final answer: the first position where 1 appears in $$$s$$$ must be <= first position where 1 appears in $$$t$$$, if it possible to make $$$t$$$ from $$$s$$$.

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

Solved ABCD, but I am below people that only solved ABC or ACD...

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

Great set of problems!!!! But Internet and "Confirm you are not a robot" costed me 5 minutes on A :(

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

what is the idea behind D?

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

Upvote if you think that the penultimate problem of a prized CF round having almost 200 solves is a great idea

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

Man, the limits in C were pretty harsh. This got me a MLE: https://codeforces.net/contest/1994/submission/271247958. And this one got me TLE for some reason: https://codeforces.net/contest/1994/submission/271261706

Both solutions exceeded the problem's limits despite being O(N^2), I guess my rating is plunging once again hehe.

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

    Usually $$$n \leq 2 \cdot 10^5$$$ indicates that $$$O(n^2)$$$ solutions will not work. There was a $$$O(n\log{n})$$$ solution for the problem.

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

    mine

    void solve(){
        int n,x;cin>>n>>x;
        ll a[n],p[n];
        REP(i,0,n)cin>>a[i];
        p[0]=a[0];
        REP(i,1,n)p[i]=p[i-1]+a[i];
        ll count=0;
        int dp[n]={0};
        for(int i=n-1;i>=0;i--){
            auto it=upper_bound(p+i,p+n,p[i]+x-a[i]);
            int j=it-p;
            dp[i]=(j+1>=n?0:dp[j+1])+j-i;
            count+=dp[i];
        }
        cout<<count<<'\n';
    }
    
    signed main(){
        fast_io();
        int t=1;
        cin>>t;
        while(t--)solve();
        return 0;
    }
    
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I went through hell and came back while trying to solve B.

Anyways, great problem set! Thanks for the round EJIC_B_KEDAX zwezdinv green_gold_dog molney azureglow Sokol080808 and all testers!

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

G = https://codeforces.net/contest/1670/problem/F

Do the coordinator and the problem setter believe that DIV 1 + 2 equals DIV 3 ?

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

I had a very bad experience.The network is terrible.codeforces keep verifying me “are you a human?”. And the statement on m1.codeforces.com is somewhat not available.So I can only read the problems on my phone and solve the problems.After about half an hour am I able to visit the page normally.And now and then it needs verifying and the page just stuck there for minutes,which is quite annoying....

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

Will my solution for C be accepted if its O(n^2)?

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

    Nope, C is le funny problem

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

    Unless you use bitsets in your program, this is impossible

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

Fucking Speedforces :(

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

Didn't want to participate because I didn't sleep well last night, read problem E in bathroom, realized solution was simple, turns out I was one of the first to get accepted lol.

Solution is just count occurrences of bits of sizes of trees, if a bit occurs twice you can turn on every other bit below it. The shape of the trees is not important

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

    how did you reach this conclusion ? ( in the last line ? )

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

      You can get any size removing leaf by leaf. Then, if you have more than one tree with the i-th bit on, you can remove leaves from other trees to turn on all the bits less than i.

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

        Hii, Suppose I have two trees of size 8, Both trees are of the form: Root is 1 , and 7 other nodes attached to root 1. 1st tree will give me 8, Can you please tell how will you generate 4,2,1 using the second tree? I can generate either (4 and 1) or (2 and 1) but not all three simultaneously.

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

          You just take a leaf from one of the trees then You have 7 and 8, 7 | 8 -> 15

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

      You can always delete some unimportant leaves, so if the size of some tree is $$$N$$$, you can get a tree with any size less than $$$N$$$. If you reach a tree size of $$$2^m$$$, by removing 1 more leaf you can set to $$$1$$$ all bits less than $$$m$$$.

      Too bad I spent a lot of time figuring out if my solution for D is correct or not, E wasn't actually difficult at all.

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

Someone just ping me when the editorial is out I'm only able to solve A,B and tried D but TLE :) , As my first contest solving 2 questions is fine ? :')

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

c was wild

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

I had to reevaluate my whole life while solving B and C today.

But overall nice problem set!

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

In problem B, what will be the answer for this testcase : 0110

0101

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

    Yes.

    Apply operation $$$(2, 3)$$$ to make it 0100, then $$$(3, 4)$$$ to make it 0101.

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

      Thanks! I didn't even consider overlapping segments in the contest.

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

speedforce

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

E got WA on pretest 11 and don't know why :(

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

    I got the pretest passed and even I don't know why

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

When I was finally able to open the very first problem statement (which was problem A, but I wanted to start with B or C), the timer already showed more than one minute passed since the start of the contest. During this time I tried to use m2.codeforces.com, but it told me there is no access to the statements. The main site was either displaying the connectivity error message or asking me to prove that I am a human being.

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

I just can't solve problems anymore xD

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

;!

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

Super easy solution to H: 271267941

code
  • Query 1: ask aa -> learn p
  • Query 2: ask S = (z 50 times) -> learn a = X mod m (where X is base value of S)
  • Query 3: ask some string with base value $$$X - a - b$$$ where 1 <= b <= a + 1 -> learn m

You learn m because $$$(X - a - b) \text{ mod } m = (((X - a) \text{ mod } m) + (m - b)) \text{ mod } m = m - b$$$.

To form string for query 3, first subtract 1 from the base value by reducing the first character by 1, then subtract something between a and 2a. To do this, just consider how many multiples of every power of P you must subtract to subtract a. If it is at most 24, subtract that straight from the letter. Otherwise, subtract 1 from the next letter. This works because P <= 2 * 25, and every letter is subtracted at most once from the carry, and at most by 24 directly.

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

With more and more coordinators like 74TrAkToR who would place the G at G, I'm sure it will soon become a trend for users from all rating ranges to solve problems A ~ G in Div 1+2!!!!!!!!! Very refreshing speeeeeeedy round, love from Botswana

UPD: The trend also appeared in past Div2 contests like 1891F.

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

Nice round!

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

I got in top 1023 places but I'm not specialist yet. How can I gain my prize? Haven't NEAR thought about people that have <1400 rating??

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

    Try participating from your main account next time.

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

      Yes I am sorry for using my alt account (to make it seem less severe, the first round I'm taking I'm having a headache so I decided not to risk it and thought rounds with money must be participated with this account eversince). But actually the thing I'm most concerned with is there may be other main <1400 rating accounts who have missed the prize.

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

        Having multiple accounts is against the rules. You should be banned on your both accounts. cc: MikeMirzayanov

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

          Snitch.

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

          I recommend you to let Mike ban my friends first: They have higher rating which may cause more harm codeforces.

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

    nice hoping you did it by urself

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

I spent one hour trying to know how to find the Euler circuit but failed, and I saw this problem at least twice before... This round should not be a division 1 and should be an educational round. Additionally, Codeforces was intermittently down during the contest.

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

    In my opinion, understanding the Euler circuit problem is important for problem F, but not all of it.

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

Thanks for the amazing test cases in problem D.

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

Got the idea of A in first 5 mins but it took me 30mins to implement it I am such a dumb:(

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

fapipotato orange when (v_v")

hope for positive delta and road to lagenry grandmister!!1! (^o^)/

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

It wasn't until I saw the "int foo" in the tourist's E-question code that I realized I was just a fool.

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

WTF????Extortion???

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

(Problem F)

It is guaranteed that you can reach any house from any other by walking on the roads with NPCs only.

I think that the constraints on the input should be written not only in the problem statement but also in the Input section.

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

    You're right. Sorry, missed that when editing the statements. The validator checks that, of course.

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

I'm sorry,but I want to say that it's a rubbish contest because the rank depends on the speed,not the knowledge you have.In the other words,if you have enough knowledge but little speed,then you will fail in this contest.But OI and things like that needs a lot of thinking and the knowledge is more important than speed.This contest can't train contestants to think or to learn.So I think it's a bad contest.Hope that author can have more high-quality contests!

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

Can someone suggest me some source for

$$$dp$$$

questions on codeforces so i can practice and learn??? I'm really afraid of the topic and want to overcome that fear.

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

I finally became blue :)

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

    If I understand your question correctly, the link you pasted is generally the right way to onboard to Acadé Studio (modulo the right handle instead of ~).

    Feel free to ping me via DMs if something doesn't work.

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

Hi i got rating (0) does that mean its a +0 or its a glitch :(

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

    +0

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

      bruh i think i should make a new id this id could be a cursed

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

        You know that is a rule violation right? If you only care about rating you will just keep on making new accounts learning nothing, I'm sure that's not your goal??

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

        You don't want to be like zh0ukangyang, right? Then don't make alt accounts.

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

F: There weren't any extreme cases such that

2 500000
1 2 1
1 2 1
1 1 1
1 1 1
...

Some bad implementation of Eulerian Circuit (including my contest submission) got uphack, so if you're afraid I suggest you to resub to check.

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

The problems are so known that even chat gpt can solve it

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

About C, I think this question is enlightening:

https://atcoder.jp/contests/arc169/tasks/arc169_b

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

Why the time for 1+2 is 2h. I nearly passed G but I had no time at last.

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

Yoo ,C was a good educational question.Got to learn something new.Thanks

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

I like TrAkToR:)

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

    It seems a lot of people didn't like this round, but I liked the round. The cloudflare issue wasn't that bad for me. Apparently there were repeated problems, but I hadn't seen them, and I thought F was interesting.

    I think people deserve second chances. Let's support 74TrAkToR !

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

      Couldn't agree more! Even though most of these problems have shown up on leetcode and code.org (jk haha)

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

Thanks for decent quality contest.

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

It's really a great SpeedForces Round.

Here's my thought during this round.

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

I have some problem with my near account. I didn't copy my Private Key or Seed Phrase and now I can't login. Is there any solution or who do I need to find for help?

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

tourist is back

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

Can anyone hack or explain my solution in problem C?

i don't know why this pass. TwT

271325693

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

Stuck in B forever Gang

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

Very good trush round!This made my brain quickly rotate.

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

I should've won 1 NEAR and after the contest I opened my NEAR account and it shows the amount to claim is 0?

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

    You would receive message from System when near are distributed

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

Downvoted

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

I should've won 2 NEAR and after the contest I opened my NEAR account and it shows the amount to claim is 0?

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

    The prizes for this round have not been entered into the system yet.

    It takes several days after the round to filter out all the duplicate submissions and finalize the standings.

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

for problem 3 and I solved the question with a good amount of time and also got a wrong submission . But codeforces saying my code is same as of someothers . Just check it : My code :https://codeforces.net/contest/1994/submission/271254358 Others code ( given by codeforces) : https://codeforces.net/contest/1994/submission/271237089 How it could be simillar I agree the intution is quite simillar. And its very simple to be . Please recheck it and give me back my rating .

(There are many one Who have also the same code as the others but they didn't got any plagrism) Also Got an solution https://codeforces.net/contest/1994/submission/271241875 which is as same as the others but this account did't got an plagrism . I appriciate the thing of plagrism it should be more trict but at first it should be more accurate.If giving plagrism please check it out carefully. My Submission : 271254358 Othhers Submission : 271237089 One's Submission same as others but didn,t get plagged : 271241875

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

    Same with me I submitted after a lot of Wrong answer at almost closing time of the contest on my own.But I received a mail that mine coincides with a lot others.

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

      Bro . Thats Good that they are checking but its wrong that giving plag to the genuine code

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

Dear Codeforces Team,

I am writing regarding submission 271253205 in contest 1994. I have been flagged for plagiarism, but I would like to emphasize that my code and the flagged submission may share similar intuition, but they are not identical.

I have invested significant effort in solving this problem, and my last submission was just before the contest ended. I understand the importance of maintaining integrity on Codeforces and respect your responsibility in ensuring fair play. However, I kindly request you to review my submission separately from others that have been flagged.

I am willing to discuss any concerns or provide additional clarification if needed. Please reconsider the decision and avoid banning my ID outright. I am confident in my abilities to regain my rating fairly, but I hope to resolve this misunderstanding promptly.

Thank you for your attention to this matter.

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

Hello, [submission:271243589][submission:271238016], i have got email from CF that my solution is copied from the other solution. I want someone to please check and help me what thing i copied, as i have not done any kind of cheating. i am new to this platform and getting this email is discouraging. How to stop it and avoid in future if someone can guide me , and what mistake i had done in the solution that seems to be copied, i am not getting that point. Its was question with general answer. Please someone guide me and help. And request CF to remove cheating tag from my solution.

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

Subject: Clarification on Solution Similarity and Account Suspension

Dear Codeforces Team,

I received a notice about my recent solution (ID: 271257872) matching another submission. I want to clarify that, while the approach may be similar, I used my own code snippets and did not copy any solutions. After two unsuccessful attempts, I submitted my original solution. Please note that my other two submissions, which have no allegations of copying, were also skipped.

Additionally, my old ID (Anas_006) was suspended for a similar issue. Could you please inform me of the expected time for its reinstatement?

Thank you for your understanding and assistance.

Best regards,
suplex_city

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

problem name is fun ngl:)