By BledDest, history, 12 days ago, translation, In English

Hello Codeforces!

On Oct/11/2020 12:05 (Moscow time) Educational Codeforces Round 96 (Rated for Div. 2) will start. Note that the start time is unusual.

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 Adilbek adedalic Dalabaev, Alex fcspartakm Frolov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: The editorial is here.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 WZYYN 7 186
2 137_345_2814 7 194
3 jiangly 7 200
4 LayCurse 7 203
5 dreamoon_love_AA 7 258

Congratulations to the best hackers:

Rank Competitor Hack Count
1 ViciousCoder 100:-9
2 ManasG 45:-13
3 Valera_Grinenko 57:-40
4 Voldmort 36:-3
5 fstzyh 38:-9

858 successful hacks and 2258 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Sevlll 0:01
B jkchen 0:03
C alireza_kaviani 0:03
D jkchen 0:12
E MagicSpark 0:05
F LayCurse 0:36
G MagicSpark 0:36

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

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

This unusual time makes me unusual :(

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

4AM for me :(

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

notice the unusual time getting usual

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

    which can be a good thing for many (and a very bad thing for some)

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

Btw, not sure where to write this, I just noticed there is a testing round just before this contest. Personally I am already tired to do a contest for 2 hours, so i don't really want to do a testing round just before that. I am happy to do a testing round any other time actually.

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

why unusual time for ECF...2AM

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

Hmmm.... from Edu 46, every Announcement blog was authored by pikmike and he was always included in the problemsetters' tab. Did he get angry from all the downvotes from last round? The last round was pretty great problem-wise, learnt a lot, especially from problem G.

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

Note that the start time is unusual, is getting usual to us :)

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

No vovuh , Roms , Ne0n25 and pikmike! Are they okay?

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

    vovuh, Ne0n25 and pikmike are participating officially in the contest this edu is based on.

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

my hope to return a cm

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

Normally unusual timings is due to a live contest happening at the same time. Is there any reason this time?

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

what happened to my rating graph its weird... how to solve it?? please look my profile?? @admin anyone can help??

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

Lunchtime for me :(

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

    Where do you live and what time will be in your country at the contest?

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

ECF and opencup are at the same time, not cool

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

I will be doing online class and contest together. Shouldn't miss a single contest in this quarantine <3

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

    do you have classes on sundays?

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

      Yes, we have class everyday except friday in Bangladesh.

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

        on Sunday? strange

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

        Friday is special day for Muslim. We are majority Muslim in our country. So government make Friday off day for us. Such as Sunday is Holiday in your country.

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

The timing is great for me. Thanks :)

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

Can anybody explain me what does solution hacking means? Thanks in advance.

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

    Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!

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

Great start time for chinese participants:D

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

    Same here in Korea.
    it's 18:05 (UTC+9)

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

    For Japanese too. :) (start at 18:05)
    Recently many contests were held at 23:35(UTC+9), in which is difficult for me to participate.

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

2 days Back to Back Contests

10 October 2020 HHKB Programming Contest 2020 Codeforces Global Round 11

11 October 2020 Educational Codeforces Round 96 AtCoder Regular Contest 105

Great for learning

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

I think there should be more contests of this Asian timezone. Maybe there should be two types of contests for Europeans and Asians.

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

11 minutes left time to be ready : )

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

Will BledDest be conducting the future rounds as well ? He's been conducting the last 2 EDU rounds too.

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

    He has actually been conducting the last 79 edus.

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

      Sorry I meant if you will be away like this contest.

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

