Блог пользователя TimeWarp101

Автор TimeWarp101, 2 недели назад, По-английски

Hello, Codeforces!

NJACK — the Computer Science Club of IIT Patna is excited to invite you to ByteRace 2023Codeforces Round #845 (Div. 2) and ByteRace 2023 under Celesta — the annual Techno-Management Fest of IIT Patna.

The contest will take place on Jan/21/2023 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

Many thanks to all the people who made this round possible:

You will have 2 hours to solve 6 problems.

The scoring distribution will be updated later.

$$$\color{white}{\text{I love Kaori}}$$$

UPD: Scoring distribution: $$$500-1000-1500-2000-2250-2750$$$

UPD: Editorial

UPD: Congratulations to the winners!

Official winners:

  1. jiangly_fan_fan_fan_fan
  2. ducati
  3. xiachong
  4. FasterThanLight
  5. Remask_588_handles

Unofficial winners:

  1. noimi
  2. jiangly_fan_fan_fan_fan
  3. Nyaan
  4. ducati
  5. neal

First solves:

A: noimi at 00:00
B: neal at 00:02
C: noimi at 00:06
D: noimi at 00:09
E: noimi at 00:15
F: sjc061031 at 00:13

PRIZES: 30 hoodies (customizable with name) will be given to:

  • Top 20 Indian participants
  • Random 10 from top 100 (rank 21-100) Indian participants

Note: we will identify Indian participants through their flags and they may be asked for address proofs later.

See you all in the standings!

UPD: Here is the list of people who won hoodies. We will contact you all soon. Congrats!

Top 20 Indian participants

Random 10 from top 100 (rank 21 — 100) Indian participants

About Celesta

Celesta is the annual Techno-Management Fest of IIT Patna. Celesta conducts a variety of events in various technical domains. Some of these are open and free for all, with exciting prizes and goodies for the winners!

You can head over to our website and check it out for yourself!

Good luck!

 
 
 
 
  • Проголосовать: нравится
  • +268
  • Проголосовать: не нравится

»
2 недели назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
2 недели назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

As a VIP tester, I VIP-tested. Hope you enjoy the round!

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thanks Celeste for the contest! I appreciate it.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Congratulation to all participant.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Good luck to everyone.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hello I am having problem with submission of Problem B.My Code runs fine on my local machine but its giving wrong answer when I tried to submit it here.. It seems to me the issue with compiler pls look into this..

    • »
      »
      »
      2 недели назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      There is no issue with the compiler. Check your code for inconsistencies that may be leading to undefined behaviour. Try custom invocation to find the bug.

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I just changed the datatype from long to long long and everything worked fine now.

»
2 недели назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

As a problem setter I set problems.

शुभकामनाएं

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope the competition is not too difficult.

»
2 недели назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

omg Spring Festival Eve round

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • Q1: Why only for the Indian?
  • Q2: Why hoodie? Why not any expensive prize?
»
2 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

omg new year eve round

»
2 недели назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Omg the round i tested is tomorrow. Hope you guys have fun!

»
2 недели назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

I am going to win this round. Bad luck to all losers!

»
2 недели назад, # |
  Проголосовать: нравится -105 Проголосовать: не нравится

