By awoo, history, 3 months 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 LiM_Hfsy_tie_tie 6 176
2 SSRS_ 6 184
3 maojiayi 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

»
3 months 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 :/

»
3 months ago, # |
  Vote: I like it -54 Vote: I do not like it

As a ......

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

Let the comments with "as a" begin

»
3 months 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!

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

    yes same

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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.)

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

    so Madara Uchiha saved you, huh.

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

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

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

I hope it will be a good round

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

Hope for the nice contest!

»
3 months 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.

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

    Hahahhah did you also get burned by today's contest?

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

    educational=(4problems or more)*adhoc XD

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

    what is adhoc?

    • »
      »
      »
      3 months 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.

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

        would adhoc be considered to be general-thinking problems?

    • »
      »
      »
      3 months 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 ?"

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

        You mean, the less you know, the better off you are?

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

Hope,I will enjoy this round as today!

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

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

»
3 months 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!

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

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

    • »
      »
      »
      3 months 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

    • »
      »
      »
      3 months 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!

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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.

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

            well u can eat sometimes without being hundry good for you

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

              don't tell u have never eaten something even tho u were full? CP is a sport. Many people play football or any other sport without wanting to play for a club or a country.

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

                what would u call the release of serotonin when u win and the thrill when u loose ,u can eat but when u loose its the hunger that make u move forward ,ofcourse i am speaking on avg not on individual level but thats a fact

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

    Why are you so cute :')

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

I hope i will become expert today..

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

Hope to become specialist today

»
3 months 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 :)

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

There should be a third button IMO XD

  • »
    »
    3 months 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.

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

      Doesn't look like it.

      • »
        »
        »
        »
        3 months 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.

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

    MathForces!

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

    And a forth: MathForces...

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

I hope i can solve first 2 problems quickly :)

»
3 months 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!

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

Hey Legend tell me how can i improve my skill on number theory ? in previous contest after lot of observation still i am not able to solve 3 and 4th problem

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

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

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

(

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

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

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

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

time to become green (hopefully)

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

It will be a wonderful contest. Best wishes!

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

My chance for specialist.

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

As a contestant I wish you ALL THE BEST

»
3 months ago, # |
  Vote: I like it -14 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hoping for a good contest!!

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

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

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

Best of luck to all :)

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

A and B kinda sucked ngl

  • »
    »
    3 months 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

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

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

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

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

    • »
      »
      »
      3 months 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.

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

the idiot tottered happily towards grey coder again

It's me I'm the idiot :)

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

is educational contest rated for all or only for div2?

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

B — balanced

»
3 months 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...

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

How to solve C?

  • »
    »
    3 months 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.com/contest/1476/submission/105933562

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

      Fixed. I didn't handle the 6th case well.

    • »
      »
      »
      3 months 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.

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

        Here's my code see if that helps.

      • »
        »
        »
        »
        3 months 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.com/contest/1476/submission/105949955

        Hope it helps!

  • »
    »
    3 months 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.com/contest/1476/submission/105907608

  • »
    »
    3 months 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;
    }
    
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just realized my approach wasn't greedy at all. It's just DP without a DP array. Yeah, I solved it btw.

»
3 months 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

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

    I thought so, but after seeing that the length of the chain can be 1e9, I knew it wasn't a graph problem.

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

    Yes, C isn't greedy.

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

      There might be a greedy algorithm to it, but I solved it by trying all possibilities using dp

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

      I think it's greedy I got AC using greedy.

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

        Nice, I also did greedy but it failed on testcase 3.

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

          I failed on testcase 3 also in 1st attempt , you're probably missing the edge case.

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

            can you tell the edge case your code failed the first time? I can't understand the logic of why you put the cur=max(cur,y-x+1); in your passed attempt.

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

                Thank you. For some reason, I thought that this case is covered on ans=max(ans,cur+c[i-1]); this part of your code. Thank you

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

                  Yeah, I need to learn to write clean code ;), I put so many max conditions that were not necessary at all xd.

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

        there is not much difference between greedy and dp in this problem because you are accessing only the values from the previous index.

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

    I solved it using greedy.

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

How to solve D?

  • »
    »
    3 months 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.

  • »
    »
    3 months 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

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

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

  • »
    »
    3 months 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

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

      How to think for such solutions?

      • »
        »
        »
        »
        3 months 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

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

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

    • »
      »
      »
      3 months 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.

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

        Does nope mean that I did it wrong?

        1. n >= k then k = ceil(n/k)*k and do the same thing.
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basically the idea is take 2 coditions- 1-if n<=k Here of course ans is n/k if(n%k)==0 and n/k+1 if it is not equal to zero because imagine sum consisting of 1,1,1... and then remaining will be added acc from first. 2-if n>k Basic idea is as n>k, bring k multiple as close as possible to the smallest number greater than n so that is eventually again satisfies the first condition and then proceed as if it is now a case 1.Hope u get the idea Here's the sample for case 2-

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

    Here's some one liner code for ya
    (k - n % k + n - 1) / n + (n % k != 0)

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

Any hint for A?

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

    find nearest integer >=n which is divisible by k say x, ans=ceil(x/n)

