By awoo, history, 4 years ago, translation, In English

Hello Codeforces!

On Jan/29/2021 17:35 (Moscow time) Educational Codeforces Round 103 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 sometimesnaive 6 176
2 SSRS_ 6 184
3 MagicalFlower 6 251
4 hank55663 6 255
5 Strigon-12 6 276

Congratulations to the best hackers:

Rank Competitor Hack Count
1 stdmultiset 133:-79
2 Tsovak 98:-10
3 dapingguo8 68:-6
4 MohamedAboOkail 65:-3
5 peti1234 60:-1
3590 successful hacks and 2569 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Warawreh 0:01
B MysteryGuy2 0:04
C WZYYN 0:10
D peti1234 0:09
E CoderAnshu 0:06
F - -
G iaNTU 0:57

UPD: Editorial is out

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

| Write comment?
»
4 years ago, # |
  Vote: I like it -90 Vote: I do not like it

Please please please don't make it as hard as today's contest :/

»
4 years ago, # |
  Vote: I like it -54 Vote: I do not like it

As a ......

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

Let the comments with "as a" begin

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

I am new to Competitive programming, codeforces made me fall in love with it! Thanks to you all amazing people!

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

    yes same

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

    i tried everything to find my interests and nothing felt like i enjoy doing them

    as i started CP on codeforces 2 months back i feel like this is all i want to do for the next large amount of my time :) really thankful to the best internet community

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

      Same brother, initially I thought to first finish all Data Structures and Algorithms and then start CP, but doing it simultaneously is much better and helps retain concepts easily. Every new coder should start doing CP. (PS: Only if you don't mind your ratings dropping and you trust yourself enough, that one day, you'll make it.)

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

    so Madara Uchiha saved you, huh.

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

As a participant of today's contest kindly make the problems easier...

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

I hope it will be a good round

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

I will die if there will be adhoc problems in this contest too.

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

    educational=(4problems or more)*adhoc XD

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

    what is adhoc?

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

      adhoc problems usually ask you to construct or to build something. Usually those problems can be solved without knowledge of algorithms. For example, you can check problem F from codeforces Round 640 div4. This is an example of ad-hoc problem.

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

      The problems on which you die thinking which algorithm to use while contest and then after looking at the editorial think .. "wait ... thats it ?"

»
4 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it
FORTUNE COMMENT!
»
4 years ago, # |
  Vote: I like it -21 Vote: I do not like it

My current rating is 401 will I be rated in this contest?

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

I am a newbie, it really made me happy that I could solve few problems. Looking forward to upcoming contests!

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

    those who dont want jobs out of it will loose hope soon

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

      Well not getting a job when you are working hard is depressing but you have to believe in yourself, it can do miracles

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

        well, recently a newbie girl I know received an offer from FAANG.

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

          I am neither a newbie nor a girl, darkness awaits me.

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

      I'm in high school and do CP. And there are many others who don't want a job out of it. Problem-solving using DSA is fun!

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

        well i am 2 nd year electrical engineer i do it to keep my brain sharp but our job is decided by such factors we tend to target on this site it all connects.and if u cant get anything out of it u will decay soon thats what i meant

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

          Depends on how you define 'anything'. For many people, there are more things in life apart from getting a job.

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

I hope i will become expert today..

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

Hope to become specialist today

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

Hope the tasks aren't too hard, hope everyone can get a rating which can satisfy you :)

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

There should be a third button IMO XD

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

    There was but it got deprecated: HackForces. Now it's only present on Topcoder with name TopHacker.

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

      Doesn't look like it.

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

        I meant for usual div 2 rounds. Usually educational rounds have more hacks because of longer and separate hacking phase.

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

    MathForces!

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

    And a forth: MathForces...

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

I hope i can solve first 2 problems quickly :)

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

Writing educational contests is really good way to develop. Thank you for this contest and good luck to everyone!

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

hoping it to be a hard contest (and not containing math only ;-;)

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

(

)
»
4 years ago, # |
  Vote: I like it +251 Vote: I do not like it

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

    This feels deep. You have my upvote sir

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

    This is the most relatable meme I've seen on codeforces. Especially after yesterday's contest and today's.

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

Waiting for the contest which would take me to specialist :)

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

It will be a wonderful contest. Best wishes!

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

Hoping for a good contest!!

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

Giving a contest after long time today ! Fingers Crossed..

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

Best of luck to all :)

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

A and B kinda sucked ngl

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

    before contest i was confident that i will be successfull in protecting my specialist badge. after contest i am confident i will be successfull in getting demotion to pupil

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

    Yeah, but I thought C and D made up for it!

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

    Fu**ing B costed me 7 WA because of floats.

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

      That is why you should always work in integers if possible, if you are comparing $$$\frac{a}{b}\ge{\frac{c}{d}}$$$, compare $$${ad\ge{bc}}$$$ instead. Watch some people like Errichto and you will pick up these things, it helps a lot.

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

B — balanced

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

I wasted literary 1 hour on problem C because I forgot typing else... GG I will always be silver...

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

