sigma_g's blog

By sigma_g, history, 3 weeks ago, In English

Hello all!

We are proud to invite you to CodeCraft-21, which takes place on Mar/29/2021 17:35 (Moscow time). It is rated for all Div2 participants (rating under 2100).

This contest comes under Threads'21, as a part of our annual techno-cultural fest Felicity, IIIT Hyderabad. We have special prizes for Indian participants!

You will be given six problems to solve in a duration of two hours.

We have tried our best to keep clean statements, useful samples with good explanations, and strong pretests! We have written step-wise editorials, and will also release video editorials!

We would like to thank these amazing people for helping make the contest happen:

There will be an interactive problem! You are recommended to read the corresponding guide.

We hope you enjoy the contest as much as we did preparing it! Good luck!

Update: The scoring distribution is 500/1000/1750/2500/2500/3000.

Update: Editorial is up! Video editorials available on our YouTube channel.

We are sorry for the sudden increase in difficulty from C to D. Nonetheless we hope you enjoyed the problems! :)


PRIZES: The following twenty lucky participants receive a tshirt:

  • top 10 Indian participants
  • random 10 from top 100 (ranks 11-100) Indian participants

These ranks are determined from the combined unofficial ranklist. We are coordinating with the CF team for the tshirt design, and we'll update the blog post when it is finalized. We also have INR 7K worth prizes exclusively for IIIT-Hyderabad students!

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

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

Hope I remain a specialist after this Round;)

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

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

maybe ill reach pupil :) glhf

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

Wishing all Indians as well as all members of codeforces community " A very happy holi(Festival of colors celebrated in india) in advance.

Although the contest will clash with holi celebrations nevertheless will try to give it. :)

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

hope for no In queue in this contest

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

Wishing you all a colourful and Happy Holi.

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

How you decide if a participant is from India or not.

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

    Scrapping the leader board and applying simple script where data-field of country is India for a participant. As it is public for every user.

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

Hope we will enjoy this round

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

Hopefully I'll reach Green after this contest! I love bright colors, not this Grey :(

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

Hope I become expert in this contest

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

video editorials ! hmmmm.... NICE =)

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

I can vouch that the clean statements, good samples with useful explanations and strong tests part is definitely true. This is also one of those rounds where basically everything seems to be contest-ready (statements, tests, sample explanations etc) more than 48 hours before the contest, which is good (not having this is more common than you would think, sadly...). Kudos to the Codecraft team. I would recommend participation.

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

    wtf!? no "As a tester ..."

    its new method ig

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

    I second that.writers have really worked hard and have prepared a beautiful problemset.

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

    Your graph is cool! T_T

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

    Hi, Can Someone help me understand how to solve Problem E. I don't understand what is SCC and compressed SCC. Can some one guide me what i need to learn in prior to understand the solution?

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

As a tester, I found the problems to be very interesting and I had a lot of fun solving them..... Don't miss this contest!

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

I hope everyone achieves good rating. All the best to all!

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

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

5

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

what about score distribution?

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

Video Editorials. Excited. I wish there is more of it in codeforces.

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

After contest: System Testing failed: wrong answer expected '912999919212692864314789981255...8619859796115667579776922582953', found '912999917212692864314789981255...8619859796115667579776922582953'

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

High hopes with this round

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

What if there is less than 10 indian participants in the rank range 11-100?

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

    It is random 10 from top 100 Indian participants, and not random 10 Indian participants from top 100 :)

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

CodeCraft is a new way to learn to program by constructing things in a virtual 3D world => Google's Definition

What a deep meaning :)

»
3 weeks ago, # |
Rev. 3   Vote: I like it +77 Vote: I do not like it
Happy Holi Everyone
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Hockey team?

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

    No offense, but ironically your new year message was the same except "holi" in it lol.

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

    That hockey team sarcasm is so good!

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

    Hey guys i want to wish you all a happy holi. Discord is full of copypasted holi messages, that people don't even read and just forward to other servers. I don't like that. I like to write what i deeply wish and what comes from my heart. Our friendships, from the most deep ones to the most virtual ones are very important and will never be represented by a simple message copied from elsewhere. This being said I would like to thank all of you. You are the best hockey team i've ever played with.

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

    Posts that are so sarcastic that they return to normal!

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