Wtf with this indian rasism? Why all indian contests give prizes only to indian participats?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    They are Indian setters. They can't send prizes to other countries because it costs too much.

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится -91 Проголосовать: не нравится

      Bla bla bla. You (indians) are the only one in this world, who are doing this. What a shame.

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится +30 Проголосовать: не нравится

        I am not Indian and I'm not saying whether they are right or wrong. I'm just saying what setters say in their comments usually.

        • »
          »
          »
          »
          »
          2 недели назад, # ^ |
            Проголосовать: нравится -30 Проголосовать: не нравится

          Well code ton also gives prizes here and there.
          Its only for indians that it cost so much.
          stop talking Raito_Yagami

          • »
            »
            »
            »
            »
            »
            2 недели назад, # ^ |
              Проголосовать: нравится +13 Проголосовать: не нравится

            Ton rounds give crypto currencies. This is different. I am not defending them nor am I attacking them. I am only stating what setters say when someone asks them about this. Please stop.

            • »
              »
              »
              »
              »
              »
              »
              2 недели назад, # ^ |
                Проголосовать: нравится +23 Проголосовать: не нравится

              An Indian round without an Indian-rascism-shitposting thread is like a river without water. Sun Tzu | The Art of War

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        I am not sure why you are so invigorated by this. In this round, 2 packages were given to two participants in Vietnam and the contest organiser was Vietnamese.

        Please understand that this contest (including most of the Indian contests I assume you were referring about and the Vietnamese contest I mentioned above) are not sponsored, so they are giving prizes from their own money. Shipping costs are a lot, so the prizes are confined to the contest's country.

        Also, Codeforces is meant to be a rich and diverse platform for coding, not a way to get prizes. If that is your goal, I have a list of excellent gift stores I am sure you would like.

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It seems that awards have nothing to do with people of your moral character.

  • »
    »
    2 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

    I was part of organising similar events in previous years, generally sending prizes requires approval from college professors and they denied to approve the transactions for overseas participants since it was "costing too much". Too much pain to convince them for anything. Later on we did send amazon gift cards to overseas winners but couldn't get approval for some prizes :(

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck and have a good time! See you in the standings.

»
2 недели назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

I would have been top1 in this contest but unfortunately wont be able to participate.

»
2 недели назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

As a problem setter, I discovered that, upon giving this contest, your IQ will increase $$$555$$$ times.

PS: The problems are super fun. Hope you all will enjoy solving them! Don't forget to read them all :)

»
2 недели назад, # |
  Проголосовать: нравится -44 Проголосовать: не нравится

Clashing with Leetcode round :/

»
2 недели назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Setters are from my college, so excited. Best of luck people!

»
2 недели назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I need pants!

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

--

»
2 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hype overload!!

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All the best everyone

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Excited for the Saturday thrilll...

»
2 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Good luck to everyone participating! Hope you enjoy the problems.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please i want alot of advices to know how to increase my rating i am using c++ and I don't know how to do that if you have any advice tell me and I will do thank you for your help if you will tell me practice tell me from where and what is the rating of this questions

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Happy Lunar New Year!

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope that I get a positive delta in this round :|

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello I am from India's neighbor country Bangladesh

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping to reach pupil this round.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

so excited for this round!

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why only Indian participants?

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All the best

»
2 недели назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Nobody wants to watch the boring Spring Festival Gala.A CF round is much better compared to the bad shows.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

all the best everyone . have a good and learning contest for all.

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

As floormate of the problem setters, I can confirm that this round will be really interesting.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What prizes do u have for Belarus people?

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Looking forward to the round !

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I need expert back.

Edit: It's done

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg Spring Festival Eve round

»
2 недели назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Want to hear AwakeAnay side story.

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

#845 is about to begin and there's no official editorial for #844

»
2 недели назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I have a bad feeling about this round

»
2 недели назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to perform well in the contest

»
2 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What's the scoring distribution? It's still not updated.

»
2 недели назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

I sincerely wish people all over the world a happy Spring Festival! In the new year, I hope you can achieve everything you want, be healthy and have good luck.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great to take part in a Codeforces Round while watching the boring Spring Gala! Wish everyone and I have a great positive rating delta as well as a great new year!

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is the first time I have seen the output of the first token -1. (Problem- C, Example input:output)

»
2 недели назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Congratulations to participants for participating on Chinese New Year Eve.

»
2 недели назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

A wise man once said, "When you're not afraid of rating, you'll be red."

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am having issue with submission of problem B. When running it on my local machine it is giving right answer but when I submitted the code it is printing different output. Please look into this..

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    You should try it in custom test and check if you are having the same output as your local machine or not.

»
2 недели назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