How to solve C?

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

    I solved C considering three cases:

    1. If we are at index 0, we only have one option, i.e. to start a cycle from here.

    2. If we are at the last index, we only have one option, i.e. to end the current cycle.

    3. If we are at an index in the middle: We check if b[index+1] == a[index+1].

    • If this is true, then we need to terminate the current cycle and start a new one
    • We again have 2 options here. We can either continue the current cycle with the existing length summed with the Number_of_vertices[index] - 1 - (b[index+1] - a[index+1]).
    • The next option is to start a new cycle from here with length b[index+1] - a[index+1].
    • The reason why this is always true is that the rest of the cycle remains unaffected by the choice we make at this index.
    • Another option is to terminate the current cycle here after adding Number_of_vertices[index] - 1.
    • Remember to add 2 every time you expand the current cycle to count for the edges used to link the chains together.

    Link to code: https://codeforces.me/contest/1476/submission/105933562

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

      I did same still got WA on test case 3, Can you help? The code is easy enough to understand.

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

        Here's my code see if that helps.

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

        Firsty, I think that you have messed up the implementation in the if-else condition.

        • It is safe to swap b[i] with a[i] if a[i] > b[i[. This will help to get rid of those abs().
        • Also you are adding 1 - a[i+1] + c[i] - b[i+1] which should actually be c[i] - 1 - b[i+1] + a[i+1].
        • Lastly, you are not considering the case when we can start a new cycle from this index with length b[i+1] — a[i+1].
        • I corrected these things in your code and submitted which gets accepted.

        Link to the submission: https://codeforces.me/contest/1476/submission/105949955

        Hope it helps!

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

    You can use some dp to store maximum length cycle including all vertices of a[i] as ans[i].

    See my solution:https://codeforces.me/contest/1476/submission/105907608

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

    It can be solved by dp; firstly, let dp[i] denote the longest length at ith chain, "the longest length" means the longest length you can get before the cycle is formed, so we can get dp[i]=max(dp[i-1]+c[i]-1-abs(a[i+1]-b[i+1])+2,abs(a[i+1]-b[i+1])), then we update the answer by dp[i-1]+c[i]+1. one thing to be noticed is that when a[i+1]=b[i+1], dp[i] should set to 0.

    #include<bits/stdc++.h>
    #define ll long long
    #define pb push_back
    #define FULL(x,y) memste(x,y,sizeof(x))
    using namespace std;
    
    const int N=100005;
    int t,n;
    ll c[N],a[N],b[N],dp[N];
    
    int main() {
    	cin>>t;
    	while(t--) {
    		cin>>n;
    		for(int i=1;i<=n;i++) cin>>c[i];
    		for(int i=1;i<=n;i++) cin>>a[i];
    		for(int i=1;i<=n;i++) cin>>b[i];
    		for(int i=1;i<=n;i++) {
    			dp[i]=0;
    		}
    		ll ans=0;
    		dp[1]=abs(a[2]-b[2]);
    		for(int i=2;i<n;i++) {
    			dp[i]=max(dp[i-1]+c[i]-1-abs(a[i+1]-b[i+1])+2,abs(a[i+1]-b[i+1]));
    			ans=max(ans,dp[i-1]+c[i]+1);
    			if (a[i+1]==b[i+1]) {
    				dp[i]=0;
    			}
    		}
    		ans=max(ans,dp[n-1]+c[n]+1);
    		cout<<ans<<endl;
    	}
    	return 0;
    }
    
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Was I the only one who went into C and D thinking that they are graph problems, but both of them turned out to be dp ones? :P

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

How to solve D?

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

    Note that the structure of the graph only depends on the parity of time elapsed. Therefore, we can use $$$(node, parity)$$$ as stage and use DSU to maintain the reach-ability between stages and the sizes of connected components.

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

    Make a left_c and a right_c array which represents the maximum number of cities city i can traverse that lie strictly on it's left and it's right respectively.

    Then, notice that if there lies a path b/w city i and city i-2, then city i can traverse all those different cities that city i-2 can because at time t and time t+2, all paths are exactly the same. If there just exists a path b/w city city i, and city i-1, then increment one to the left_c array for the city i. And, do similar things for right_c.

    Answer for the i_th city is left_c[i]+right_c[i]+1

    You can check my submission

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

How to solve A? I'm new here...

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

    take range of get the smallest number x with x*n >= k

    or if n > k : x*n >= ceil(n/k)*k

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

      How to think for such solutions?

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

        "disclaim: It took long time for me :("

        -the first observation is that the smallest value for n positions is : 1n,2n,3n,4n, ...

        say you have n = 3 and k = 11 => 1,6,9,12 , 15,... you can get 11 by replacing 4 by three 4,4,4,3.

        -so you can get any lower values of x*n by replacing on or more x by lower value

        you should take into account n > k

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

          Comment section is filled with amazing people! It's motivating :)

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

      nope.

      Lets consider two cases:

      1. n >= k. if n is divisible by k, you simply set everything to 1. otherwise, you set some of the numbers to 1, some others to 2, so that in effect you have added "enough 1s to make n divisible by k.

      2. n < k. There is no point in making the sum any bigger than k and by pigeon hole principal, at least one of the numbers will be ceil(k / n). As (ceil(k / n) * n) >= k, it suffices to subtract some amount from some of the numbers to make the sum equal to k.

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

Omg -141 delta for me

Question D is far more simpler to me compared to question B and C :/

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

    I had a terrible day too!

    At least some previous contests had interesting problems I could not solve and I got negative delta, but this one was Painfully pointless to me :(

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

my contest in 1 photo :

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

    the division with 1 huh? Yes it took me some time as well. But no worries mate I lost 1 hour on C not because I could not find the solution but just because I forgot a simple 'else' statement. Look at my submissions on C if you don't believe. Like what separates the successful from the unsuccessful I believe is just the ability of removing the blindness effect that I don't even know what casts it upon us. It's like we are in a MOBA arena and we have a passive ability of getting blinded for 1 hour randomly. We can be blind friends together hit me up if you ever want us to do a Virtual Contest together and then laugh at our blindness.

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

      Not really. First I tried binary search and now i am wondering what was wrong on that solution, after i found some interative solution but i used the wrong formula :) .

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

        Ah sorry I just realized you stuck on B and not A. My bad. Anw I solved B without binary search I would be very interested to see how it is solved with binary search.

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

          first you have to observe that the solution is to add some number just to p0. Now ,let x be the solution and you can find it with binary search. For each x, check if can be a solution. If not, have to increase x, otherwise ,decrease it. The article in EDU about binary search is very nice, I ve learned a lot from that one.

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

            Oh this is smart but it requires more complexity than the linear solution. Still very smart nevertheless. 105884577

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

            I just read you solution. It is linear as well. Oh I can see where it got hard maybe when you where trying to calculate how much to add. I just did a max there since the maximum is what you need. Damn I could rank up so much in this round had I been a little more careful.

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

              my binary search solution : CODE

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

                Yes so it is O(nlogn). It just instead of doing the division and checking for the modulo that I was doing you do the BS to find the correct value.

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

    Bro how did multiplying by 100LL instead of 100 get the answer in B ?

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

      because your variables are int, and 100*1e9 = 1e11 and this value for int is overflow

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

        If all variables and array are taken as long long. Will it still overflow ?

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

Don't you think the copying during contests is increasing day by day?Also there are many smurfs account in the contest. Affects rating of a lot of people

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

    Who is copying?

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

      AkashRamjyothi1 see his solutions

      105874881 : A

      105895241 : B

      105915359 : C

      105929955 : D

      while(true)

      { int abc = 0;

      abc++;
      
      
          abc++;
      
      
          abc--;
      
      
          break;
      }

      He is using these lines to save his code.

      awoo, MikeMirzayanov please look into it

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

        In order to check if a program is a copy of another one, can't the program be subjected to run on a set of deliberately faulty test cases during system testing? Programs whose behaviors, that is, the errors/exceptions they throw, the current values of all present variables, and the variable names in use, are the same for all test cases can then be weeded out...

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

You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj].

This is ambiguous. I thought it meant the rearranged patterns index mtj, causing me to write completely wrong code.

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

E was really nice. for each string s, for all the patterns that matches it, I put a directed edge from the first pattern it should match (mt for that string) to every other pattern that matches it and the answer is YES if the graph formed is a DAG?

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

    I thought the same but dismissed it quickly because how is that not TLE? Each string can match to potentially all $$$m$$$ patterns. So $$$O(m^2)$$$ sized graph (or DAG) right there? The only explanation I can think of is that maybe because of the contraint that each pattern is distinct this bound can be tightened? Do you have the proof?

    EDIT: Oh got it. smh. Each string can only match to atmost 16 patterns (because of distinctness constraint) so size of graph is bounded $$$O(m)$$$.

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

      According to the question, all patterns are distinct. For a string s, given its maximum length is 4, we can have at most 2^4 + 1 patterns that match it (for all binary numbers from 0 to 2^4, if $$$ith$$$ bit is 1 then keep s[i] as it is, else replace it with '_').

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

      A string can match with at most 2^k patterns. Let's take an example string "abc". Which patterns can it be matched with? "abc", "a_c", "ab_", "a__", "_bc", "__c", "_b_", "___" So, for each position of a string, we can either keep the original letter as it is, or replace it with '_'. so, for this reason a string can match with at most 2^k patterns.

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

    Yes, and the answer is the topological sort of the DAG.

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

Can someone please tell me why is my code failing, I did a 2 way kadane-ish dp and printed their sum. WA_CODE

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

    The dp seems to be off by one, since the indices go up to $$$n$$$ (as there are $$$n + 1$$$ cities).

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

I think problem B needed more tests, although figured out how to get 99 on test 1 it doesn't seem like it for the other tests.

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

The most educational things I learnt from A and B is that don't forget to use ceiling when comparing

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

The hardest part of E was understanding it. Nice problem set though, thank you!

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

    I still didn't understand the problem. Can you explain it?

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

      Let the initial arrangement of patterns be $$$P$$$. Your goal is to find an arrangement of patterns $$$P'$$$. $$$P'$$$ is such that, for each string $$$s_j$$$, the first pattern in $$$P'$$$ that matches with $$$s_j$$$ is $$$P[mt_j]$$$.

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

        That how it should be written in the statement!
        As for me, it was absolutely unclear that s[j] matches P[mt[j]], and P remains the same. Maybe I misread something, but it seems there is no contradiction if you understand that part of statement differently

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

          Reading it again, I feel it was somewhat clear what they meant. In my hurry to read it, I misunderstood and wasted 45 minutes on solving a different problem. Perhaps the problem statement should have held your hand a bit to be completely clear (like I did in my statement). I can't complain too much though, it's my fault I didn't read it closely enough.

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

            At least that other understanding doesn't pass samples. That was the point at which I figured out that something is wrong: coding is done, I fail first sample, OK let's actually look at the samples now...

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

    Yeah I wouldn't understand if there were no sample testcases.

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

In Q2 multiplying by 100LL instead of 100 got me AC. Any reasons why ?

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

imagining C graph cases gave me a headache but I liked this contest you have my upvote

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

How to solve G?

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

    Mo's algorithm

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

    only $$$O(\sqrt n)$$$ different values in the cnt array, so then apply Mo's algorithm to it and use a list to maintain different values in cnt, and then for each query take out all values and brute force

    total complexity is $$$O(m\sqrt n\log n+n^{5/3})$$$.

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

      But i am unable to handle the updates. Please elaborate.

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

        I'm assuming you know how to handle the problem without updates (using Mo's).

        To handle updates, split the queries (type 1+2) into blocks. Now, within each block, run Mo's. When you start processing a block, make sure that all the updates in the preceding blocks have been applied. To account for the updates in this block for a query of type 1, you can naively iterate from the start of this block applying all applicable type 2 queries. Since you broke it down into sqrt(m) blocks initially, it is guaranteed that you'll only iterate block_size times at max even when doing updates naively for each type 1 query.

        You might need to fiddle a bit to find the appropriate block size though.

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

          You mean for every block run Mo's naively?? Then for every block it should be $$$O(N*sqrt(N))$$$. Please correct me if I am wrong.

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

            Google "Mo's algorithm with update"

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