Please, less ad-hoc.

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

    please graphforces

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

    C and D without educational worth.

    C is just "try it, should work...somehow", D is kind of edgecase hunting.

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

      Nah, C was kinda cute. To minimise the end value, we had to keep as many smaller digits as possible was my conjecture (which I indeed took a few minutes to prove after a guess submission). The solution (I think) was to take the biggest two values and perform the ceiling operation and then continue. D was quite great too if we (at least I) didn't misinterpret what the problem statement. I thought E could be something to do with segment trees and inversions but that didn't end so well for me implementation-wise.

      I looked at your submission for C and it was kinda hilarious to see your struggle in comments. Well done though!

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

        In C , For any value of n , i always got answer as 2. It was more observation based ig

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

        I just recalled those two problems, and still, I think I did not learned anything from them.

        In C you see the intended solution by coincidence, or you do not. If you do not come up with the idea to simply add the two biggest values you'll get stuck at this problem. Or find some other algo which coincidently works, too, like mine. But for somebody who did not solve C the thing you get is "There is nothing you can do. Solve more problems, mayby then someday you'll get the intuition to have the right idea at the right time."

        And problem D is basically the same. You find the right pattern by blindly trying some pattern. Or you do not find it. I found the three points given as hints in the tutorial within like 10 minutes. But still did not found a way to make it a working algo for like an hour. And afterwards, just like in C, absolutely no knowledge of what I could have done differently or better.

        That might be nice riddles, but from my point of view no problems to educate anything.

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

scoring?

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

is there penalty on correct resubmission in educational round?

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

I am eagerly waiting to see the test case no:2 of problem D,,,huh.

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

Idea behind E?

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

Contest Finished.

Can we discuss the problem before system judge?

I have not too much ideas about F&G

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

How to solve D?

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

How to solve D????

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

    111011 -> [3, 1, 2]

    delete -> minus 1

    remove prefix -> delete first number

    Then try best to maximize the operation

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

    two pointer concept.

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

    Maintain an array of lengths of consecutive elements. If the first prefix length is greater than 1 (>1), then we can remove that prefix and increase the number of operations. Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it. If such length is not found, remove the last length from the array (maintain 2 pointers one left and one right and reduce the right pointer).

    Example :- 1 5 10111

    After 1st operation -> 011

    After 2nd operation -> 1

    Thus 3 operations are required.

    A counter example as to why we should reduce from the first large prefix instead of the largest one is here

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

      Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it.

      Please tell me wouldn't that make the complexity n*n. It tried the same thing but got tle on test 4.

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

        Just keep pointer to last element that is greater than 1 and shift it right if necessary (do not search for it from the start every time).

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

        You don't have to search starting from the first element always. Suppose your at 2nd element in [1,2,2,3]. Now, after reducing that, you only need to move forward in the array because the previous entries will be <=1. This can be done using a variable to store the current reducing index and incrementing it accordingly.

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

          Thanks :)

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

          How can we know that the next value is >= 2?

          Example: [1, 2, 1, 3], if you are at the second element

          then you will decrement the 2nd element and it will be [1, 1, 1, 3] now if you increment it by one it will be on the 3rd element which is 1. But reducing 1 isn't correct, the correct one is to reduce 3.

          So how to increment it?

          Please I am stuck here for several hours.

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

            Suppose your pointer was on the 2nd element, now you have to increase until it becomes >=2. If it is not possible, then u just reach the end of the array.

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

      I used the sae concept but getting WA on 252nd test : https://codeforces.com/contest/1430/submission/95251105

      How do I figure out a test where it fails ?

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

        Try reading the comments to find any test cases that your solution may fail. I don't think there is a way to access that particular test.

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

          I got it. When the current value if "1", I was trying to make up for it by using the element which is the largest in range (i+1,N) which is not always optimal , better option is to use the element closest to the current index (on its right) . Thanks!

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

            Not largest, any number which is greater than 1 in range (i+1,N) is my approach. What's wrong in that?

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

              Choosing any number in range (i+1,N) is not optimal , its better to always choose the first number greater than "1" in range (i+1,N) . Why ? Because, you are at index "4", and a[4]=1 , also, a[5]=1,a[6]=1,a[7]=3,a[8]=1,a[9]=1,a[10]=5 .

              Now, you have only two options, either select from a[7] or a[10] , but the best choice is to select from a[7] , because soon you are going to reach a[7] , and its all potential value will be destroyed , once it is destroyed by prefix technique ,so better completely use a[7] before destroying it.

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

      Why is it necessary to find the first greater than 1 segment ... If I find the largest segment everytime and reduce it.. won't it work ?

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

      In case of prefix length = 1, instead of looking for the first length > 1, I looked for the largest length substring of the same value and reduced it's length by one but I got WA using this approach. Can you help me? My submission

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

Problems just awesome in this contest.

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

