By ArshiaDadras, 3 weeks ago, In English

👋 Salam, Codeforces!

We are thrilled to invite you to the Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2).

The Selection Round is a rated contest for Div. 1 + Div. 2, taking place on Nov/30/2024 17:35 (Moscow time). The problems for this round were crafted and prepared by ArshiaDadras, MohammadParsaElahimanesh, AmShZ, AmirrzwM, and Keshi.

The top 60 trusted participants (with a maximum of three from each country) will qualify for the onsite Final Round in Tehran, in Spring 2025. An additional quota is reserved for the host country. Hotel accommodation, local transportation, and meals will be provided to all finalists. More details about the final contest will be available on the Rayan website.

🏆 Selection Round Prizes:

  • The top 50 participants will receive T-shirts. 👕
  • Additionally, 50 random participants from ranks 51-1000 will also receive T-shirts.

🏅 Final Round Prizes:

  • 1st place: $15,000 💵
  • 2nd place: $10,000 💵
  • 3rd place: $5,000 💵
  • 4th–6th places: $2,000 each
  • 7th–10th places: $1,000 each

🙏 Special Thanks:

We would like to extend our deepest gratitude to:

📊 Score distribution: $$$500 - 750 - 1500 - 1500 - 2000 - (2000 + 2000) - (3000 + 3000) - 5000$$$

We look forward to seeing you both online and onsite!

Good Luck & Have Fun! 🎉

Note: Editorial just published here! 🚀🍿

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

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Auto comment: topic has been updated by ArshiaDadras (previous revision, new revision, compare).

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there a separate category for Iranians, or will all participants be grouped together?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      All participants are considered together. The only difference is that we have a separate quota (about 30–40) for Iranians, which will not be counted within the main quota.

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

As a tester, I didn't know I could have won $15,000 (just needed to beat a certain Belarusian...)

Y'all should give it a shot!!! Good luck.

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

    Sorry man, but I have to admit that I'm kinda glad you didn’t know that 🫂

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

    For the 1st time in my life, I found the tester's comment funny!

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

As an author, please give me T-shirt too.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -114 Vote: I do not like it

I predict tourist will fall below 4000.

Edit after round: everyone who downvoted this should apologize to me in DMs.

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

Nice! This must be one of the rounds of all time, I'm so excited to see my teachers' round ;)

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

    Let me tell u sth about ArshiaDadras:

    I officially started competitive programming and programming classes with Arshia Dadras four years ago. He is a very capable and ethical teacher. Thank you, Arshia, for being so great <3

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

      Thank you so much for your kind words and support, AmirParsa!

      It’s truly a pleasure to be remembered in such a thoughtful way. I’m also really happy to see that you’re continuing to improve your coding skills.

      Wishing you the best of luck in your journey, and I hope we get to meet in person soon!

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you, man. It's an honor for me to have grown under the guidance of professors like you. I'm looking forward to meet you in person too ;)

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

"The top 60 trusted participants (with a maximum of three from each country)"

How will you enforce this?

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

    We will start inviting participants from the top of the list while considering the country limit (a maximum of three participants per country) until we fill all 60 spots. Each invited participant will have a specific time frame to confirm their attendance. If someone declines or cannot attend, their spot will be given to the next eligible participant from the scoreboard who meets the criteria.

»
3 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

Paying people that much to solve problems with already existing solutions..

»
3 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

As a tester, this is the $$$4^{th}$$$ time in a row I found at least one problem in the round I tested really satisfying, and I hope people would feel the same.

»
3 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

I love Persian contests!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you like Persian contests?

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

      Because most of them are about their history, and Persian history is very good.

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester I wish good luck to everyone!

»
3 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

As a tester, I can confirm that I tested this round.

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

As a tester, I liked to test my first round! :)

PS: If you win $15,000, please give me the T-Shirt, hahaha

»
2 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Final Round Prizes: 1st place: $15,000 2nd place: $10,000 3rd place: $5,000 4th–6th places: $2,000 each 7th–10th places: $1,000 each

^^^

How much will you win? They're really rich...