In C what does this mean that "First chain is skipped", does this mean we cannot take any node from first chain? I had initially set the ans to c[0]. That was the only reason I was not able to solve C and costed me wrong ans :)). First chain skipped means I thought I cannot connect any node to previous ones, otherwise I can taken some nodes from first chain.

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

    your last nodes can be in first chain.It means your cycle can't go above it.

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

Can Anybody Please give Me some counter test case i.e., Fail My Code

Question Link

Solution Link

I tried Everything but not able to find any counter case, Also did Stress testing, Still Not able to find it.

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

    try to use multiplication instead of division in check, that can be a problem.

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

      Yes got accepted after doing this, Thank-you so much brother

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

How to solve E?

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

    Take a look at this comment

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

    If there are multiple $$$p_i$$$s match the same $$$s_j$$$, then the specified constraint is basically implying the specified pattern exists before all other $$$p_i$$$s. Thus, we can keep track on the indices of patterns and build a dependency graph based on the constraints. For any specific $$$s_j$$$, there would be at most $$$2^k$$$ distinct patterns matching it. Thus, at most $$$2^k$$$ edges would be added to our dependency graph. Hence, the problem is reduced to check if a given directed graph with $$$n$$$ vertices and at most $$$m\times 2^k$$$ edges is acyclic, and if so, report any topological order. This can be solved by topological sort.

    There are a few trivial cases to notice, like the specified pattern not matching the given string or different occurrences of the same string being matched by different patterns, you may refer to my submission 105914103 for implementation details.

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