How to solve E?

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

    Have an vector of stack of size 26 where u push each character to respective bucket initially. Now we know that the first character has to reach the end. But the important thing to notice is that only the last occurence of the first character is required to reach end to save operations, that is why we maintain a stack to get last occurence.

    Now if we know that the last occurence of ith character is at position j, we also need to know how many of the characters from j to n-1 have already been push to right and for that we use segment Tree/BIT.

    So at each postion ans += n — 1 — (no. of char in [j,n-1] already pushed) — lastest position of that char

    Heres my Submission

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

      Could you explain why do we need to know the number of char already pushed? And how about handling the chars that has index larger than n/2?

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

        That is because set of character after the last character given in the input are already in reverse and we dont need to consider them. It would be better to explain with an example.

        Lets say we have the string: icpcsguru

        First move: We move the i at postion 0 to the end and get cpcsgurui. moves=9-1-0=8

        Second move: We move the c at position 3 to end(after u) -> cpsguruci. moves=9-1-3=5

        Third move: This is the important one. Here we move the p at position 2 but the moves wont be 9-1-2, instead it would be 9-1-2-1=5.

        This is because the c ahead of p is already moved to end and this is exactly why we need a range query from j to n-1 to get how many are moved to end.

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

Why did you not bold 'prefix' in D :(

delete the maximum length prefix consisting of the same characters...

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

    Ah, damn it... This is where most of us went wrong. Most of us did indeed solve a different version of this problem correctly.

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

      I tried for over 1.5 hrs but couldn't come up with a solution for the "different version" of the problem.

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

    wait, I missed that too... :(

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

I misread B and thought that only adjacent swaps were allowed.

(Sorry for the edits)

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

Helps for Problem D please

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

    precompute an array of sizes of chunks of 0s and 1s for [0, 0, 0, 1, 1, 0, 1, 0, 1, 1] -> [3, 2, 1, 1, 1, 2] now in each step first chunk would be removed anyway but we need to remove 1 other element before that, choose the chunk either after it or itself that has size > 1, if theres no such chunk remove the last element

    Since we never delete a chunk of size 1 from middle, it is ensured that two chunks are never merged. Hence we will always get the optimal answer.

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

      I used nearly the same approach. But when there is no chunk of size >1 then I just add (remaining unprocessed elements+1)/2 Here is my submission.

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

      I actually did this exact thing .. You would see if you go through my last two submissions .. I now want to figure out where it went wrong

      Upd : I got the bug .. actually I thought to use the first non one value and hence used a priority queue to keep the minimum next indices avalaible for operation only to realize now that we get a maxheap as a default.. my bad.. Got the same code accepted Now. Thanks for replying and help anyways :)

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

What on earth is Test Case 2 for D ?

UPD : my greedy fails for 5 10111, ans should be 3, not 2. Optimal way is to take 5th character first.

Damn, it seemed so obvious, the guy who set this problem is pure EVIL!

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

    Exactly...Here is my approach.....

    If prefix has more than 2 same characters then 1 operation consists of removing the first character and then the remaining prefix...this way we delete the minimum we can after every operation. Also if s[i]!=s[i+1] then we jump to s[i+2] after deleting si and s(i+1). This can be proved to be true by some casework...but I dont know why this greedy approach is failing.

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

      well i understood why this approach is wrong in last second consider 101111

      according to ur algorithm answer is 2 ! where u can get answer 3 by erasing 3 on first operation and erasing 2 on second operation and then erase 1

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

        so 3 operations in total

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

          My solution gives 3. Can you please have a look at it?

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

            I stress-tested my solution and got some tests where my code fails:

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

          My solution idea is same but it fails on test-525 . Can anybody tell me which test if fails ?

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

    1 7 0100010

    You can try this case, my solution was giving wrong answer on this case. May be you might get your mistake. The correct answer is 4.

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

    I figure what's wrong when my first submission

    I maintain two index, the head and the index of number bigger than 1.

    It's important to notice that the second index must >= the first index.

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

this contest actually had a really good combination of problems ! neither too easy , nor extremely tedious . Thanks BledDest for the contest

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

What hurts more?

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

    If you use O(n^2), you will surely get TLE. I also copied code from GFG though and get TLE on test cae 41 :P https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/

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

      What's the point of getting a positive rating when the code and logic aren't yours in the contest!?

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

      You guys are copying? ://

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

    Getting TLE on test case 41 while simultaneoulsy on call with GF with she breaking up wid ya at the same exact moment or vice versa whatever minimizes your mood. My guess is you probably got lucky with both events not happening at the same time....If even luck did not favor you on that...then oh boy.... that oughta hurt (In Matthew Mccounaughey's voice)...good luck xD.

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

      This is what happens when you are already overthinking and you start to overthink your overthinking. PS: You are funny!

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

        Yeah I am watching Sherlock these days, and my tone..be it in any chat..whatsapp,CF,CC,CSGO,twitch,among us(xD)... etc sounds so deductive and caseworkey lol. Thanks btw.

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

please tell me why my answer for B is false this is my answer:

include<bits/stdc++.h>

using namespace std;

int main(){

int t;

cin>>t;

while(t--){

    int n,k;

    cin>>n>>k;

    int a[n];

    for(int i=0;i<n;i++){

       cin>>a[i];

    }
    int kk = sizeof(a)/sizeof(a[0]);

    sort(a,a+kk);

    int i=2;

    while(k--){

       if((n-i)>-1){

         a[n-1]=a[n-1]+a[n-i];

         a[n-i]=0;

         i=i+1;

       }

       else{

         break;

       }


    }

    cout<<a[n-1]-a[n-2]<<"\n";
}

}

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

    I think if n=1 then your a[n-2] will become a[-1]. Maybe that might be the mistake. You should only write a[n-1] as the answer because a[n-2] is already zero.

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

      n cannot be 1 according to given constraint in problem. (1<=k<n ..)

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

    try using long long instead of int, integer overflow takes place if you take int.

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

Is there a greedy approach for D ?

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

why my solution got accepted after changing int to long long https://codeforces.com/contest/1430/submission/95208979

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

Anyone can tell how to solve F & G ?

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

    F is DP

    $$$dp[i][j]$$$ = minimum cost (in bullets) to beat $$$i$$$ rounds (and start the next round) with $$$j$$$ bullets remaining in your magazine.

    Note that since $$$j \leq 10^9$$$ you should use a map/associative array for that dimension.

    The initial state is $$$dp[0][k] = 0$$$. Each state can be the parent of up to two states, one with $$$j < k$$$ (no reload after round) and one with $$$j = k$$$ (reload after round; only transition to this state if you have enough time). A state may also "dead-end" if it is impossible to beat the current round from it; if all states dead-end the answer is $$$-1$$$.

    This fits in $$$O(n^2)$$$ or $$$O(n^2 \log)$$$ as the number of states increase by at most one each round (the $$$j = k$$$ state may create a new $$$j < k$$$ state, while the $$$j<k$$$ states only "move" about or merge into the $$$j=k$$$ state)

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

Can anyone tell me why this O(nlogn) solution for E gives TLE at test 41 solution link

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

D was EVIL :(

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

Is there any other way to solve E without using fenwick tree/ segment tree ?

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

    count inversions any other way (merge sort , set -order_of_key)

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

    use pbds if you are using c++, 95257988

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

      codingkshatriya can you explain the logic of E.

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

        For each position, we know what caharacter should come there, we have the initial string, so each time it is optimal to move that character which comes first, for example cdad, first position should be occupied by d, there are 2 d's but it's optimal to move the d in the second position to first, but string changes when we do that, it becomes dcad, if you notice all elements before the moved position, their index increments.So we can store the positions of all characters and every time we just have to know the changed position, which is just the number of elements greater than the current position that have been already moved, we can solve it using pbds ordered_set

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

    It can be done without segment/fenwick trees. Because its a character string, we can keep prefix/suffix frequency arrays for both initial and reverse strings and maintain the answer. You can look at my code for reference.

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

hi, can anyone tell me, what is hacking? and did it give score also?

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

    not in educational and div.3 rounds.

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

      Does that mean an unsuccessfull hack would have no effect on your final score?

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

        In Educational and Div.3 rounds neither successful nor unsuccessful hack gives you extra points. But in regular Div.2 and Div.1 you get +100 points for each successful and -50 for unsuccessful hack.

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

    Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!

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

Can C be solved using heap? This solution gave TLE but I just to know if there is any way to optimise it or if it can't be solved using a heap. This solution without heap worked correctly.

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

    I would give u a better approach .. Just use the max 2 possible values each time and then work yourself on a case or two. You would get to know that you would always end up at 2

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

      The second link is using the solution that you mentioned. But I never thought about it always ending at 2. In the cases that I tried it ended at 2 but I thought that it would increase for bigger cases. I just want to know if it can be done using a heap.

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

    i believe x[2:] is costly operation(tell if i am wrong) and yes the approach is right here

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

    Yes! i used a priority queue and got AC

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

      I solved it after I read your solution. My mistake was using a heap but not using the heap functions. I was using list operations and performing multiple heapify. Using heappush and heappush performs heapify on its own. Thanks a lot!

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

First I convert 1000111000 to [1,3,3,3] then if the chuck is greater than one than i add one to my ans , if the chuck is equal to one than i remove one from the biggest chuck remaining , 95255021 can someone point out what's wrong with the approach

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

    An example test case is -> 1 13 1010010101111

    Your approach gives 6 while the answer should be 7

    The problem is that we should not remove from the biggest chunk because we may exhaust it early. The ideal way is to remove from the first chunk which is greater than 1. That way we can optimally utilize the chunks. In the example, it exhausts (1111) which could have been used for 6th element while we could have reduced the (00) for the 1st element.

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

      thanks man. should have seen this. at this rate someday my rating will be lesser than the number of contests I participated.

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

Prob C hurts me a lot. I even don't have time to catch up Prob D.

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

    Dude I overcomplicated my C because I thought the solution to C should not be so obvious. Now I see that a brainless greedy works. -_-

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

      I also overcomplicated C .... took 1 hour.

      but what hurting me more is TLE on testcase 41 for problem E.

      so sad

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

My screencast of getting 7th place [assuming I don't FST], along with solutions to all problems is being uploaded to my youtube channel. Youtube should finish processing it in 20-30 minutes or so. If you want to see it as soon as they finish processing, you can turn on notifications. Good morning and thanks to the authors for the cool problems! :)

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

Nice Problemset. Was E a standard question of Fenwick Tree ?

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

Why is this brute force wrong? (PROBLEM A)

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n, i, j, k;
        cin>>n;
        int flag=0;
        for(i=0; i<=334; i++){
            for(j=0; j<=334; j++){
                for(k=0; k<=334; k++){
                    if(3*i+5*j+7*k==n){
                        flag=1;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
        }
        if(flag) cout<<i<<" "<<j<<" "<<k<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}
»
10 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For some reason, I'm really bad at educational rounds...

My last four ed-rounds
And this one will be even worse (expected -64)

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

    The problem for loosing rating in this contest has huge role of your mindset saying that "I will loose rating from previous pattern ,making you feel pressure and under pressure u don't do well". Thinking it to be any normal contest and being cool , you might have performed better.

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

Sweet
Slightly over an hour since the end of the contest and already 500hacks.

I'm not complaining though as it may seem. Just noticing a funny fact

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

    yeah most of them are for problem A, people have forgotten to break their nested "for loops" (those who have used this looping concept). most hacks for TLE in that

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

Anyone else used Dp for problem A? XD

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

    I did the recursive sol exactly as yours

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

    I thought about something like this initially. But decided that it is quicker and less error-prone to write brute-force that should converge quickly

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

A lot of successful hacking attempts for A & B. It's sad.

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

    My solutions got hacked in both. So sad.

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

      Do you have any reasons why we got tle in B Especially java users? while looping backwards*.

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

        Trying to figure out the same as it happened to me too :(

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

    for java users B — Arrays.sort() was the issue

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

      But many has used that method. Just the difference I found is that the accepted one is one in which they are looping from i=0 to k .

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

        Idea is correct. but Whoever has used Arrays.sort() in java then you can hack that solution by $$$TLE$$$. Arrays.sort() is O(n^2) in worst case. google for that particular testcase and you can hack all java solution which uses Arrays.sort();

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

Does anybody have proof for the fenwick tree solution of E. Why wouldn't there be a case where we need lesser number of moves than taking it to the last possible position.

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

    So, here is my solution : First take the reverse of the given string and try to get all characters into position starting from the last.

    Some sort of proof for this : It is always optimal to choose the rightmost matching character in the original string to swap and get to the final intended position. Assume it takes X moves for rightmost character to get into final position. Now any other character Y will take X + dist(rightmost character, Y).

    Now, on why it is better to start fixing from the end of the string : When we try to fix some position before fixing the positions to the right of it, then this character might get displaced once again when some other to the left of the fixed character needs to go to the right of it.

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

      is it necessary to move from right to left

      i reversed the string and tried moving from left to right

      getting wrong answer on test 41.

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

        It should work. The logic may slightly change though like you must take the leftmost matching character instead of the rightmost etc.,

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

          Hi thanks for the reply, actually i was using int instead of long long.

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

I want to know D's solution, shouldn't it be traversal string simulation operation? I have seen a lot of AC codes, they all have found a certain pattern, can someone tell me this pattern?

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

    Let's say there are various segments of same elements, so one thing that you can see clearly is that you don't want to merge two segments, right? Now if the segment at front has size 2 or greater you can simply delete one of its element and then delete this segment. But what if our segment at front has size 1. In the first operation you want to delete a number other than this segment, so you can do it by deleting from any segment after this and size greater than 1. It will basically create a suffix with ones only and you just want to find the size of this suffix. the answer will be number of segments initially — (suffix length/2).

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

      mafailure Can you please explain the solution w.r.t to 1000100 ?

      If I first take i = 7 string becomes 00010,

      Now if I take i = 1 string becomes 10

      Now if I take i = 1 string is empty

      ans is 3, but it should be 4, can you help me with that?

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

        make a vector of lengths, in this case it will be v={1,3,1,2};
        now first length is 1 so we need a length>2 ahead in the vector or the last length==2 if any of the condition met then we can reduce that length by 1
        if both these conditions are false then we have to forget about a length
        for clarity see this https://codeforces.com/contest/1430/submission/95243326

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

          what do you mean by "last length is 2" ?

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

            if we encounter with length==1 then we need a length of 3 or more or the last length 2 or more

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

              so in 1000100 I can take i = 7 right? since last length is 2

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

                hmm

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

                  but that would leaves us with string 00010, now when i just take i = 1, string becomes 10, and now the answer is only 3, but when I take i = 2 in the first operation it can become 4, so how does it work ?

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

                  here our vector of length will be v={3,1,1} now first length is 3 so it is safe then we have 1 and none of the condition are met so we have to drop the last length that is so ans will be 2.. idk what do u mean by i

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

                  pinged in DM

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

Not noticing the unusual time made me miss the contest.

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

    10 downvotes for expressing my mistake and feeling sad for missing a contest, ouch.

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

Can someone explain the "flow" solution for G?

I only know the bitmask dp solution.

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

    Can you explain what the bitmask dp solution?

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

      Yes.

      You can find that the number you use can be convert into $$$0,1,2,3...k,(k\leq n)$$$.Then you can add node in increasing order of $$$a_i$$$.When adding a node you must check whether this node can be added.

      The time complexity is $$$O(n*3^n)$$$,but in fact the states are much less.

      This is the code during the contest: https://codeforces.com/contest/1430/submission/95237357

      However because of its huge constant, it's hacked after the contest by the test:

      18 0(time: 3000ms+)

      But we can reduce the enumeration of the maximum $$$a_i$$$.Then it can pass.

      Ac Code:https://codeforces.com/contest/1430/submission/95257898 (331ms)

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

In fact, problem e is not difficult, but I don't have enough time to complete it. The slow hand speed is also one of my flaws. .

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

My solution is a perfect O(N) solution. But it got hacked for TLE. Problem A of this Educational round 96. 1430A - Number of Apartments Kindly look for yourself and tell me why this happened @ BledDest adedalic fcspartakm Submission : 95203970

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

    python is too slow, change to c++

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

      Bro I submitted in PYPY3, that's supposed to be faster than Python. And since the complexity is correct there shouldn't be any problem in the language right? Like the setters should make sure it gets submitted in all languages if the required complexity is fulfilled

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

        Your code is taking 1247 ms for t = 1000 and n = 1000 for every t. Try it in Custom invocation.

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

          Exactly my point , given the complexity is correct which is O(N), It's showing TLE ie time taken is above 1 sec. Which shouldn't happen for the given values.

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

        You should calculate dp once for the max value of n = 1000. But you do calculate it every time.

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

          Yes, I thought about ,but considering the situation for T = 1000 and N = 1000 , it should be quite evident that O(N) should work

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

    This solution is O(tN) at best and on each iteration it creates at least six three-element dictionaries. Six million three-element dictionaries are not free

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

      Dictionary with 3 elements can be considered as constant, it occupies O(1) complexity , how does it matter??

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

    Hey, You can check out my PYTHON TEMPLATE for making your Python code run faster.

    Also, I have been a Python Coder for quite some time now, but sometimes even I have to submit a program in C++.

    Mentioned below are some areas for which you should not choose Python as a language to code your solution :

    (1) Recursion with a depth > 1000.

    (2) If you need to apply lower_bound or upper_bound on a set as Python doesn't support it.

    (3) String problems with the length of string > 1e5 and your solution is supposed to have a time complexity of nlogn.

    Hope this helps you.

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

    I was a Python coder myself. Normally PyPy is faster, but once I submitted a problem in PyPy and it got TLE (the same code was later accepted in Python3). So I had to decide which to use where.

    Even though a solution is O(n) and optimal does not guarantees an AC in every language. Internally Python is slower than C++ and a more efficient solution in Python may get TLE whereas a less optimal solution may get an AC in C++. Even though there is a time relaxation in the background for some languages, that is not enough to get an AC.

    Therefore sometimes it is written that_ a solution is not guaranteed in every language_.

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

Can somebody prove problem D solution ?

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

In problem D :

Why is it "always" optimal to pick just next chunk with more than one value and not any other chunk with more than one value , whenever we encounter 1 ?

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

    If you don't choose, the just next valid chunk will be erased at some step, thus not better than the solution.

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

Can somebody prove the solution to D ?

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

If someone has got a little free time, can they mind explaining to me dp approach for solving problem A. Thanks.

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

    A dp solution for such a problem would be based on the observation that if we got a solution for some n, then we can simply construct a solution for n+3, n+5 and n+7, each by adding that number to the set of numbers in the soluttion.

    So start at zero and go up to n. Foreach number if there is a solution, construct the next three soulutions and store them.

    This will finish after n loops with solutions to all numbers in range 0 to n.

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

where are the editorials?

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

How to solve D using Binary Search ? It has BinarySearch tag.

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

Is there a way for java users to solve problem B, because I used Arrays.sort() and got hacked. Collections.sort() is even slower. If we use a priority queue then it has insertion and deletion time complexity of NLog(n) and is a min-heap so it will only work for some cases. So what is the alternative??

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

    Use mergesort Or sort Array of Object instead of Array of Primitives. Arrays.sort() uses quicksort for which worst case time complexity can be O(n^2) (only in case of primitve data type).

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

    HarnoorSta7 has already pointed out. So, we got a TLE because Arrays.sort(int[]) uses quicksort which can have a worst case complexity of O(n^2) when the array is almost sorted. Now Collections.sort(List) is indeed slow because of non-primitives but it is still O(nlog(n)) in worst case because it uses Tim-sort instead of quick sort. So, I think it would not be a TLE if we used Collections.sort(List) in this question.

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

      Thanks for the link. Java was a lie for me. All the java accepted solutions I saw are using Arrays.sort() for int. Let's see how many java users survive for question B after final testing is completed.RIP java users!!

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

    To avoid worst case of Arrays.sort() function for primitive data types which is O(n^2), first shuffle randomly the elements in the array then use Arrays.sort() function. The function which I use to sort the array is-

    static void sort(int[] A){

    int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
     }
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please tell me why my solution on problem A doesn't get TLE on a test with 1000 of 1's in input? This is kind of a max text and it's not even close to TLE (around 300ms).

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Hi
    Max cases: 1000 & worst test: 1000.
    loop1:
       break at worst case 1000/3 = 330 
       loop2
          break at worst case 1000/5 = 200
    
    • Your code at worst case: 330*200*1000 about 6e7 < 10e8 so it's fine.
    • Note:
    • Expected to be 10^8–10^9 simple operations per second, in C++ or Java.
    • Less for Python, about 10^7.
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But if I have 1 as n, my fors don't break at all.

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

        When u get the answer and b = false, the both loops will break coz of "&& B" in loops.

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

          Yes, but if the answer is -1 it wont

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

            You 're right, My apologies I was wrong. Hope you get the correct answer soon.

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

            When used "long long" instead of "int" in same code got TLE and don't know why. 95291943

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

I'm almost sure the intended solution for problem G doesn't involve Simplex, but if you know this method and you prove (or assume :P) that the coefficients found by the algorithm are all integers, you can get a really quick accepted.

Also, this solution should work fast enough even if $$$n<=100$$$ and $$$m<=n*(n-1)/2$$$

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

95241114 Why is this solution showing unsuccessful hacking attempt even though it shows compilation error in online IDEs?

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

    just so you know, in hell exists a special place for A-problem hackers!

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

      Nd there are some dumb people like you whose A-problem gets hacked...lol

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

        It saying the green pupil. just so you know it is infinity number of the way to hack every problem A solution.

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

95295302 Can someone tell me how to optimize it to have an AC. This gives TLE. I saw solutions of other people with the exact same method having AC. Please help! Thanks!

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

    The problem is Arrays.sort() I think. It uses quick sort, whose worst-case time complexity is O(n^2). Try using Collections.sort() instead.

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

After reading the first 2 problems, I am pretty sure the problem setter was watching the water jug scene of Die Hard 2 while writing these problems.

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

Can someone plz help me why my solution shows TLE for the Barrels problem of today's div 2 B Here's the link-https://codeforces.com/contest/1430/submission/95296320

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

    Probably Arrays.sort(arr); is the problem there.

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

      But i saw others code and they have done the same.The only difference between them and mine code is that they used a for loop to count the summation and I used a while loop. Can u plz tell why it's happening.

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

Me after using x / 2 + x % 2 in rounding up in the questions

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

Please, can someone proof C solution? Thanks.

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

    We just need to proof that an answer less or equal to 1 cant exist. If (a+b)/2 rounded up is 1, then 1 <= a+b <= 2. Its impossible to get a+b <= 2 if n>=2, so the minimum possible answer is 2.

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

    As last contest. This way is really better. Thanks for improve CF continually.

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

    Can I ask a question? What does it mean to remove cheaters? According to my understanding, cheaters should be counted as zero points and kept in the rating change list.

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

    wait removing cheaters ? are you removing them manually or what ?

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

No idea why my submission for Problem B gives TLE (got hacked in the hacking phase)
Can someone please check?

UPD: Got it fixed. Arrays.sort() is the problem here. Aaah, this thing ruined my contest big time. Why you implement it via quick sort java. Whyyyyy? 
»
10 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Please upload the editorial..

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

In Problem A I used two pointer method.Like this

lp(i,mx+1)
	{
		
		j=0,k=mx;
		while(j<k)
		{
			
			if(i*3+j*5+k*7==n)
			{
				cout<<i<<" "<<j<<" "<<k<<endl;return;
			}
			else if(i*3+j*5+k*7>n)
			{
				k--;
			}
			else
			{
				j++;
			}
		}
	
	

But still got WA .Why?

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

    That loop stops to early while(j<k)

    It should be something like while(i*3+j*5<mx) because there is no reason why j must be smaller than k.

    And that is, because it is basically no two pointer problem, but a brute force.

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

editorial?

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

Where are the editorials?

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

Editorials Please BledDest

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

When will the tutorials be published?

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

Are some test cases intentionally left out for such contests?

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

Is there an available editorial?

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

Is it possible to get all the test Cases for the problem from Somewhere. My Solution for D fails on 149th input of test case 2. If not it would be great if someone provides some good cases for checking the fault in my code . I have tried all the cases given in the comment section and all the outputs(from my code) have matched with their expected output.

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

    yes , is there some way to download all test cases ?

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

    It's a bit hacky, but you can sniff the test case by hardcoding something like if (test_case==149) and print it out in a submission.

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

      It was a Cool Idea , I got the failing testCase and my error as well. Thanks a lot

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

Why editorial is not published yet?

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

Very happy to get First-AC at problem E&G.

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

Problem E was awesome.