(This is my first comment on CodeForces so if you think I'm wrong please politely scold me)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you look at their website, the onsite part is sponsored by a university and from what I can tell an entire ministry, and these prizes are for the onsite part. This round is only a selection round before the onsite one.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understand, thank you. By the way, the prize money for the competition held by Huawei last time was also as high as this

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

as a persian, i can confirm i ain't winning shit

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

    But I guess we'll have someone from Iran in the top 10... P.S. Let’s bet lunch on it!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    as a persian, i also confirm i'm not winning anything

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

W salam

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

I'm quite interested that, is there any special about the sponsor? why does this contest appears on the top bar?

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

niceeeeeeeeeeeeeeee

»
2 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

tourist will destroy this contest to earn money

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

As a participant, I will participate!

BTW, what watch are you wearing, sir ?! ArshiaDadras

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

Do you arrange this every year?

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

    We’re planning to do that, but this is Rayan’s first year!

    We need to evaluate the feedback and reception from participants before making a clearer decision.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks.. It will be great. Can I ask you the meaning of "Rayan"

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

        “Rayan” is derived from the first part of the Persian word “Rayaneh,” which means “computer.”

        Fun fact: If someone asks us, “What is the event name?” we would reply, “It’s Rayan.” In Persian, we could say this as “Rayan eh,” which follows the same pattern as saying, “It’s cold” -> “Sard eh” or “It’s good” -> “Khoob eh.” Interestingly, this sounds exactly like the word “Rayaneh”!

»
2 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

hope to reach expert this round. any recommendations?

»
2 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

this round will make tourist get back to gm i guess. lol

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

Fantastic ! nice job Iran. Good luck everyone.

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

and maybe the final prize in the next year

Bcz problems for this year have been leaked and the winners are already decided $$$??$$$

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

I am new to codeforces but still I try.

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

As a Participant, I can confirm that I am not a tester.

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

I'm just looking at the rewards knowing I won't be even close to top 10 :/

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

    Why not? At the very least, you’d get to enjoy a wonderful trip to Iran, stay in one of the best hotels here for free, and experience some amazing hospitality! (if you can make it to the top 60 😁)

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

Hey Tourist, I accept donations here ಥ_ಥ

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

Excited for my first contest as a specialist!

»
2 weeks ago, # |
Rev. 3   Vote: I like it -43 Vote: I do not like it

I will beat you all and go to the final round to win $15000.

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

if there are $$$50$$$ russians above me and all of them refuse to go to the onsite, will i be invited?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, as I said here! (if you'll be one of the next candidates to invite)

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

      if someone sets their country to Gibraltar will you somehow check that they are indeed from Gibraltar?

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

        I hope we don’t encounter these types of cheaters in the top 60. But don’t worry—we’ll verify their passports during the invitation process to catch any discrepancies.

»
2 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

As an Iranian, this really makes me proud!

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

    And I would like to thank the medalists who designed the questions and all the people involved and hardworking in this event!

    I think it is a good thing that the famous programmers of Codeforces come to our country.

    I hope to see the tourist here!

»
2 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

The same day as chinese NOIP! Hoping we all have good performance in the both round!

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

is it for rating

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

May everyone get their expected rating plus this round<3

GG everyone!!

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

Is this round rated?? as normal cf contest

participation is enough for registration or i have to register on website or something??

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's like a normal rated contest in CF. Also, participation is enough for registration and you don't need to register on the website or somewhere else.

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

Great

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

Time Conflict with ICPC Regionals QAQ

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

im new to codding but still im going to Participate hopefully i receive a t-shirt

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

looking forward!

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

Salaam too.

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

Hope to cross 1100 again this time!

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    Hey..I looked at your profile..you have been doing cp for more than 2 years now but still not able to improve much even after being so consistent..with this much pracitce you should have touched pupil by now..Mayb you are doing something wrong.. Try solving cses that helped me..also you can practice usaco guide silver level prblms and learn techniques on prefix/suffix sum,two pointers etc..Also try atcoder contests and gym prblmes..Good luck buddy

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

      Thank you, buddy, for your suggestion. I’ve already solved many problems on CSES and am familiar with concepts like prefix sums, two-pointers, binary search, basic graphs, and recursion. I’ve also participated in a few Atcoder contests but haven’t practiced USACO or GYM problems yet— planning to work on those. Previously, I lacked consistency. So, recently I have been consistent and hopefully, I will reach pupil soon. I will try my best. Again buddy thanks for your suggestion. I am getting more inspiration to reach pupil now.

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

        You're most welcome.. I would suggest to go through the topics of usaco silver level and try to solve the problems of those topics like bs, prefx sum etc. from there first..(some of those problms are really nice but you may need to create accounts on multiple sites :)) Maybe then you can try out the gym problems.. (Also dont spend too much time on a problem if you cant solve it on first try.. Go to the next ones then come back agaim here.. I used to spend too much time on a prblm but thats not worth it but just a waste of time for most of the times) Hope for the best.. See ya

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester, I wish everyone good luck! :)

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

teams or no?

»
11 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Rayan Gosling Round

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

Wish tourist back 4000++ once more.. yo yo

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

rainboy orz (Problem H).

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

Seems orzdevinwang will become tourist soon!
...Why does the sentence sounds that strange.

»
10 days ago, # |
  Vote: I like it +6 Vote: I do not like it

I said D > C;

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

What is the case in E where a solution exists for both k and n being odd and k < n?

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

    in all cases, a solution will exist if n and k are odd except for k=1 and k=(n-1)!

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    1
    5 3
    
    YES
    1 2 3 4 5 
    3 4 5 1 2 
    5 3 1 4 2
    
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how do you construct the solution if k=3 and n>k?

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        Spoiler
        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ah ok i get the solution i just assumed that if k=3 and n>k it was impossible

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

nice pics SIR

»
10 days ago, # |
  Vote: I like it +17 Vote: I do not like it

C was so annoying to solve. Forgot one edge case and spent all my contest time on it, leaving no time for D :(

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

    Actually, C seemed difficult to me not because of solving the problem, but because of the implementation. What edge case did you get stuck on? I can share my solution if you want.

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

      Yes, the implementation was also painful. But I solved it at the last minute :')

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

How to solve E?

  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it
    Spoiler
»
10 days ago, # |
  Vote: I like it -68 Vote: I do not like it

Sooo nice E! Though it contains some casework, there is a beautiful construction method.

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

    Can you share it with us common folk?

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

      We treat $$$n=1$$$, $$$k=1$$$, $$$k=n!$$$, $$$k>n!$$$ first.
      Let's define $$$i$$$ th permutation as the permutation when we call next_permutation for $$$(1,2,\dots,n)$$$, $$$i-1$$$ times.
      First we construct for even $$$k$$$. We can just take $$$i$$$ th permutation $$$p$$$ and $$$(n!)+1-i$$$ th permutation $$$q$$$ together. (actually, $$$p_i = n+1-q_i$$$)
      For even $$$n$$$, if $$$k$$$ is odd, the answer is No (because $$$k \times \frac{(n+1)n}{2}$$$ isn't divisible by $$$n$$$)
      Now, we construct, for odd $$$n$$$, $$$k=3$$$. This can be done by this method (as an example, let $$$n=7$$$).

      • $$$(1,2,3,4,5,6,7)$$$
      • $$$(4,5,6,7,1,2,3)$$$ (left shift $$$\frac{n-1}{2}$$$ times)
      • $$$(7,5,3,1,6,4,2)$$$ (make sum = $$$3 \times \frac{n+1}{2}$$$)

      At last, we construct, for general odd $$$k$$$. We ignore following pairs:

      • $$$(1,2,3,4,5,6,7)$$$ and $$$(7,6,5,4,3,2,1)$$$
      • $$$(4,5,6,7,1,2,3)$$$ and $$$(4,3,2,1,7,6,5)$$$
      • $$$(7,5,3,1,6,4,2)$$$ and $$$(1,3,5,7,2,4,6)$$$

      At the current state, we can take $$$\frac{n!}{2} - 3$$$ pairs. After that, just add $$$k=3$$$. Then, we can construct for $$$3 \le k \le n!-3$$$.

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

        tysm

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

        wow! That left shift (n-1)/2 is insane, Any inspiration to come up with that?

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

          I saw this problem and immediately coded brute force for $$$n=5$$$ and $$$k=3$$$ and the first one that came out was that construction

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

          It comes by try & error so I can't tell exact step, but I tried to match $$$(1,4,7)$$$ first, suddenly cames up my construction.

          Maybe $$$(1,2,3,4,5,6,7)$$$ + (shift) leads the difference of the sum of two permutation $$$+2, +2, \dots, +2, -n+2, +2, \dots, +2$$$ (and under odd $$$n$$$, this works) is the decent way?

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

          I didn't manage to solve E during contest (I was really close, but I missed a few simple cases, like n = 1 and forgot about the cap for evens). I did get something very close. But basically once you realise that you can do all evens up to n! you can come up easily with "maybe if I can figure out a solution for 3 then it will work". And then you realise that you are looking for something that once you add 1 2 3 ... n it makes the same thing, you get the idea that you make something where the sum increases by 1 every time. I still had some trouble, but then I thought it would be easier if I just do every 2.

          So for every 2 I could do for 7:

          4 5 6 7

          1 2 3 4

          that would add up to 5 7 9 11

          and then the rest complete the sequence. So my own solution for 7 was:

          4 1 5 2 6 3 7

          1 5 2 6 3 7 4

          7 6 5 4 3 2 1

          Then it's somewhat obvious that 4 = 7 / 2 + 1. Then it was easily expandable as start for n / 2 + 1 for the first one.

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

    why is this getting downvoted

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because the problem E is neither nice, nor beautiful.

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how you rate a problem can be subjective, however, why would you take it out onto someone else who's not involved in setting it?

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

Nothing could be worse than losing rating on my birthday :(

Edit: problems are nice, I choked on H with some cases like 1 3 105 63 45 and what I missed is just enumerating the GCD of all picked numbers...

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

    happy birthday! :)

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

    Happy Birthday!

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

    Happy birthday tho!

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

    Well a gain of 0 is better than any loss I suppose. Happy birthday!

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

      Yeeeees! I’m so happy that codeforces give me this non-negative delta as my birthday gift, and my solution for H works after fixing the bug. Thank you! OvO

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

My God!

I don't know; maybe as an Iranian I would have preferred not to take these internal disputes to CF and resolve them by ourselves!

Of course, I definitely didn't want a few one-sided people talking about it, and I'm happier that both sides' opinions were presented.

But in the end, the beauty of the previous comments was lost in this kind of discussion and debate....

»
10 days ago, # |
  Vote: I like it +92 Vote: I do not like it

AT 2:53 OF CONTEST TIME THE DIFFERENCE BETWEEN TOURIST AND ORZDEVINWANG WAS 32 POINTS. TOURIST NEEDED TO HACK SOMEONE AND HE MANAGED TO DO SO 8 SECONDS BEFORE THE END OF THE CONTEST!!!!!! BUT ORZDEVINWANG SOLVED G2 3 MINUTES BEFORE THE END OF THE CONTEST, SECURING THE FIRST PLACE!!!!! WHAT A DRAMA OMGOMGOMGOMGOMGOMGOMGOMGOMGOMGOMGOGMOG

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

The problems were nice, though I feel like I solved something very similar to F a long time ago on Codeforces (I didn't have time to solve it though, I spent too long on implementing D and E). Also, they have very nice pictures :D Do you think that they are AI generated? They are very intricate but I don't see any obvious AI artifacts. Otherwise, big respect to the artist who made them.

»
10 days ago, # |
  Vote: I like it +21 Vote: I do not like it

orz orzdevinwang. Also IF orzdevinwang didn't solve G2, then tourist would have won by doing a successful hacking attempt at the last minute, that's crazy.

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

Is it true that in H the max size of the answer is 3? And does it have randomized solution?

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

    The max size of the answer is 6. let $$$x=2\cdot3\cdot5\cdot7\cdot11\cdot13$$$, then $$${\frac{x}{2},\frac{x}{3},\frac{x}{5},\frac{x}{7},\frac{x}{11},\frac{x}{13}}$$$ is a valid set

  • »
    »
    10 days ago, # ^ |
    Rev. 4   Vote: I like it +14 Vote: I do not like it

    Here is the rough sketch for H.

    This is how we can characterize all possible linearly independent sets $$$a$$$.

    First find a set of distinct primes $$$p_1,p_2,\ldots,p_k$$$ and let the gcd of all the $$$a$$$ be $$$g$$$. We will write $$$P = \prod p_i$$$ as the product of all the primes here.

    Then we can construct a linearly independent set $$$a_1,a_2,\ldots,a_k$$$ where $$$a_i$$$ is a multiple of $$$\frac{gP}{p_i}$$$ but not $$$gP$$$.

    For each linearly independent set, you can find a corresponding $$$(g,p_1,p_2,\ldots,p_k)$$$ that satisfy the above constraint.

    Then after brute forcing everything, you realize the the number of possible $$$(g,p_1,p_2,\ldots,p_k)$$$ with $$$k \geq 3$$$, $$$g \mid P$$$ and $$$\frac{gP}{\min(p_i)} \leq 10^5$$$ is at most 500k or something. So you brute force everything. I had to use a bunch of constant opts to pass because my code is shit.

    Checking answer is at least $$$2$$$ can be done in $$$O(n \log n)$$$.

»
10 days ago, # |
  Vote: I like it +31 Vote: I do not like it

What's with the constraint of A? I see a lot of people passed it with brute forcing, but they're quite close to the time limit, while I got TLE and I suspect it's because I used long long instead of int.

I don't see why it couldn't be much higher so that no brute force solution could pass, or be much lower so that every brute force solution could pass.

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

Why are there few pretests on problem D and E? I'm worried that my solution won't pass the system tests.

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

Problem C was nice (although very standard dfs problem). D wanted me to kms.

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

    how to solve that?

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

      C or D?

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

        C

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

          I applied DFS here. Firstly, i marked all the non '?' boundary cells bad if they were actually making the pointer out of bound (for example, if a[0][0] = 'U', this is bad cell). Now, I just applied dfs from an unvisited cell. For the question mark, we can replace it with either of the 'L', 'R', 'D', or 'U'. Hence, if any of the four gives me a good answer, I'll take that, otherwise I'll mark that cell as bad. For the explicit cells, like a[i][j] = 'L', it will be marked based on dfs(i, j - 1).

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

      Problem C (my solution)

      1. Model each maze square as a node in a graph and connect them using the info given
      2. Realize that for each connected component of the graph, whatever node u start from will always give u the same end point

      Start with your answer = n*m. Perform a DFS from each node and find the end state of the BFS from each node (either an infinite cycle, a question mark node, or an escape). If a node leads to an escape, subtract 1 from your answer. For the question marks, check each adjacent grid square. If the destinations of all adjacent squares are out of bounds / escape, subtract 1 again from your answer. Done! My submission at 294079080. Reply if you have more questions.

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

        Never thought it would be a graph problem, thanks for your explanation :P.

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

    I was able to solve D, but chocked on C :(

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

      I too choked on C, but figured out that I was making a silly mistake. I was running if-else loops for the '?' marked cells instead of four separate if loops. This costed me whole hour lmao. For D, I was trying to first put all the 0's in correct positions, then 1 and 2's will eventually become easy to swap (I failed miserably).

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

How to solve F? I cant find any clear approach to solve this problem

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    Firstly, for simplicity, redefine the special conditions to be in terms of the number of rubies/sapphires in your satchel (not chest). Then add dummy states $$$(0, 0)$$$ and $$$(n, m)$$$ for convenience (we won't double value at these though).

    Define dp states to be $$$dp[i]$$$, which is the total sum of value of your satchel across all ways you can reach the state defined by the $$$i$$$-th condition.

    To solve this dp you will firstly need to define some ordering on the conditions so that when evaluating some dp state, all the states that it depends on have already been evaluated. Just sort by $$$x + y$$$.

    Then, the transition from state $$$i$$$ to state $$$j$$$ will correspond to the ways you can go from state $$$i$$$ to state $$$j$$$ without visiting any other special condition state in between.

    Computing the number of ways you can go from state $$$i$$$ to state $$$j$$$ (where $$$i$$$ occurs before $$$j$$$ in the topological ordering) without visiting any intermediate special condition state is easy and can be done using inclusion exclusion in $$$O(n^3)$$$. Call this $$$w[i][j]$$$.

    Also define the total number of ways for us to go from state $$$i$$$ to $$$j$$$ to be $$$g[i][j]$$$. This can be computed in $$$O(1)$$$ using simple combinatorics.

    Define the addition in value for going from state $$$i$$$ to state $$$j$$$ without any intermediate doubling to be some $$$h[i][j]$$$.

    Then, the dp formulation for state $$$i$$$ is:

    $$$dp_i = 2 \cdot \sum{dp_j * w[j][i] + g[0][j] * w[j][i] * h[j][i]}$$$

    (where $j$ occurs before $$$i$$$ in the topological sort)

    All states will be evaluated in $$$O(n^2)$$$.

    The final answer is the value of the dp state corresponding to the the state $$$(n, m)$$$ divided by the total number of ways to go from $$$(0, 0)$$$ to $$$(n, m)$$$, which is just $$$\binom{n + m}{n}$$$.

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

      Can you explain more about how to calculate $$$w(i, j)$$$ using inclusion exclusion, I still didn't get this part.

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

        $$$w[i][i] = 1 \; \forall \; i$$$.

        $$$w[i][j] = g[i][j] - \sum_{k} {w[i][k] \cdot g[k][j]}$$$ (here $$$i$$$ occurs before $$$j$$$ and $$$k$$$ occurs between $$$i$$$ and $$$j$$$ in the ordering)

»
10 days ago, # |
  Vote: I like it +6 Vote: I do not like it
meme on C
»
10 days ago, # |
  Vote: I like it +68 Vote: I do not like it

I liked F. However E is bad.

(1) I believe it made the contest unfair that one sample testcase was silently added. What you should have done is to make a clarification as an annoucement instead.

(2) The essential part had appeared multiple times — IMO 2009 Shortlist C2 and UTPC2023 and possibly many others. The "distinct" part does not add fun (perhaps personal opinion).

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

who can tell me why runtime error pleaseYour text to link here...

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

294071265 this gives runtime error on pretest 8 for problem C . Can anyone tell what is the reason . I have not seen similar verdicts in any other solutions , so I am curious what caused this error ?

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

    have you considered what would happen if dfs(i, j) went out of bounds?

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

      How can this even happen , for all border elements which are overflowing i have assigned visited =1 and verdict=-1 initially only. Can you explain or give example

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

How to solve D ?

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

    What I did was iterate until the columns are sorted. On each iteration I:

    1. Swap the 1 that is furthest to the left with the 0 that it furthest to the right until all 0s are to the left of every 1.

    2. Swap the 2 that is furthest to the left with the 1 that is furthest to the right until all 1s are to the left of every 2.

    I did have to use a set to store the indexes otherwise it would TLE.

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

    If there are only $$$0$$$'s and $$$1$$$'s or only $$$1$$$'s and $$$2$$$'s, just swap the values in the way Leongg wrote.

    If the array contains all three numbers, then you must put all the $$$2$$$'s to the rightmost part of the array or (if more than half elements in the array are $$$2$$$'s) put all the $$$0$$$'s to the leftmost indices. If you have to swap $$$1$$$ and $$$2$$$ or $$$0$$$ and $$$1$$$, then just swap them. Otherwise you must do an intermediate swap involving any (for example, first to the left) $$$1$$$ in the array. If there were $$$2$$$, $$$1$$$, $$$0$$$ at some indices, after these two swaps you will have $$$1$$$, $$$0$$$, $$$2$$$ on these respective indices.

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

I can't imagine how many people were blocked by $$$n=m=1$$$ in $$$C$$$ and $$$n=k=1$$$ in $$$E$$$...

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

    why is n=m=1 in C an edge case? I didn't consider this and it seems fine

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

      if you have all ?-s in the grid, then n=m=1 is the only case you will have 0 as answer. otherwise the answer is n*m always.

      but still depends on the implementation obviously, i failed it though

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

    Wrong answer on test 4 ...

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

    I realized right after the end of the contest is that the wrong with my code for $$$E$$$ is that I didn't handle the case where $$$n = 1$$$

    it really hurts 😢

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

A regular request to increase the memory limit to allow solutions in python. Going from https://mirror.codeforces.com/contest/2034/submission/294035798 to https://mirror.codeforces.com/contest/2034/submission/294041682

was neither insightful nor fun.

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

BRO I passed A with 999ms whats on about the tight TL

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

GreedyForces

»
10 days ago, # |
  Vote: I like it +37 Vote: I do not like it

idk how many CF rounds I have to do to stop wasting half an hour on finding N = K = 1 testcases on E and similar :v

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

    If you have a hard time figuring that out, then what am I supposed to do? I missed two test cases in E....

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      & I used "int n" instead of "long long n" and couldn't debug it though i had 1 hours left. :) sadlyf.

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

I FST-ed on A :( Why half allow O(t*a*b) solution

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

loved the statements, especially the characters. look forward to seeing this competition continue in the coming years!

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

TLE on A system testing because of define int long long

»
10 days ago, # |
  Vote: I like it -19 Vote: I do not like it

Loved the images :)

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

гослинг?

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

I still do not understand why I got TLE on A and B in the system testing while the other similar answers were getting accepted...

A: https://mirror.codeforces.com/contest/2034/submission/294007119 B: https://mirror.codeforces.com/contest/2034/submission/294033976

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

https://mirror.codeforces.com/contest/2034/submission/294091655

please someone help me in figuring out whats wrong in my code?

please!

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

Hoping to get my first t-shirt(among Randomly choosen 50 participants)

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

This is my code for question A but it has not been accepted and showing TLE . How is this possible. I have reviewed my code thoroughly and believe it is correct .The code should definitely work as the constraints are — (1≤a,b≤1000) and (1≤t≤100). Many with same logic have their solutions accepted. I kindly request re-evaluation of my submission.

Submission Id — 294008048

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "Debugtemplate/template.hpp"
#else
#define debug(...)
#define debugArr(...)
#endif
#define int long long
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define mp make_pair
#define F first 
#define unmp unordered_map<int,int>
#define S second 
#define all(x) x.begin(),x.end()
#define sortasc(x) sort(all(x))
#define sortdes(x) sort(x.rbegin(),x.rend())
#define f(i,ind,n) for(int i=ind;i<n;i++)
#define PI 3.1415926535897932384626
const int mod = 1000000007;

void solve(){
    int a,b;
    cin >> a >> b;
    for(int i=min(a,b);i<=a*b;i++){
        if(i>=a || i>=b){
            if(i%a==i%b){
                cout << i << endl;
                return;
            }
        }
    }
}
#undef int
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
// freopen('input.txt','r',stdin);
// freopen('output.txt','w',stdout);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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

    Your solution works in $$$O(tab)$$$, with the constraint the worst case is $$$10^3\times 10^3\times 10^2=10^8$$$.

    However, the % operator has a large constant factor, which might case TLE in this case.

    #define int long long also slow down your code a little bit.

    PS: your code runs for about 2700ms on AtCoder (usually faster than codeforces) in about a $$$8\times 10^7$$$ total product, which is within the constraint. It would definitely TLE in the worst case here.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    problem con see hi

»
10 days ago, # |
  Vote: I like it +27 Vote: I do not like it

The fact that the glorious history of Iran and amazing myths were mentioned in the text of the questions made me proud that I was born in Iran. I hope this beautiful work will be repeated later.

»
10 days ago, # |
  Vote: I like it +9 Vote: I do not like it

unable to view the editorial

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

hello everyone do you know how to get job because i was recently graduated i don't know what to do

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

This contest gave me 120+ delta and made me a Specialist <3 standings

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

can anybody give me the id of this contest

»
9 days ago, # |
  Vote: I like it +9 Vote: I do not like it
»
9 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Nice problems! F2 and H are nice, even though I wasn't able to debug the latter in contest time :(

On a side note: Why insert the image in the middle? It randomly divides the statement into two parts, which can be really annoying when checking to see if you have missed something.

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

Runtime Error

AC

can someone explain why the first one gets Runtime error while the second code gets accepted?

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

C is too implementation heavy.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    idk its pretty standard implementation, you probably just need to do more dfs/bfs problems

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

When will we know if we got tshirts or not?

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

Today I received this message:

Spoiler

This is unfair decision. The only similar parts of this submissions: mine, studboy — is parts with sets, which is not the main logical part. Main ideas looks quite similar, but ways of solving are different. Hope this misunderstanding will be fixed.

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

    Hello, Timophey!

    Detecting similarities between codes and marking them as potential cheating cases is not something handled by the problem authors. In fact, we aren’t informed when these checks are performed or who ends up being flagged as a result.

    This process is part of the system’s automated operations. I believe reaching out to KAN or contacting the appropriate individuals in charge might help resolve this situation for you.

    I’m sorry that I’m unable to assist directly with this matter.