I was unable to sove even Problem A, can some one say the intuition to problem A. I tried binary search for problem B, but it did not pass 3rd test case

for i in range(int(input())):
	n,k=[int(i) for i in input().split()]
	arr=[int(i) for i in input().split()]
	prefixSum=0
	ans=0
	for i in range(len(arr)-1):
		prefixSum+=arr[i]
		if (arr[i+1])*100<=k*prefixSum:
			continue
		else:
			Min=1
			Max=(10**9)+1
			posible=Min
			while Min<=Max:
				mid=Min+(Max-Min)//2

				if (arr[i+1])*100<=k*(prefixSum+mid):
					posible=mid
					Max=mid-1

				else:
					Min=mid+1

			ans+=posible
			prefixSum+=posible

	print(ans)

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

    Try 1 2 1 1 1000000000

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

    Increase the Max value.

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

    Consider all array elements to be 1. We need to increase these numbers until the sum is divisable by k. So, first step is to find the next multiple of k bigger or equal to n. Second step is to find the max array element if the sum equals the number found in first step.

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

    I learned this the hard way — 99% of the time you don't need this big code for problem A. You probably need to take a deep breath and think at more fundamental level what the question is really asking.

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

      And my solution got hacked. To all the losers making hacking attempts, go fuck yourselves.

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

        It would probably have failed system tests anyways so I don't think it matters.

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

        Here's a tip for you
        $$$\lceil \frac x y \rceil = \lfloor \frac {x + y - 1} y \rfloor$$$

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

simple dp for C . a is vector of heights , b and c are vector of endpoints connecting to previous. we have to recompute this dp between all the inclusive indices of where b[i+1]!=c[i+1]

dp[i]=abs(b[i+1]-c[i+1])+1 +max(a[i+1],dp[i+1]-1-abs(b[i+2]-c[i+2])+a[i+1]+1-abs(b[i+2]-c[i+2]));

simple code.