Congratulations to yzc2005 for making submission 190000000 (link won't work until after contest).

»
2 недели назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

Trash Indian rounds with very standard problems. Bad E and F.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится
    • Makes Codeforces account
    • Solves all 6 problems in a little over an hour, getting 5th official place
    • Calls it a trash indian round with standard problems
    • Refuses to elaborate
    • Leaves
  • »
    »
    2 недели назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    i do not see issue with standard problems, earlier codeforces used to give standard problem variations only if you pickup few age old problems. It is just since recent 4-6 years that more constructive and math problems are coming and i do not see any issue in both standard/adhoc as they both enhance problem solving/approaching skill.

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Problem C is interesting.

And how to approach D?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    tree dp

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How exactly?

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        The answer is 2^(n-1)*sum(the max depth of the subtree with root i) where i iterate among all vertexs. (the depth of leaves is 1, the depth of parents of 1-depth vertexs is 2, and so on)

        • »
          »
          »
          »
          »
          2 недели назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I guessed this solution after an hour of doing random stuff on the sample case :/

        • »
          »
          »
          »
          »
          2 недели назад, # ^ |
          Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

          I explained it like this: If at least of the children has a possibility to be a 1, that possibility has to be 50%.

          Any number of XORing 50% possibility of 1 still gives 50%, so as long as one child could have a 1 in the previous round, we got a 50% chance of getting a 1.

          For leaves it's just 50% one time, then they become 0. For a node one above that, once all children are 0, it also becomes 0 the next round. So if e.g. the longest child chain has 2 children, we have to take 50% chance 3 times, 1 for the start, and 2 for the 0 to trickle up through the length 2 children line.

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Try to find the solution for every pair of nodes and times and then you'll soon realize that they are all the same before becoming zero.

  • »
    »
    2 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Hint
    Hint 2
    Solution
  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Did you solve C? What was your approach?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Thank you for the appreciation, it means alot. 🧡

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Lol, problem F seems to be standard

»
2 недели назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I didn't do as well as I wanted but I enjoyed the contest, thanks setters ! :)

»
2 недели назад, # |
Rev. 9   Проголосовать: нравится -24 Проголосовать: не нравится

Problem D can be solved by tree dfs(we need to find the maximal path from every vertex to it's childs), and we can solve E with any template for finding strong components (we just need to add an negative weight edge v--(-w)-->u for every u--(w)-->v, representing the edge can be reversed if cost>=w, and binary search for cost), but I could not solve C.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Problem C is just two pointers :)

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't think D was that trivial as it was pretty hard for me to see the idea. Or maybe it's just a skill issue on my part.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same... C took me 1 hour and a half ( I didn't see that I WA'd B cuz I didn't check submissions) ☠️ but D took me like 3 minutes to think of the solution and 10 minutes to code (though this was after the contest already ended so I can't submit.)

    sha256 of my sol
»
2 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to prove Problem B solution?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    n!*n*(n-1)

  • »
    »
    2 недели назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    see below for my attempt to prove

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I did the same thing. I saw that each permutation gave the same answer.

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      For the proof, 1 2 2 1 consider the permutation, if you put 3 in to anywhere
      1 2 3 3 2 1
      1 3 2 2 3 1
      ...
      it will increase the inversion count by (3-1) * 2

      Because if for the left half its inversion count is j, for the right half it will be 3-1-j, plus all elements on the right half have inversion with the left 3, overall it will be j+3-1-j + (3-1) inversion. For m, it will m-1+m-1 = (m-1)*2 inversions. Summing this for all m <= n gives n * (n-1)

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hint
    Answer
  • »
    »
    2 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Suppose $$$p_i,p_j$$$ such that $$$1\le i<j\le n$$$ are distinct elements of the permutation. Their reflections are $$$p_i',p_j'$$$, respectively. If $$$p_i<p_j$$$, then they contribute only $$$2$$$ inversions because $$$p_j>p_i'$$$ and $$$p_j'>p_i'$$$. If $$$p_i>p_j$$$, then they also contribute only $$$2$$$ inversions because $$$p_i>p_j$$$ and $$$p_i>p_j'$$$. Thus, for every pair of distinct indices $$$i,j$$$, they contribute $$$2$$$ inversions. There are $$$n\choose2$$$ ways to choose pairs of indexes. So, the answer is $$$n!\cdot{n\choose2}\cdot2$$$.

  • »
    »
    2 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Consider a specific permutation of size $$$n$$$. For any two different indices $$$i$$$ and $$$j$$$, either they form an inversion in the original array OR they form an inversion in the reverse array. Each such pair will contribute exactly one such inversion (note that there are no duplicates in the original array, since it is a permutation). There are $$$\frac{n(n - 1)}{2}$$$ pairs of indices.

    This will already count all inversions that are between indices that are either both in the original array or both in the reverse array. All that's left is to count inversions where one index is in the original array and the other index is in the reverse array. Because both the original and reverse arrays are permutations, it's easy to count them: the value $$$k + 1$$$ in the original array will have $$$k$$$ values smaller than it which are present in the reverse array. Thus, the total number of such indices is $$$\sum_{k = 1}^{n - 1} k = \frac{n(n - 1)}{2}$$$.

    Add them up and we have exactly $$$n (n - 1)$$$ such inversions. This is for a single specific permutation, without actually depending on what the permutation is. Since there are $$$n!$$$ permutations, the required answer is $$$n! n (n - 1) \bmod (10^9 + 6)$$$

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Consider any pair of numbers $$$i$$$ and $$$j$$$, such that $$$i$$$ is to the left of $$$j$$$.

    In the final array you will have ... $$$i$$$ ... $$$j$$$ ... $$$j$$$ ... $$$i$$$ ...

    You can see that no matter which value is higher, each pair will give 2 inversions.

    There are $$$ \frac{n(n - 1)}{2} $$$ pairs, each will contribute $$$2$$$ inversions per permutation and there are $$$n!$$$ permutations

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    All permutations of a given n have the same number of inversions (write a couple down and you'll see why). The number of inversions for a single permutation of n is the Gaussian sum of n — 1. For concatenated permutations, it is double the Gaussian sum. So, final answer is just n! * n * (n — 1).

»
2 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

how to solve problem C?

  • »
    »
    2 недели назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    Sort the input array $$$v$$$. Keep track of 2 pointers $$$left$$$ and $$$right$$$, initially both at the 1st position of the array, and keep a map that stores the frequency of all the divisors from $$$v[left]$$$ to $$$v[right]$$$. If the size of the map is not equal to $$$m$$$, then increase $$$right$$$ and update the map, otherwise increase $$$left$$$ and update the map. Keep track of the minimum difference between max and min while iterating.

    • »
      »
      »
      2 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      This approach just kept giving me TLE :( 190022533 What is the complexity of it? N*sqrt(N) should pass those limits or am I wrong?

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Try using a vector for divisors instead of set, set adds complexity for no benefit.

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      calculation of divisors of all array elements take time;O(n√n) approx;10^7,will it be accepted?in contest i thought it will give TLE

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        yeah same thought

      • »
        »
        »
        »
        12 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's safe to assume that $$$10^8$$$ operations can be performed in one second when the operations are basic (add, subtract, multiply and divide as well, the division is a bit intensive though).

        Reference

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve b

  • »
    »
    2 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Consider three cases separately,

    case 1: where the inversion is completely in the first half (i.e. the original permutation),

    case 2: where the inversion is completely in the second half (i.e. the reversed permutation),

    case 3: where one end of the inversion is in first half and the other in the second half.

    The answers for these cases will be t+(nC2-t)+(1+2+3+...+(n-1)) where t will depend on the permutation. But as you can see, the sum is simply 2(nC2) which is same for each permutation of length n. There are a total n! such permutations. So the answer is n!*2*nC2 which is n!n(n-1).

»
2 недели назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Due to Codeforces not loading properly near the start of the contest, some participants may have accidentally submitted the same code multiple times. In my case, for example, I used the main site to submit and got a 502 Bad Gateway, so I switched to one of the lightweight versions (m1, m2, or m3, not sure exactly which one) and submitted over there instead, not realizing that my first submission actually went through. This was treated as a resubmission and I lost 50 points because of it.

Is it possible to make any adjustments such that these kinds of duplicate resubmissions are not penalized? Note that the main site normally blocks the user from submitting an identical code twice, so I think it would be perfectly justified to remove such identical codes that did manage to get through (due to using the lightweight site, which implies technical issues that the participant should not be punished for experiencing).

Here are my submissions: 189973808 189973881.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was stuck in problem C for a long time, any intuition on how to solve it?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hint
»
2 недели назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

i swear there is like no other solution for problem C other than annoying brute force and also to make the execution somehow fast

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My code of problem C wrong answer on Test #2, but when I tested it with my another code that TLE on test #3, all of the datas I made, the answer between them is same. Could anyone give me a data that my code will give a wrong answer ? :(

my submission

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Read the problem statement for E as the minimum weight of edge reversal weight so that every node is reachable from one another. IMO this version seems cooler (and harder) than the original one.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    It's as simple as the original problem (both versions need to check strong components). The original is checking "whether there is only one component with 0 in-degree", and your version is checking "whether there is only one strong component".

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why did 189996915 not pass? I thought since ind and fac[n] are modded M already, ind, fac[n] <= 1e9+6. and (1e9+6)^2 <= max ll??

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is d tree dp? I couldn't really think of a solution, how do you solve D?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    No, it's math. For each node to be equal to 1, calculate total no. of arrays for which it is possible. Also find its relation with its height.

»
2 недели назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

The TL on F is stupidly high, a simple $$$O(n^2)$$$ passed: 190000292

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Maybe there's larger test in system testing…

    Also there's possibility that the problem setter forgot to disable O(n^2) solutions for Div2F.

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's very likely that there's a bigger test but anyone who is familliar with vectorization will assure you that 8 seconds is just way too much for this problem. Also what do you mean by "forgot to disable O(n^2)"? That's a huge issue if you can pass a problem with a naive solution. Not sure what the final time will be, but if it's low enough it would either mean that the TL is dead wrong or that perhaps the problem should've been scrapped entirely.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I hacked it, the system tests are too weak

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

      Optimized it, I wanna know if you could hack this one: 190039238

      Still, me being hacked doesn't change the fact that TL is absurdly big when only $$$O(nlognlogA)$$$ was intended in the first place.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone knows why simple dfs from first vertex in topological sort works in E? (for checking the condition)

As far as I know, topological sort only works for graphs without cycles

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    If you think about it, the first vertex after the topological sort is the one which will always belong to the first SCC (i.e. a SCC with 0 indegree). So, just checking whether all the other nodes are reachable from this vertex is enough for the problem.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I didn't see the constraint on n (problem D) carefully and set 100000 for the arrays. However, instead of getting RE, it got TLE ??? Just changing it from 100005 to 200005 made the program pass...

»
2 недели назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I liked problem D. It had such a simple solution (after thinking it through). Missed the submission by a few seconds tho ^^

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please look into my profile and suggest something, I don't know but cannot perform well for the last 7-8 contests. Please do recommend anything. It would be a great help. Thank you!!

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can't believe I screwed up the contest by not precomputing the divisor array globally as I did the question by finding out the divisor of elements for every array as I thought what's the harm, finding divisor is sqrt(a[i]) time complexity anyway --> worst mistake. What a sad feeling it gives when you could've solved the question but lack of knowledge or stupidity comes in the way. PS: 1. Learned something new 2. Won't be forgetting it ever again

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem E is a template of Tarjan.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Essentially what you want to find first is a subarray of numbers such that the number of factors of all numbers in that subarray is exactly $$$m$$$. Once you have done that, all we want to do now is to minimize the difference between the maximum and the minimum numbers in that subarray. You can do this by having $$$2$$$ pointers, and incrementing the $$$1st$$$ pointer towards the right while making sure that the number of factors remain $$$m$$$

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had a different approach from many , I sorted the array and then used a map in this map when i am traversing i take the factors of a[i] and then updated the map of these factor values by the value a[i] so in map if we have all elements from 1 to m i will see which is the minimum map value of 1 to m to find the element which must be used and then taking the difference and check if it is minimum till now.code->

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me find, what might be the issue with this submission for problem D?

190024130

Idea is to find the depth of each node and sum them. Finally multiple that by pow(2, n-1).

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hints for D please?

»
2 недели назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

system test when ?

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Here goes how solved A-F today in brief.

Upd: Add all problems now.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for those who need help with C,D you can find the video editorial here — https://www.youtube.com/@grindcoding. Happy coding!

»
2 недели назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

When will the System testing start? I have to cry myself to sleep also.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Guys, in Problem C, I wondered why example test case 1 turns out to be -1. It should be 0, isn't it?

I meant we can pick arbitrarily 3 or 7 because it's still divided by 1. Does the example explain that 2 <= m, why is that?

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you arbitrarily pick $$$3$$$ or $$$7$$$, it will be divisible by $$$1$$$, yes. But neither of them is divisible by $$$2$$$ or $$$4$$$. You need to find a multiple of each of the numbers $$$m = 1,2,3,4$$$, not just one of them.

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      so it means that all from 1 to m must be divided by a least 1 number in a[]?

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        one more thing, is this problem typically two pointer problem?

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        All numbers from $$$1$$$ to $$$m$$$ must be divisors of at least one number in your choice of the team

»
2 недели назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

why is it taking so long for system testing

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Main test? MikeMirzayanov

»
2 недели назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Speedforces

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can't wait to upsolve.System testing :(.

»
2 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

anyone solved C with binary search

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain your solution with binary search? I got WA with binary search.

    • »
      »
      »
      2 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      First I used seive to get the factors of all the numbers and used them in a map and I observed that the number of factors would not be more 125.

      Then I sorted the array.

      Then I binary searched on 0 to 1e18 (I took the upper bound randomly high) where for every mid I used sliding window to check if the given mid is possible or not .

      Then shifted the window accordingly.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why am i getting WA on pretest 2 for problem c : 190021791

»
2 недели назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

I submitted 2 times for B (due to fear of TLE for large test cases). I got low score and eventually my first attempt got skipped? Is it due to consideration of my second code or someone has the exact similar code to me... the major difference between both my codes is n/N but time is the major concern there. MikeMirzayanov

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my submission is not tested on main tests please look into it 190002478 TimeWarp101

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why this solution:190038867 for problem A is giving WA. Thanks.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    cout before cin

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In the case of N = 1 for some testcase, you do not cin >> A[i] for the vector A. Thus, you return before you have read input for the current testcase

»
2 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In D, I was memsetting a bool array of size 2*10^5 every single test case, which could have been 10^5 times. I'm surprised it got accepted. Is memset really that fast? Is it doing something magic in the background? https://codeforces.com/contest/1777/submission/190020821

»
2 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

when will be ratings updated?

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do C?

I think the solution is to binary search the answer,but I can't write the $$$\operatorname {check}$$$ function,because its time complexity is so high.

(sorry for my English)

»
2 недели назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

to me, C is too hard and D is too easy, I'm stupid

»
2 недели назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

i don't want to offend you but the datamaker of F have no brain?

»
2 недели назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

to me: D was easier than C

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I tried C and debugged all the way but I still don't know what kind of test case I didn't pass. Could anyone please help me? Thanks https://codeforces.com/contest/1777/submission/190058563

»
2 недели назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

my friend got 8000th standing, and i got 6600th, yet he still got more rating, i got my rating reduced he had his 9th contest this round and this was my 7th :/

»
2 недели назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

I got WA in Problem-C

Can anyone help me please.
My approach for Problem C:
  1. Sort the array A.
  2. Count and store all the multiples(1 to m) for all n elements. If all multiples from 1 to m are not exist in the array then the answer will be -1.
  3. Take two pointer L=0, R=n-1
  4. If multiples of the element in index L can be removed(all multiples from 1 to m still exist in rest of the array), then remove element from index L and increase L. Stop if we can't remove the element(multiples from 1 to m is not exist in rest of the array).
  5. Do the same from index R and decrease R untill we can't remove the element(multiples from 1 to m is not exist in rest of the array).
  6. Answer should be A[R]-A[L]
Example:
5 7
6 4 3 5 7
Here,
n=5, m=7
A=3 4 5 6 7
Multiples of
3->1 3
4->1 2 4
5->1 5
6->1 2 3 6
7->1 7
Frequency of the multiple 1, f[1]=5
As well as f[2]=2, f[3]=2, f[4]=1, f[5]=1, f[6]=1, f[7]=1
Now, L=0, R=5-1=4
remove A[L]=3 and change the frequency of the multiple
f[1]=4, f[3]=1
L=L+1
Then we can't remove A[L]=4 because frequency of 4 that is f[4] will be 0. So, we stop here and start from index R,
We can't remove A[R]=7 because frequency of 7 that is f[7] will be 0. So we stop.
The answer is A[R]-A[L]=7-4=3

My submission: https://codeforces.com/contest/1777/submission/190090177

  • »
    »
    13 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Check this test case n=4,m=5,a=[8 9 10 20]

    • »
      »
      »
      13 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you _Gawd_

      Later I did the same reversely in the array and had the minimum and still got WA.

      In your given case, n=5=4, m=5 A=8 9 10 20 Multiples of 8->1 2 4 9->1 3 10->1 2 5 20->1 2 4 5 Frequency of the multiple 1, f[1]=4 As well as f[2]=3, f[3]=1, f[4]=2, f[5]=2 Now, L=0, R=4-1=3 remove A[L]=8 and change the frequency of the multiple f[1]=3, f[2]=2, f[4]=1 L=L+1 Then we can't remove A[L]=9 because frequency of 3 that is f[3] will be 0. So, we stop here and start from index R, We can't remove A[R]=20 because frequency of 4 that is f[4] will be 0. So we stop. The answer can be A[R]-A[L]=20-9=11

      We will do the same thing in the array reversely,

      So, A=20 10 9 8 f[1]=4, f[2]=3, f[3]=1, f[4]=2, f[5]=2 Now, L=0, R=4-1=3 remove A[L]=20 and change the frequency of the multiple f[1]=3, f[2]=2, f[4]=1, f[5]=1 L=L+1 Then we can't remove A[L]=10 because frequency of 5 that is f[5] will be 0. So, we stop here and start from index R, We can't remove A[R]=8 because frequency of 4 that is f[4] will be 0. So we stop. The answer can be A[L]-A[R]=10-8=2

      The answer is Answer=min(11,2)=2

      New submission: https://codeforces.com/contest/1777/submission/190264458

»
11 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hey I find this Round has become unrated.Does anyone know why?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Temporary rating rollbacks are common. Generally, they need to recalculate rating changes (e.g., after identifying a significant set of cheaters). It should be updated soon afterwards.

    It's also possible that this contest was decided to be unrated due to some serious issues, but there was no announcement about this, nor did I see anyone discuss any such issue, so I think this is extremely unlikely. The contest should be rated; please be patient.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What the hell man...one more codeforces round that got unrated...i just noticed that the ratings have been withdrawn..this sucks man..it absolutely sucks

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why the ratings for this contest has been roll back?

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why the rating of this contest rolled back?

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

я никогда не использовал ideone.com, и искренно хочу сказать что ничего против правил не делал и и это просто какая ошибка или случайность, как доказательство я не знаю этого чувака которым у меня схожи код, пожалуйста восстановите мой рейтинг, это какая та ошибка

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi , I have got a Notification that my Soln. 190012662 of Prboblem B is coinciding with divyank_7701/190013952 . As Soln. of Problem B just needed an Obesrvation and after that a calculation of mathematicl Expression . Generally there is a standard function for calculation of Factorial taht's why the Soln. of Problem looks somewhat similar But it is not the same code for Sure. My ratings has been rolled back without any mistake of mine . I have not Shared and Published my code with anyone. I hope My ratings will be again increased , I haven't broken any Guidilines of the Contest.

»
10 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please update problem ratings