How do you know if a participant is Indian or not? On CF it is very easy to change the country. And some participants don't even include country name in their profile.

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

    We will post the relevant details after the contest is over (when standings+rank deltas are finalized). So keep following this blog for future updates!

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

Hope I can add a new colour to my CF account ( Specialist :: Cyan ) in this festival of colours :)

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

Hopefully, I will try to sit and make efforts till the end of the contest and won't give up in between :)

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

Forgot to mention earlier, there will be an interactive problem! You are recommended to read the corresponding guide. Good luck! :D

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

interactive, you mean binary search problem? :p

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

Hope I become expert in this contest.

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

Finally India's contest. i challenge any non-indian to win the contest

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

Please announce the scoring distribution of the contest!!!

Upd: Announced

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

Kudos to IIIT-H, hoping for small and clear problem statement

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

Another Div 1.5 is coming :(

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

after seeing score distribution i'm like my limitation is up to problem C

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

make it 16:40 please,, eating my lunch :D

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

People want to see me doing contest. So, I'm going for that. Congras me.

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

worst problem statement of B

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

Whatta jump between C and D :'(

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

    solved C i am getting stuck after contest please someone tell me how to solve C i am pretty sure its DP tag !!

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

    at 500 250 test case i am getting wrong answer i don't know what i am missing ? logic seems fine to me but dot know where i am getting wrong !!

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

    test cases are very limited in C where k=1,2,3 and then direct 250 fuck me up !!

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

      the k = 250 is actually good tho since if you pass that test case then the chance your solution is wrong is too low. Stop whining and go improve instead

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

If your div2B is harder to prove than your div2E then miss me with that shit

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

    Seriously though, I felt the necessity for a proof, otherwise I would've solved that. How does one prove that the greedy thing works?

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

      It is allways better to place a piece in a row instead of not using the free space.

      Then, we can allways put two of a shorter length where we can put a longer one.

      So, if we simply put allways the biggest possible piece into the remaining space of the current row, then it is optimal.

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

Good sample cases :)

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

India is an actually a good country :D

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

A= An Easy Problem

B = Bad Statement

C= classical DP

D/E/F ---> Sorry Don't want to kill myself.

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

Weak pretests in D (:

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

what is pretest 8 in problem E?

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

My notebook just went full as I tried to solve Problem C with a diagram for the big K value.

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

How to solve Div2 E ?

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

was there any special algo for problem D ? or just looping and bruteforce like sieve ?

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

Can't believe I passed 40 pretests on E. If I do not get FST, that problem is better suited for the April fools contest. I didn't even understand the problem correctly IMO.

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

    What did you do ?

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

      random solution which I thought would fail within the first few pretests. I can't even explain my solution because I have no idea why I did it. 18 mins left, I just wrote something.

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

        I wish i could write something like you sir . xD

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

        Haha, okay. I tried thinking of some random solution too...Didn't work !

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

    Same thing here — I took a gut-shot: while there is a city with 0 incoming roads, remove it and decrease all other values of K by one. Then take the max remaining K and min remaining K as your answer, unless you end up with no array left, in which case there never was a strongly connected component.

    Let's think about why this works. Suppose every road has >= 1 incoming road and >= 1 outgoing road

    • If we are at node X, and we perform DFS, every time we reach a new node, we will be able to continue, because no city is an end point

    • The graph is connected, so we will reach every city, and use every road

    • Therefore the remaining graph is strongly connected

    This means that once we've removed the cities with only outgoing edges, we can just take largest remaining K value and the smallest remaining K value.

    EDIT: I am clearly missing something — my solution should have failed according to uphacking.

    EDIT 2: The above is wrong — all nodes must either be part of a strongly connected component, or they must connect other strongly connected components. So the correct approach is actually to sort all pairs by the absolute differences in k-value, and if the smaller k-value city is reachable from the bigger k-value city, that's the correct answer.

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

      I somehow missed this line — There is exactly one directed road between every pair of houses" even though it was in bold. Now I understand why this works. Just now I received a message that my solution has been uphacked so system tests were weak.

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

        My code failed the same test yours did as I just managed to hack myself with it! So I must also have missed something.

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

    Same for me. I didn't even understand why I am writing the solution but alas, it passed all the test cases. !!!

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

Can anyone tell me what has to be done to solve that ques. And also what the hell is testcase 2. i used simple approach to fill the W optimally . My code for that-----; ll n; cin >> n; while (n--) { ll a, b; cin >> a >> b; // vi v(a, 0); multiset m; rep(i, 0, a — 1) { ll g; cin >> g; m.insert(g); } ll ans = 0; ll k = m.size(); while (k > 0) { k--; ll f = *m.rbegin(); m.erase(m.find(f)); while (f < b && k >= 1) { ll gf = *m.begin(); if (gf + f <= b) { k--; m.erase(m.begin()); f += gf; } else break; } //cout << f << " ";

ans++;
}

cout << ans << "\n";

}

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

