sigma_g's blog

CodeCraft-21 and Codeforces Round #711 (Div. 2)
By sigma_g, history, 4 years 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

Comments Comments (162)
| Write comment?
»
4 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Hope I remain a specialist after this Round;)

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

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

    I understand the pain sir, upvoted !

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

      Prolly the community didnt feel the pain of get downvoted lol, people downvoted :/

      → Reply
»
4 years 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. :)

→ Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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 :(

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

Hope I become expert in this contest

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

video editorials ! hmmmm.... NICE =)

→ Reply
»
4 years 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.

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

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

    its new method ig

    → Reply
  • »
    »
    4 years 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.

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

    Your graph is cool! T_T

    → Reply
»
4 years 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!

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +26 Vote: I do not like it

5

→ Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

what about score distribution?

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

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

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

High hopes with this round

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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 :)

    → Reply
»
4 years 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 :)

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +77 Vote: I do not like it
Happy Holi Everyone
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Hockey team?

    → Reply
  • »
    »
    4 years 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.

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

    That hockey team sarcasm is so good!

    → Reply
  • »
    »
    4 years 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.

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

    Posts that are so sarcastic that they return to normal!

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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!

    → Reply
»
4 years 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 :)

→ Reply
»
4 years 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 :)

→ Reply
»
4 years 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

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

interactive, you mean binary search problem? :p

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

Hope I become expert in this contest.

→ Reply
»
4 years 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

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

Please announce the scoring distribution of the contest!!!

Upd: Announced

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

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

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

Another Div 1.5 is coming :(

→ Reply
»
4 years 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

→ Reply
»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

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

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

Whatta jump between C and D :'(

→ Reply
  • »
    »
    4 years 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 !!

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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.

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

Good sample cases :)

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

India is an actually a good country :D

→ Reply
»
4 years 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.

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

Weak pretests in D (:

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

what is pretest 8 in problem E?

→ Reply
»
4 years 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.

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

How to solve Div2 E ?

→ Reply
»
4 years 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 ?

→ Reply
»
4 years 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.

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

    What did you do ?

    → Reply
    • »
      »
      »
      4 years 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.

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

        I wish i could write something like you sir . xD

        → Reply
      • »
        »
        »
        »
        4 years 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 !

        → Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
  • »
    »
    4 years 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. !!!

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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 :(

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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?

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

any one tell me how to solve div2 b?

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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...

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

    Change your country tag to INDIA. As simple as that

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

How to solve C ?

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

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

    → Reply
  • »
    »
    4 years 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)

    → Reply
  • »
    »
    4 years 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;
}
    → Reply
»
4 years 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 ?

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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. !!!

      → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

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

HAAPPY HOLI EVERYONE !!

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

I am afraid of system test :(

→ Reply
»
4 years 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 !

→ Reply
»
4 years 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.

→ Reply
»
4 years 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...

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

fst :(

→ Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

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

    Same here

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

      And you are violet. What a shame!!!

      → Reply
      • »
        »
        »
        »
        4 years 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.

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

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

→ Reply
  • »
    »
    4 years 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.

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

Can anyone tell how to solve C using iterative dp?

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

    Have a look at this submission: https://mirror.codeforces.com/contest/1498/submission/111377465

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

      Thanks.

      → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
        • »
          »
          »
          »
          »
          4 years 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!

          → Reply
»
4 years 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.

→ Reply
»
4 years 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!

→ Reply
  • »
    »
    4 years 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.

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

Wow rating changes came so fast

→ Reply
»
4 years 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.

→ Reply
»
4 years 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

→ Reply
»
4 years 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://mirror.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) ?

→ Reply
  • »
    »
    4 years 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.

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

→ Reply
»
4 years 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 :)

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

Etdiroail is too good :}

<3

→ Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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://mirror.codeforces.com/contest/1498/submission/111420403

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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.

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

When will t-shirt prices be announced ?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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()
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

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

When will problem ratings for this contest be updated ?

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
»
4 years 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.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +56 Vote: I do not like it

Now that more businesses are gradually reopening, we can finally distribute the tshirts. We have sent out the form link to all the 20 winners (as well as the testers and the writers). The design of the tshirt is:

(credits to victorknox for the design)

We hope you like it! :) We will try to send the tshirts as soon as possible.
Cheers! :D

→ Reply