»
3 months 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 :/

  • »
    »
    3 months 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 :(

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

my contest in 1 photo :

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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 :) .

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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.

          • »
            »
            »
            »
            »
            »
            3 months 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

          • »
            »
            »
            »
            »
            »
            3 months 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.

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

              my binary search solution : CODE

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months 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.

  • »
    »
    3 months 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 ?

    • »
      »
      »
      3 months 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

      • »
        »
        »
        »
        3 months 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 ?

»
3 months 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

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

    Who is copying?

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

      guitar_waale_bhaiya 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

      • »
        »
        »
        »
        3 months 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...

»
3 months 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.

»
3 months 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?

  • »
    »
    3 months 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)$$$.

    • »
      »
      »
      3 months 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 '_').

    • »
      »
      »
      3 months 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.

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

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

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

.

»
3 months 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

  • »
    »
    3 months 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).

»
3 months 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.

»
3 months 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

»
3 months 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!

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

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

    • »
      »
      »
      3 months 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]$$$.

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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.

          • »
            »
            »
            »
            »
            »
            3 months 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...

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

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

»
3 months 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 ?

»
3 months 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

»
3 months ago, # |
  Vote: I like it -14 Vote: I do not like it

F, I wasted 1+ hour on B because I completely forgot that division by int rounds down :(

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

How to solve G?

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

    Mo's algorithm

  • »
    »
    3 months 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})$$$.

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

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

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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.

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

            Google "Mo's algorithm with update"

»
3 months 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.

  • »
    »
    3 months 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.

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

God I could have solved B if I had 30 more sec... I submitted right after the contest ended and got AC :( Spent 60+ mins to figure out why my solution got WA... I really get mad at myself

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

    I believe we both made the same mistake :(, but I was able to submit it just before the contest finished.

»
3 months 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.

  • »
    »
    3 months 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.

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

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

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

Why was my submission not uploading after 10 PM. Ugh I don't get it. Now my rating will decrease without any reason, man!

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

How to solve E?

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

    Take a look at this comment

  • »
    »
    3 months 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.

»
3 months 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)

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

    Try 1 2 1 1 1000000000

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

    For problem A: we are need minimum sum that can be divided by k. Let find that sum.

    sum = ceil(n / k) * k;

    After we know sum, we need to spread it to cells, that each element was minimum possible

    answ = ceil(sum / n);

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

    Increase the Max value.

  • »
    »
    3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

      • »
        »
        »
        »
        3 months 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$$$

»
3 months 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
»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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?

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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

        • »
          »
          »
          »
          »
          3 months 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

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

Fs in the chat for question F

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

When "vovuh" is one of the writer then contests are awesome!!! Thanks for another good contest :-))

»
3 months 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

»
3 months 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?

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

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

  • »
    »
    3 months 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.

»
3 months 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.

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

    No you are not sorry, so stop pretending ffs.

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

brilliant contest! Thank you

»
3 months ago, # |
  Vote: I like it -46 Vote: I do not like it

this is my code for 2nd question inflation can anyone help where is the problem

include<bits/stdc++.h>

using namespace std; int main() { int t;cin>>t; while(t--) {int n,k; cin>>n>>k; long long sum1=0;long long sum=0; long arr[n]; for(int i=0;i<n;i++) {cin>>arr[i]; sum1+=arr[i];
} sum=arr[0]; for(int i=1;i<n;i++) { if((arr[i]*100-k*sum)<=0) { int c=1; } else { long long d=arr[i]*100/k; sum+=d-sum; while((arr[i]*100-k*sum)>0) {sum++;} } sum+=arr[i];

}
 cout<<(sum-sum1)<<"\n";   
}

}

»
3 months 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.

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

How to generate hack test cases? I am trying to hack A with highest constraint, i.e. T=1000, K=1, N= $$$10^9$$$, but still solution passes

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

C was harder than D

»
3 months 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.

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

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

»
3 months 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

»
3 months 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

»
3 months 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

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

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

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

As well as all of the other educational rounds

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

is there any extra points for hacking in educational rounds ?

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

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

»
3 months 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}$$$?..

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

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

»
3 months 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!

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

    What's your solution?

    • »
      »
      »
      3 months 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$$$.

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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).

          • »
            »
            »
            »
            »
            »
            3 months 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 :)

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

            Thank you for the explanation.

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

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

»
3 months 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 :(

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

For Problem C i've included all border cases , still I'm getting WA, can someone please tell me what's wrong or give a test case on which my code fails ??

my code : https://codeforces.com/contest/1476/submission/105940952

»
3 months 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?

  • »
    »
    3 months 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.

»
3 months 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?

»
3 months 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.com/contest/1476/submission/105888794

»
3 months 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

»
3 months 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

»
3 months 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

  • »
    »
    3 months 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.

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

    when you use double then if your ans is large it tend to represent ans in power of e
    notation .So to avoid it you can name your variable as long long int
    or when you are printing ans just typecast the ans i.e cout<<(long long int)ans<<" "

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

My First ever Educational Contest in which my rating increased , Thanks to Open hacking which saved me from decrement ps : Feeling bad for whose solution where hacked

»
3 months 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.com/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.

  • »
    »
    3 months 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

»
3 months 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!

»
3 months 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

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

    educational rounds usually have slow editorials and idk why

»
3 months 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.com/contest/1476/submission/105923499 }

  • »
    »
    3 months 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)

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

      But why that happened !

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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 ☹️

          • »
            »
            »
            »