Can someone explain Problem E? I sorted it by descending |ka -kb| pairs and queries a b if a>b and b a otherwise until I get a match. I did not expect it to work but somehow it passed test cases.

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

    I think it's because the structure is that you can group houses into groups of biconnected components (which are also cliques). Then the meta-graph on these biconnected components form a total ordering, where all edges between two biconnected components all go in the same direction. Any house in a lower rung in this total ordering must have strictly more incoming edges than any on a higher rung.

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

    I did the same thing after removing all nodes that do not belong to a cycle, failed on pretests :(

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

    Well I used the pigeonhole principle — Say we have two vertices A and B and $$$k_B > k_A$$$, then we know that there are $$$n-k_A$$$ edges outgoing from A and $$$k_B$$$ edges incoming to B. Now by the pigeonhole principle we know that if the some of the above two quantities is greater than the total vertices apart from A and B, and if there exists a path from B to A, then we have a A and B in a directed cycle — and notice by choosing $$$k_B > k_A$$$, $$$n-k_A+k_B > n-2$$$ is true by default. Therefore if we query ? B A and get Yes as response, then we have A and B in a directed cycle — which is what we want. I'm still little sus about this being sufficient.

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

Nooooo I was like 1 minute away from solving E! Was it just to loop through all possible combinations of A and B where B has more incoming edges than A, in order from best to worst according to the cost function, and if A is reachable from B then it's the answer?

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

any one tell me how to solve div2 b?

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

    Greedily fill using the largest possible rectangle.
    If no such rectangle is possible, stack above (height++).
    Repeat until no recatangle remains.

    111372831

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

I am not a native Indian, but one by heart. Do I get a t-shirt too?

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

    Makes me wonder, if a participant changed his country of origin in the settings to Indian as of now (or maybe prior to the contest), does the system consider that participant to be an Indian? Now that's just a scam if possible right...

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

    Change your country tag to INDIA. As simple as that

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

How to solve C ?

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

    how to solve C please explain ? i got the logic but that didnt work for 500 250 test case it was DP i am damn sure !!

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

    2-D DP. One for the index other for k.

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

    let f(k, n) be the count of multisets with "k" decay age and n planes available in its direction.
    Reflecting on a particular plane, we get another ray with N — n planes (direction inverted) and k — 1 decay age.
    The original ray continues to travel with n — 1 planes remaining.
    so, f(k, n) = f(k — 1, N — n) + f(k, n — 1)

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

    I solved using recursion and memoization.My code

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

    Simple TOp Down DP.

    ll recur(ll i,ll n,ll k,ll dir) {
        if(i==n+1 ||i==0) {
            return 0;
        }
        if(dp[i][k][dir+1]!=-1) {
            return dp[i][k][dir+1];
        }
        long long int ans=0;
        if(k>1) {
            ans=(1LL+recur(i+dir,n,k,dir))%P;
            ans=(ans+recur(i-dir,n,k-1,-1*dir))%P;
        }
        else {
            ans=(ans+recur(i+dir,n,k,dir))%P;//same dir
        }
        return dp[i][k][dir+1]=ans;
    }
    
    
»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Am I the only one who thinks that the time limit for problem E is too tight for Java 8/11 ?

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

    Sorry to hear that! We've a AC submission in Python on our side.

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

      Thanks for the confirmation. I might have to optimize my solution more if it doesn't pass System Test Cases. !!!

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

      Just an FYI for the future, Java often runs slower than Python in interactive or output heavy problems. For example, during the testing of 1451E2 - Bitwise Queries (Hard Version), the limits on $$$n$$$ had to be reduced from $$$2^{17}$$$ to $$$2^{16}$$$ as Java couldn't pass it without using PrintWriter or custom IO classes instead of the default System.out functions, while Python easily passed.

      Similarly, while setting a problem on Codechef (which usually has a much faster judging environment, especially with respect to IO) that required a large string to be printed, Java failed to print $$$5 \times 10^{5}$$$ characters in 2 seconds while C++ and Python easily managed to print $$$10^{6}$$$ characters in the same time, all without any fast IO.

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

        Then I guess the time limit should be a bit more, else the solution with CPP/Python having the same Java logic gets passed and Java solution gets TLE.

        It may seem unfair.

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

HAAPPY HOLI EVERYONE !!

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

I am afraid of system test :(

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

Well, even if I sadly bugged my C (actually I just realized I was doing useless transitions lmao), I really enjoyed the round ! Problems were nice, statements clean, sample useful... I hope you'll do more CodeCraft rounds !

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

can anyone say why my B failed 111388954

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

It is much easier than Div2 i think. But anyways problems were well framed with very short codes for all. But i personally feel that problemset is too easy or the problems should be shifted one level back for DEF , D->C, E->D, F->E. Thanks for the contest.

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

It's very sad, when tasks are sorted out of order of increasing difficulty...

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

fst :(

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

btw i believe F is easier than D and have less solves just because it is on position F

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

    No way. It miiiiight be easier for those who memorize random algorithms but can't think. And even then it is dubious.

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

what should i do to avoid such pathetic mistakes?

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

Somehow, I didn't think of a dynamic programming solution for C. I just ended up counting the number of particles with decay ages from i=1 to i=k and obtained that by using prefix sums.

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

    Same here

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

      And you are violet. What a shame!!!

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

        Lol, why does having an alternate solution have to be shameful, if anything its a good thing — reading aliters is a good way to develop thinking.

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

Please help in this submission of C : https://codeforces.com/contest/1498/submission/111405668

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

    Try to reduce the for loop inside the recursive function to one or two recursive calls.

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

Can anyone tell how to solve C using iterative dp?

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

      Thanks.

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

      Can you explain your approach.

      i solved it iterative dp too but yours look eaiser

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

        Consider some DP where the state is represented by:

        1. $$${hits}$$$: The number of planes in front of the particle

        2. $$${age}$$$: The age of the particle

        And our answer for the state is the total number of particles that are produced during this state.

        So, formally: $$${dp[hits][age]=}$$$ number of total particles produced when we shoot a particle with age $$${age}$$$ towards $$${hits}$$$ planes

        So how to calculate the current state from previously calculated states? It seems tricky at the first glance but it's actually kind of simple.

        When we shoot a particle towards $$${hits}$$$ planes what happens?

        1. A new particle with age $$${age−1}$$$ gets reflected by the first plane in front of the current particle and it will now face $$${n−hits}$$$ planes, which is the state $$${[n−hits][age−1]}$$$.

        2. The same particle goes through the first plane in front of it then continue to face $$${hits−1}$$$ planes (obviously it's age won't change), which is the state $$${[hits−1][age]}$$$

        So now we know the transitions from our current state, the recurrence becomes:

        $$${dp[hits][age]=dp[n−hits][age−1]+dp[hits−1][age]}$$$

        Of course, this can be optimized to get rid of the second dimension since we only need the information from states with $$${age}$$$ and $$${age−1}$$$, this improves our space complexity to $$${O(n)}$$$, Code

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

          I had to read that many times to understand it but worth

          great solution, Thank you!

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

My submission of E is still "Pretests passed". I'm very confused by this crazy verdict.

»
3 weeks ago, # |
  Vote: I like it +24 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!

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

    I get "Accepted" only now after rating changes (on E, which I solved on contest), hope you will fix this.

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

Wow rating changes came so fast

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

sigma_g please have a look at my submissions for problem E with the same source code.
1. Submission during contest — It gives TLE.
2. Submission after contest — It gets Accepted.

Please have a look over this issue and do update the ranking if possible.

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

Can we solve c using prefix sums and iterations for each k??plz tell ..i think we can do this..but am not able to get correct ans using modulo

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

Could someone pls help me on what is wrong with this submission for D ? Also I defined int as long long and double as long double.

https://codeforces.com/contest/1498/submission/111408649

I did the old fashioned dp solution. But it seems to fail on test 12. Is it due to the fact I am using long double (precision error) ?

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

    I think it's precision error. Actually there's no need to use double in this problem.

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

a number answer

include

include

using namespace std;

int sum1(long long int n){

int sum=0; while(n>0) { long long int m=n%10; sum=sum+m; n=n/10; } return sum; } int main() { long long int t,n,sum=0,m,k,k1,k2;

cin>>t;
while(t--){

cin>>n; k=n;

k1=0; //cout<<"k1"<<k1<<endl; while( k1<=1){

k2=sum1(k);

//cout<<sum<<endl; k1= __gcd(k, k2); //sum++; if(k1<=1){ k++;} //k1= __gcd(k, sum);

// k1=__gcd(k, sum); } cout<<k<<endl; sum=0; }

}

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

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

Can anyone please tell me why this solution 111375843 for problem B is wrong. I solved using 2 pointers. Thanks in advance :)

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

Etdiroail is too good :}

<3

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

MikeMirzayanov

These two codes are exactly the same, but the first code was submitted during the contest got TLE on test 15 but the other code submitted after the contest got accepted.

The code, getting TLE: 111380434 The code got AC: 111417474

Due to which my rating got affected. Please have a look at it. Thanks

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

    Your accepted code also passes in 982 ms and there is usually a +- 50 ms difference during execution times on different runs.

    Also, avoid using long long when unnecessary. It takes longer to read integers into long long. For instance, this is your exact code with the line "#define int long long" removed. It ran under 600 ms which is significantly faster.

    https://codeforces.com/contest/1498/submission/111420403

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

      Yeah, thank you for your explanation. I Will avoid using it next time when unnecessary. But can nothing happen this time? As the code is correct only, even the judge is giving accepted sometimes. So, during the contest, it is difficult to think of such a reason for a new coder even though it passes all the pretest. MikeMirzayanov

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

        Don't worry, these things average out with time. There'll be another time when you'll get lucky. Everyone goes through such issues.

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

          Yeah, you are true. Thanks for writing and motivating.

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

Problem Explanation was very poor for Problem C, D. It could have been better. I understood it only after reading sample input output.

Problem Writers should participate in Codeforces contests to understand how problem statements are written. It looked like problem setter was deliberately trying to confuse participants. If you can't write problems upto standards of codeforces, at least you can keep the contest private to your college, Don't make it Div2 contest.

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

When will t-shirt prices be announced ?

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

    Ideally, it should not take more than a week to finalize everything and announce the results.

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

Python doesn't support too deep recursion for problem C, even though I changed the limit.


import sys sys.setrecursionlimit(1000000) def dfs(i, k, cache, n): if i == 0 or k == 1: return 1 if (i, k) in cache: return cache[(i, k)] ans = dfs(i-1, k, cache, n) + dfs(n-i, k-1, cache, n) cache[(i, k)] = ans return ans def solve(): n, k = map(int, raw_input().split()) print dfs(n, k, {}, n) % (10**9+7) for _ in xrange(int(raw_input())): solve()
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, that is why the editorial solution for Python is iterative.

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

When solving problem B using the binary search method, we select the height of the box and check whether all rectangles will be included in it. I cannot figure out how to account for the space that has already been used. How this formula works from the analysis ci = ci + 2 × ci + 1 + 4 × ci + 2…. Where does this formula come from? Explain someone. Thanks.

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

    One block of width $$$2^{i+1}$$$ occupies the same space as two blocks of width $$$2^{i}$$$. Therefore, to account for space used by the $$$i+1$$$-th block, we add $$$2\cdot c_{i+1}$$$ to $$$c_i$$$. The same reasoning can be extended to larger blocks.

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

When will problem ratings for this contest be updated ?

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

You guys are not able to make a random generator in two days which can decide 10 from 11 to 100 ranks lol.

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

    As clearly mentioned in a comment above, we will finalize the results and announce within a week ideally.

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

      Love you guys and your effort... So much intolerance and impatience in this world for futile things.... Awww

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

MikeMirzayanov please update problem rates for this round. It's been a week.

»
13 days ago, # |
Rev. 3   Vote: I like it +94 Vote: I do not like it
Congratulations to winners of CodeCraft-21 and Codeforces #711 (Div. 2)!

We will soon contact you regarding prize distribution.