code
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Were F and G intended to be that much hard??

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

    I'm really surprised nobody solved F. I've been rechecking and stressing my solution for hours, and I'm still sure it is correct, but it's strange that nobody got this problem.

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

      How to solve it? Is it dp(i, j) — farthest covered positon to the right if we have processed i first positions and j is the farthest to the left uncovered position, with segment tree? Or it is wrong?

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

        $$$dp_i$$$ — the maximum prefix we can fully cover with $$$i$$$ first lanterns.

        Let's look at how can we solve it in $$$O(n^2)$$$ with this kind of dynamic programming. First of all, let's write it forward. Which transitions from $$$dp_i$$$ do we have?

        • iterate on the lantern facing left that will cover the lantern $$$dp_i + 1$$$. Let this lantern be $$$j$$$. It should cover all lanterns in $$$[dp_i + 1, j - 1]$$$, so all lanterns from $$$[i, j)$$$ can be turned to the right (and we need a max query to determine the new covered prefix);
        • if $$$dp_i > i$$$ (lantern $$$i$$$ is already covered), we can just extend the prefix by turning the $$$i$$$-th lantern to the right. Note that turning it to the right when it is not covered yet will be modeled by the first transition.

        It is obviously $$$O(n^2)$$$, how can we optimize it? Let's write this dynamic programming backward. The second transition is changed to backward dp easily, what about the first one? Suppose we want to turn some lantern $$$i$$$ to the left. Let's iterate on the prefix $$$j$$$ that we will "connect" to it; for this prefix, $$$dp_j$$$ should be at least $$$i - p_i - 1$$$, and we update $$$dp_i$$$ with the maximum of $$$i - 1$$$ (since it is covered by lantern $$$i$$$) and the result of max query on $$$[j + 1, i - 1]$$$.

        In fact, we need only one such prefix — the one with the minimum $$$j$$$ among those which have $$$dp_j >= i - p_i - 1$$$. So, we build a minimum segment tree where each pair $$$(i, dp_i)$$$ is interpreted as the value of $$$i$$$ in position $$$dp_i$$$, and with min query on the suffix from $$$i - p_i - 1$$$ we find this optimal prefix, from which we should update (and to update, we can use any DS that allows max queries on segment — in my solution, it's another segment tree).

        Source code

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

          I was able to upsolve using what I think is a different DP, with $$$O(n \log n)$$$ distinct transitions, so both solutions are probably correct. Yours is definitely a much easier idea to implement.

          I reached my idea by supposing for some $$$i$$$ that every lantern in $$$[0, i]$$$ has had its direction chosen and lantern $$$i$$$ is the first unilluminated lantern. Then, there must be some lantern $$$j > i$$$ which is turned left to illuminate lantern $$$i$$$, after which the set of lit lanterns is a prefix, and every un-set illuminated lantern would thus be wasted unless turned right, which lets me greedily illuminate every lantern less than some value $$$k$$$. If $$$k = n$$$, that is a success; if $$$k = j$$$ then $$$k$$$ is facing left; otherwise $$$k$$$ may as well face right.

          It then turns out that there are at most $$$1 + 3 \log_2 (n-i)$$$ meaningfully distinct choices for $$$j$$$, and these are "easy enough" to iterate over: If $$$j$$$ is not the farthest-right-reaching lamp in the $$$[i+1, k)$$$ interval, no other value of $$$j \in [i+1, k)$$$ can possibly get a better value of $$$k$$$. But $$$k$$$ is at least 2 times farther from $$$i$$$ than the previous usable value of $$$j$$$ was! So the worst-case progression looks something like $$$j_0$$$, then $$$j_1$$$ (furthest reach in $$$[i+1, k_1)$$$), then $$$j_2 < k_1$$$, and then $$$j_3 \geq k_1 > i + 2 * (j_0 - i)$$$.

          Submission link: 105953208

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

          I had the same idea after the contest. You can simplify the code by doing some observations:

          • $$$Dp[N]$$$ is going to be increasing, so you can do a binary search instead of a segment tree
          • To do that max query on the lanterns that go to the right you can just use a sparse table that you can actually compute while reading the lamp powers.

          With those observations, I managed to get my code size at a little below 100 lines.

          Submission: 106013279

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

Fs in the chat for question F

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

can someone say y my solution failed? i am confident logic is somewat rite. solution logic: cross multiplying the equality a*100<=k*sum and checking if condition false, add differnce to overall sum

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

How can the answer of this case of problem C be 4?

3

3 3 3

-1 2 3

-1 2 3

Can anyone please explain what I am missing?

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

How many tests will problem A have? There're 1000+ hacks...

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

    I think the authors should manually look at the hacks and form some set of new testcases which cover all the corner cases, otherwise system test will continue for eternity.

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

Finally a time for me to be on the "+11" side of a widespread hacking event :D

I am deeply sorry for the people who got hacked though, I've been hacked multiple times before and I know exactly how that feels.

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

brilliant contest! Thank you

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

In problem E, "You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj]." doesn't clearly state that index mtj is referred for initial arrangement.It should have been stated clearly.

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

C was harder than D

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

Problems were good, I liked how ABC needed more thinking than coding and more thinking speed than typing speed.

It was an interesting contest even tho problem D was a standard one LOL.

»
4 years ago, # |
Rev. 4   Vote: I like it -39 Vote: I do not like it

thank u guys for 'A's weak pretests... :'((((((((((((((

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

As a...... As a novice at code/algorithm, I like codeforces! It's amazing and I like the feel to try my best to solve the problem... also I can't solve D which made me sad

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

It was hard and my solution on GNU C++17 64 bits FAILED BUT SAME SOL. ON C++17 PASSED...LOL

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

My standard screencast, with the standard tradition of misreading at least one problem

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

Nice pretests for A, as an tradition of Educational Rounds.

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

is there any extra points for hacking in educational rounds ?

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

thanks for great contest (i have 51 hacking successful =)) )

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

Just one thing: was it really necessary to have a two-letter variable like $$$mt_{j}$$$? First I saw that there is an $$$m$$$ variable, so I immediately interpreted $$$mt_{j}$$$ as $$$m\cdot t_{j}$$$, and that didn't help at all. I mean, I would understand $$$match_{j}$$$, but $$$mt_{j}$$$?..

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

I thought p[mtj] is a pattern after permutation :(.

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

I have to congratulate the setter of problem G. My solution looks like something well known, but I've never did something like that before. Really nice one, I definitely learned new stuff today. Thank you!

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

    What's your solution?

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

      I used Mo's algorithm. I didn't know about the trick to handle updates. A brief explanation of my solution:

      Keep track some stuff:

      • $$$cnt[x]=$$$ how many times number x appears in the range.

      • $$$tot[x]=$$$ how many numbers occurs x times in the range.

      • $$$vals=$$$ vector of distinct numbers in array cnt.

      It's really easy to update $$$cnt$$$ and $$$tot$$$ when you add/remove an element. For $$$vals$$$, simply push all the values to the vector while moving Mo's pointers, and after that remove values the ones that are irrelevant (those for which tot[x]=0). Also, avoid pushing an element to $$$vals$$$ twice. It's easy to see that after doing that, $$$|vals|<=\sqrt{n}$$$, because all elements are distinct and their sum is $$$<=n$$$.

      Using the fact that $$$|vals|$$$ is small, you can answer the query with two pointers over the array $$$vals$$$.

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

        What is the complexity of this implementation? I can't understand the amortized analysis of the update part

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

          when you use Mo's algorithm with updates, you have you use size of blocks $$$S=n^{2/3}$$$. In fact, i read somewhere that it's optimal to use $$$S=(2*n^2)^{1/3}$$$.

          Time complexity for addittion/removal of elements and push/rollback of updates is $$$O(S*(n+q))$$$ amortized.

          Time complexity for iterating elements and removing values form $$$vals$$$ is $$$O(S*(n+q))$$$ amortized, because each operation pushes at most one element to the vector.

          Time complexity for answering queries after removing irrelevant elements from $$$vals$$$ is $$$O(q*sqrt(n)*log(sqrt(n)))$$$ because you need to sort the vector of unique values before using two pointers method.

          So, total time complexity is $$$O((n+q)*(S+sqrt(n)*log(sqrt(n))))$$$. Please notice that this analysis uses the fact that $$$S \approx n^{2/3}$$$ (not $$$sqrt(n)$$$). In practice, the solution works a lot faster (my code runs in 1500 ms).

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

            For those interested in the details about complexity of Mo's algorithm with updates, there is a really nice blog, written by Fype, that explains everything :)

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

            Thank you for the explanation.

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

Great contest. Problems are interesting and educational. I enjoyed solving them.

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

I don't know why, but I feel like at least 1 of my 4 problems will fail system testing :(

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

The penalty for each incorrect submission until the submission with a full solution is 10 minutes can someone explain what this 10 minutes penalty mean? and if we submit the correct solution after certain incorrect submissions there will be no penalty right?

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

    No. Penalty means that if you submit a correct solution, you get the time for that solution plus the penalty. That is 10 minutes per submission, buf the first submission is for free.

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

Will it system test later,or just announce the final standings after the hacking time?

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

Can someone please tell me what error is there in my logic for this. I check for all elements in reverse order if the increase coeeff <= k and if its not I increase p0 by a sufficient amount. Link to soln: https://codeforces.me/contest/1476/submission/105888794

»
4 years ago, # |
Rev. 4   Vote: I like it -12 Vote: I do not like it

Difference between right and wrong in Question A

double n,k;
cin>>n>>k;
if(k<n)
k=k*ceil(n/k);
ll val=ceil(k/n);
cout<<val<<" "<<ceil(k/n)<<" ";

Input: 1 1000000000
Output: 1000000000 1e9
Both ans are correct but due to different format ans1 will be considered right and ans2 will be considered wrong.
So do typecast your ans

»
4 years ago, # |
Rev. 4   Vote: I like it -10 Vote: I do not like it
Your code here...
ll n,k,val;
    cin>>n>>k;
    vector<ll> pre,a(n);
    ll sum=0;
    loop(i,0,n)
    {
        cin>>a[i];
        sum+=a[i];
        pre.pb(sum);
    }
    ll add=0,maxadd=0;
    loopeqr(i,n-1,1)
    {
        val=a[i]*100-k*pre[i-1];
        if(val>0)
            add=ceil(val/(k*1.0));
        maxadd=max(maxadd,add);
    }
    cout<<maxadd<<"\n";

Question B :Using greedy approach.The basic idea is to take the maxdifference from all differences bcuz anything less than that will be satisfied by all other differences also either u start from begining or end of loop.
Here is my code which got accepted 105878231

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

hi

I really need help therefore I really couldn't understand what is the problem with the code which outputs that kind of format in test 3 problem b(but in math the number is correct)

submission:105899297

and its not just only mine

another submission of another person:105852796

help please

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

    In C++, when a really large double is divided by a small number, it changes into the scientific notation. To avoid this, explicitly convert the double to a long long int or int as required in the problem.

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

.

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

for C problem, my code failed in 4th testcase.I am not able to figure out the testcase,if anyone has any idea about what the testcase could be. Link to the code — https://codeforces.me/contest/1476/submission/105951904 My approach was to calculate number of vertices of every chain that will be added if i take that chain as an intermediate chain, ending chain, starting chain. i stored these values and calculated the maximum answer.

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

    1
    7
    16 2 12 2 7 18 8
    -1 7 1 2 1 2 2
    -1 10 2 12 2 3 12
    Correct Answer — 38
    Your Output — 37

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

CodeForce is a great programming site!I love it.It brings me a lot of fun.The change of rating again and again makes me feel very exciting!

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

Why so long for the editorial? Or is it normal? Sorry I am new, but my past contests had editorials almost in an hour

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

I really do not understand, why my code for A problem had hacked .. why ceill function returns a wrong value While N & K are long Please can someone expert help me to understand what is the problem here !

this is my submission

https://codeforces.me/contest/1476/submission/105923499 }

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

    simply just don't use ceil, use (n+k-1)/k for ceil(1.0*n/k)

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

      But why that happened !

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

        floating numbers are just too dangerous when you need absolutely correct results like codeforces, this ceil problem is very well known

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

          Thank you .. i did not know that before This mistake cost me a lot this round ☹️

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

            I too used Ceil function, it got passed. In Java ceil returns double so have to typecast it into integer before printing the answer 105866315

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

    For the test case

    1

    1 1000000000

    Your code gives 1e+009 as output, because you are doing "cout<<ceil(1.0*k/n)<<"\n";" .

    If you type cast into long long or int ("cout<<(long long)ceil(1.0*k/n)<<"\n";") it will give the correct result 1000000000

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

How to solve the other version of the problem E, i.e where the first matching string is the $$$mt_j$$$ th string in the rearranged permutation?

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

    After reading your comment I realized I misunderstood the statement of E during the contest and tried to solve the problem you mentioned XD

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

    You can keep a condition array where if con[i]=x then it means we can assign the ith pattern in the initial array any index from x to n. Initially, all values in con will be 1. Now for each string, mt pair we can update the con array for all patterns which match with the string to max of their initial value and mt. Now after processing all strings, we assign indexes to patterns in decreasing order of their con value from n to 1 if we can assign index to all then ans is yes and we can print the order else it is no.

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

    In that version you don't need the graph/top sort. Instead, go through the strings s_i and enumerate all the patterns that it can match (by adding wildcard slots just like the original version of E). For each of the enumerated patterns check to see if there's a p_i that it is equal to and assign the mt value to that p_i (using some map-like data structure). If the p_i already has a value then only update the value if our new value is larger (that is, if s_i already set it to a value mt_i=2 for example and s_j has value mt_j=3 for it, then the pattern must be in position 3 or later — if it was in position 2 then it would violate s_j's mt_j=3 condition). Note that there might be pattern that don't have any value assigned — that means they don't match any s_i and they can be put anywhere. Make a filler queue and add these in.

    After you've gone through all s_i then you need to fill out the answer array. Go from index 1->n and for index i if there's no pattern p_j with value mt_q=i then you can put an entry from filler in. If there is a pattern, then you can put that in and then put the other patterns with mt=i into the filler queue (they can go anywhere behind i and they won't violate any requirements anymore). This will give you an answer array, but you need to actually be a little more careful for some edge cases.

    When a p_i has value j and is put in index j, every s_q with mt=j must match this (otherwise the first matching pattern won't be j). To make sure this is the case, you will also have to store a count for each p_i (in addition to the index value) — in the step when you updated values you also update the count when the old value and the new value is the same (this is just the number of s_i that will get triggered by this pattern when it shows up in that given position). Now, in the last step when you fill the answer array by picking a p_i for index j, you have to pick the one with the highest count, and the count has to equal the number of s_i that have mt_i=j.

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

    Unfortunately I solved this version of the problem E. Here is the code which I have tested against many random inputs and then realised that the intended problem is something else.

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

When rating changes are updated for educational rounds?? I am new here.

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

https://codeforces.me/problemset/submission/1476/105958353

https://codeforces.me/problemset/submission/1476/105956041

These are my 2 submissions for problem B. 2nd got accepted but first is giving wrong answer on test 5 case 994 (truncated). Can anyone tell me where I have gone wrong?

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

    In the accepted submission int is defined as long long:

    #define int long long

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

      Yes I changed that too still wrong answer. When i removed #pragma GCC optimize("Ofast")

      pragma GCC target("avx,avx2,fma") these lines it got accepted. Any reason?

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

when will the ratings be given and why did they roll back the ratings of previous contest,i was about to become a pupil :(

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

Editorial, please

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

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

How this submission is getting accepted and not TLE as clearly their is a for loop that goes till 'n' and 'n' is 10^9 and test cases 't'= 1000. and time limit is 1 sec. Link: https://codeforces.me/contest/1476/submission/105860386 I thought in 1 sec only 10^9 operations can be done

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

    The compiler probably optimizes the for loop.

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

    I tried my level best to hack it.

    No, in 1 sec. 10^8 (approx) operations can be performed

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

    the loop was optimized by the compiler. I checked locally with -Og and it ran 5 seconds for each test.

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

I have a question regarding the complexity of memset. Can this code pass in 2 sec?

Code

Original Submission: 105929137

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

    memset an array of length $$$n$$$ takes time $$$O(n/w)$$$, which $$$w=64$$$ for codeforces.

    You memset 3 arrays with length $$$4\times 10^5$$$ for $$$10^4$$$ times in the worst scenario, and when that happens it takes $$$\dfrac{4\times 10^5\times 10^4\times 3}{64}\approx 2\times 10^8$$$ time, which is able to pass in 2s.

    upd. tried a hack with the worst scenario mentioned above. the solution passed in 1.2s.

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

editorials please!!

»
4 years ago, # |
  Vote: I like it -82 Vote: I do not like it

Hoping this round taught you that you shouldn't prepare contests anymore.

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

I got a message from system telling me that my solution for C problem is similar to In_Memories_11_08_2020/105891388, not_tehlka/105903063, yinuowang/105910649, sk_loves_Ritika/105921450, rivnam/105928243. In my opinion, the code is not at all copied and the only thing that is same is the fast IO template. Link to the template. Please look into the matter. It is the second time it has happened with me unnecessarily. Please restore my ratings

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

    i also got similar meassage with same accounts mentioned by you...

    i think that problem involve only certain conditions in loop thats it.. I AM DAMM SURE THAT I

    HAVENT SHARED CODE AND EVEN NOT COPIED ......i request them to please check it out and restore my rating ...

    please help even if there is some valid proof of my cheating or sharing i am ready that you delete my account else do not repeat this and restore my rating...

    i am so sad

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

    Same problem here, any help would be greatly appreciated :)

    As you can see from my submissions for this contest as well as past contests, I have used this fastIO code many times.

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

      same bro even i almost everytime using same template

      even ** i do not feel code are same ** i read 2 of them and campared with my code

      some responsible person have to say something upon this matter

      this is very bad .....i am saying this beacuse i am confident and need help of others to overcome this

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

@MikeMirzayanov can any anyone please help !!!!!!

today i got a message that my C solution matches to someone ... but i say confidently that i haven't used

any public IDE platform to code and even i did not share code with someone

so why like this with me ??? i am so sad please clearify ...

my request to others please help us to raise this issue ....even i am ready to accept that delete my account if i really do cheating or sharing but don't do like this ... ruined my performance.

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

I just received a message from the system telling me that my solution for the C problem is similar to In_Memories_11_08_2020/105891388, not_tehlka/105903063, yinuowang/105910649, sk_loves_Ritika/105921450, rivnam/105928243. I had reviewed the solution of all these people only the fast io template is matching. So, Please look into the matter. I think the codeforces plagiarism checker is not working properly. Although my rating is dropping in this contest according to the cf predictor yet I want my rating restored as I don't want any bad spot on my id.

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

Your solution 105901746 for the problem 1476C significantly coincides with solutions Fubuki_AI/105892973, misra_17/105901746, samcpp/105933007.

This happened because we all are using template of user Um_nik . All our code inside main() is different.

What should i do now?

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

how this submission accepted ? plz anyone explain time complexity of this submission..Advance Thank you.. https://codeforces.me/contest/1476/submission/105860386

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

can anyone tell me why i have 51 hacking successful but i have no more bonus ? . Thank you and sorry because of bad english

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

    Because it was an open hacking round.

    Hacking solution in this round doesn't contribute towards any bonus or extra rating.

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

I received a message from the system: Attention! Your solution 105913814 for the problem 1476D significantly coincides with solutions rk_no/105911811, nestedcode/105913814, MA7887/105919769, MayFlyyh/105931103, MTL_Sakura/105936065.

(I don't know these guys and didn't use idone or any other online compiler.)

The solution to the problem can be implemented in a standard dp approach and that is what I did during the contest. I saw the above mentioned codes and they are implemented in the same fashion. I think these type of codes should be treated differently during plagiarism check. This indicates that we can still improve the current plagiarism checker and stop such cases from happening. Innocent people deserve better. :( MikeMirzayanov awoo Please look into the matter.

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

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

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

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

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

Only one score to blue qaq. In addition, I've noticed one thing. Although the rating change of this game has come out, the rating change of div1 in the previous game is still frozen. Is it unrated? Or, the rating change will be recalculated at that time? I don't understand too much.

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

MikeMirzayanov awoo This round should be rated for me QAQ
I turned from Master to Candidate Master in Codeforces Round 698 (Div. 1) and then participated in this round.

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

    Same here, seems like people who droped from Master in Codeforces Round #698 (Div. 1) are unrated in this round.

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

Why am I not rated?

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

I participated in EDU Round 103 and got more than 70 places and qualified for the score. Why did I not gain rate??

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

    Same thing happened to me. Also in the last Educational Round 102 I was rated despite being Master before the contest. (I turned from Candidate Master to Master before Educational Round 102.)

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

Yesterday I have received two unexpected warnings from CodeForces plagiarism checker. The first one says, my solution 105930169 for the problem 1476D - Journey significantly coincides with solutions bleh0.5/105914875. After sometimes I got another warning that my solution to the same problem (1476D) significantly coincides with solutions bleh0.5/105914875, tejas10p/105917332.

There exists a very simple solution to the problem 1476D. So there is a high chance to match the solutions of two different persons. I have explored the submissions of the first 100 people according to the common standings of this round. Among these 100 submissions, I found 7 submissions that are almost similar to my solution. I'm mentioning these submissions here.

My submission:

The two submissions that matched with my submission:

Similar submissions:

  • 105883915 Here only difference with my solution is I used array and he used vector.

  • 105878527 He used vector and wrote the solution in a separate function.

Other similar submissions:

I am requesting MikeMirzayanov to look into these unexpected warnings. It's totally an injustice to me -_-

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

MikeMirzayanov awoo

rating Rollback -> update rating by this contest ->update rating(#698)

so, for example momohara, not update rating by this contest.

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

this contest rating changes :

lets add them :) -> roll them back -> add -> roll back

why?!

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

    Exactly, I have never seen this before that they roll back the rating changes for an educational round !