Ashishgup's blog

By Ashishgup, history, 6 years ago, In English

Hi everyone!

I would like to invite you to my second Codeforces Round, which I have made with my friend and Snackdown partner Jeel_Vaishnav.

With that said, I bring to your attention our new Codeforces Round 523 (Div. 2) that will take place on Nov/22/2018 18:45 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would really like to thank Jeel_Vaishnav for his help with preparing problems, cdkrot for coordinating our round and Um_nik, vintage_Vlad_Makeev, Aleks5d, KeyurJain & Mahir83 for testing the problems. I would also like to thank MikeMirzayanov for Codeforces and Polygon platforms.

You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.

Link to My Coding Library for those interested :)

Good luck! :D

UPD: Scoring Distribution: 500-1000-1500-2000-2500-2750

UPD2: Editorial

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +79 Vote: I do not like it

Your previous contest was really a balanced one, hope this one will be the same, Indian setters :D

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

Another round from Ashishgup. Really excited :)

Please put this post on Home.

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

vintage_Vlad_Makeev's handle changing color in every post is kind of record lol.

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

    he is chamaleon of codeforces

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

    I think gritukan wants to beat the record of Mhammad1 for the maximum rating change in codeforces history.

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

I don't trust this emoji :)

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

I become Div. 1 in your last round, but it would take me a huge effort to do it again this time :)

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

let me guess, all the problems can be solved using your library :)

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

Hope we all have a good rank! (I want to become blue :D)

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

and again I am very excited about the contest by Ashishgup.

Because of this blog on Quora.

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

Good luck Ashishgup!

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

I will put my best effort to become green :P

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

    I'll put my best effort to become cyan :P !
    My color was changed at previous Ashishgup's contest , hopefully I'll do that again ^^

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

    Finally, I am green again :P

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

      Yeah, Congrats ! Finally, I'm cyan :P !

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

I hope it will be great contest

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

For Chinese players, it is necessary to stay up until the early hours of the morning, I hope this contest can be rated normally.^_^

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

Good Luck

Weirui Bao

Lupeng Zhang

Jiangyu Zhang

Shipeng Li

Huangcheng Lin

Jinhui Wang

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

Why we don't have interesting contest theme/character anymore? :(

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

God keep my rate above water!

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

Seems like we are going to have another unrated round

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

    Dont you ever say that, Unrated round is not a round, its just problem set with standing!

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

    Well, It's already unrated for you :d

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

is it just me or 502 bad gateway's coming ?

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

It takes too long for the site to upload and sometimes i get 503 error. Will the problem be solved?

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

I saw signals of a DDos attack...

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

unexpected dos-attack incoming

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

Its 5 minutes before the contest and the website is already showing 502 Bad Gateway and not loading properly.I dont want this contest to be like the last one please.

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

Some serious connection problems from here. So slow loading pages and lots of 502 Bad Gateway.

I've just checked 'downforeveryoneorjustme', it also points out to that problem too:((((

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

delay again(

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

ddos again?

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

delay...

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

Please dont start the contest untill the problem is solved

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

Should we participate? I can only acces codeforces on my phone...

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


True!!

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

I can't believe it 10 minutes delay :(

I barley have battery in my laptop for two hours :(

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

Problem A O(S) solution can't hack, its passed test: n = 1 , s = 10^9 :) 46079712

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

    Tried this hack as well and it passed in 1.2/2 sec lol

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

    Same 46069414 1996ms/2000ms

    feelsbadman

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

    Looks like codeforces have very fast processors.

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

      Is this work of a compiler or processor?....

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

        The operations like arithmetic, etc. are performed by the processor. Compilers may optimize the code somehow but eventually it's the processors performing the execution of the program. You'll get to know more about this kind of stuff when you study computer architecture as a part of your curriculum.

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

    Same , I got -50 point since tried to hack this solution with n=1 , s=1e9 :'( 46068920

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

I think the contest and the difficulty of the questions could've been more balanced although I really enjoyed struggling with the questions it is kind of obvious from the amount of people who solved each problem that the difficulty gap between questions 1 — 3 and 4 — 6 is a bit much Anyway, as I said it was really challenging and I enjoyed thinking about the questions and I hope https://codeforces.net/profile/ashishgup will provide us with more of this

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

What is the hack for B?

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

    I also want to know :( dont understand whats wrong with my code

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

    i have this one

    5 10

    2 2 2 2 10

    the answer is 6

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

Really good problemset.

Anyone who solved E/F can share their approach?

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

    E: if a constraint k1 is immediately below (as in there's no other in between and k1 is in the subtree of k2) other k2, the constraint k2 will get subtracted by k1 since you need k1 and it will also appear in the other. Now, group the vertices by "first ancestor that has a constraint" and the problem becomes min-cost max-flow

    F: root in any R. You can get the amount of subtrees and the sizes in O(N * K) questions. Now, you can "walk" to the side that has the "heaviest" subtree until you get to the real root. This solves it ok for small K's. For large K's, get random paths and mark the vertices that belong to the path in O(N). There's a very high chance that the most visited vertex is the root.

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

Is F supposed to be just randomly select 2 points and check to see if they're both leaves, then isolate the root from the path? That's the idea I got, but no time to code.

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

    I too thought so but wasn't sure, though had some time.

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

    I have the same idea, but haven't enough time to debug.

    This solution should be good. You have at lest 1/4 chance to find this leafs if you take two random vertices.

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

      For k=2 probability is 1/8. Because it is 1/2 to pick a leaf and 1/4 to pick a leaf from different subtree.

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

    I couldn't solve this in the contest, but I had a similar idea. I'm explaining your comment in a little more detail.

    Choose two vertices a and b, arbitrarily. Iterate over all the other vertices x and query if b lies between x and a. If that is true, then assign b = x. At the end of this procedure, you have that b is a leaf with n queries.

    You can repeat this process for a, and ensure that it is a leaf as well.

    However, You cannot assume that the root would lie on the path between the leaves a and b. This can be checked in O(n) queries by finding the length of the path between a and b.

    And this is where I got stuck.

    Are you suggesting that we could do a probabilistic approach after this? Because a and b would be in different subtrees with probability = ? Does anybody have a deterministic algorithm for this?

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

      Yes (I did it exactly the way you described). The probability that you don't find a path containing the root using this approach is . Then the probability of getting accepted is . Sounds good enough for me.

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

        First use n-2 query to find a leaf, and then randomize select another vertex, fail probability is now (1 / k)50 (reserve 10n query for the root finding).

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

          Nice, even better. Also notice that you can find the root with a Quick-select approach, which should be a lot better than 10n.

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

      After the contest I wrote a deterministic solution for problem F: Code.

      The idea is to start at a non-leaf node and go up to the root step by step. If we are at node X and X is not the root, we need to figure out which subtree of X is the largest one and what node in this subtree is the closest to X. This could be done by partitioning all the other nodes by subtree using at most KN queries, but it would exceed the allowed number of queries for large values of K. To fix this, observe that we can stop partitioning the nodes after looking at of them. For the remaining nodes, we need just to see if they belong to the largest subtree. With extra N queries, we can figure out the node in the largest subtree that is the closest to X. In total, we would need less than 2N queries at each step.

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

B was really good. :)

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

again a very good contest by Ashishgup.

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

Why this nlogn approach getting TLE at test case 10 in D problem.

https://codeforces.net/contest/1061/submission/46081755

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

any idea about the 8th pretest for D?

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

How to solve C?

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

    It's a kind of DP problem.

    DP & Divisor Problem = O(N) * O(D^1/2)

    So total number of operations is about 100,000,000... (N = 100,000, D = 1,000,000) I think this is correct approach because the time limit is 3 seconds...

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

    Let, dp[i][j] = number of good sequences of size j using elements from 1 to i and dp[i][0] = 1 for i = 1 to n. Now, for every divisor x of a[i], dp[i][x] = dp[i-1][x] + dp[i-1][x-1]. We can reduce the first dimension of dp array by iterating divisors in non increasing order for every element.

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

      Why do we need to iterate the divisors in non-increasing order ? Also can you please show how the solution works for some sample case, thanks.

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

        To reduce the first dimension of dp array. Let x be divisor of a[i]. We need dp[i-1][x-1] and dp[i-1][x] because we need to know how many good sequence of size x-1 and x can be made using elements upto i-1. So current element(ith) can't contribute in this count. If we ignore the first dimension and iterate divisors in non increasing order then for every divisor x, dp[x-1] and dp[x] is guaranteed to be the count of size x-1 and x up to i-1 elements since for each x we didn't make any update on dp[x] or dp[x-1] till now due to current element as a result of iterating them in non-increasing order.

        Consider 6 as current element. Divisors are 1,2,3,6. Take them in non increasing order. First comes 6 , dp[6] = dp[6]+d[5] as dp[5] is count of good sequence of size 5 up to previous element. Then 3, dp[3] = dp[3] + dp[2]. dp[2] is count of good sequence of size 2 upto previous element. And so on. If we iterated in increasing order we would have updated dp[2] before dp[3] due to current element and while updating dp[3] we would use this incorrectly updated dp[2].

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

    Taran106 was much faster at typing than me. Consider this to be an expansion to his excellent answer.

    Let's iterate the array from left to right. At each position we will update our answer dp[], where dp[5] gives you the number of good subsequences which have 5 elements, dp[6] gives the number of good subsequences with 6 elements, and so forth. The answer for C will be the sum of these dp values.

    Let's say we iterate the values and at some point we arrive at value 9. We want to update dp[] to consider all subsequences which can use this particular 9. Can we continue a subsequence which has 5 elements? No, because 9 would be the 6th element and 9 is not divisible by 6, so this would not be a "good" subsequence according to the problem statement. Ha! Let's look at the divisors of 9: {1,3,9}. Clearly we can only continue subsequences where this 9 will become the 1st, 3rd or 9th element. So for each divisor: dp[divisor] += dp[divisor-1] (Example: if we had 81 ways of creating a subsequence with 2 elements, then we will have 81 new ways of creating a subsequence of 3 elements).

    You might be wondering: isn't it slow if we iterate all values and then find the divisors for all values? Any number < 1000000 isn't actually divisible by many other numbers, so there aren't that many divisors. The only question is how do we find them efficiently. There's probably some fast way to do this as we go along, but I chose to pre-calculate divisors for all numbers.

    Here's the code for pre-calculating divisors:

    for (int divisor = 1; divisor <= n; divisor++) {
        int v = divisor
        while (v <= 1000000) {
            if (v exists in original input) then (add divisor to list of v's divisors)
            v += divisor
        }
    }
    
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I'm ready for -100 rating XD . Gratz to all who performs well.

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

Is E solvable by LP solver?? If can be, can someone give link to their solution using LP solver. Or can you point you some resources for LP solvers explaining their algorithm and rough complexity and also your library code..

Or we need to convert into max flow min cost network somehow?

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

    Intended solution was min-cost max-flow. We don't know about LP solver

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

    Sorry, this is F.

    This can be solved using simple randomized algorithm. See my code for ref: 46083309 Right now this WA because I messed up with calculating tree height -_-

    Idea is simple — randomly select two nodes. There is more than 50% chance that both of them will be leaf nodes. To check if the selected nodes say x and y are indeed leaf, query n-2 times and find out how many nodes are between them. Repeat for 50 times or so. It is highly likely that you will get two leaves. (As high as probability that quick sort is nlogn).

    Now you know the path between x and y. So the root node has to be one of them. Just query for each of them to find who is the actual root.

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

      I think you're talking about F, but they're talking about E :)

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

      It's not enough to find 2 leaf nodes (they don't always have a path that goes through root). For example, in the sample picture the probability of finding 2 leaf nodes which have a path through root is 15% (8/15 * 7/14).

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

    I've got an explanation for how I constructed MCMF graph in a comment below, if you're curious.

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

is D greedy? It passed pretest but it seems suspicious

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

    What greedy do you mean?

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

    Yes. keep assigning the latest TV where show is completed. And also check if that TV should be given and taken or should be kept with you.

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

      Is there any proof that this greedy approach works?

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

For question A why solutions with O(s) complexity passed. When I tried to hack it with n=1 and s=1000000000 I got an unsuccessful hack and the time was 608ms.

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

Really cool problem set!
Although, I do wish the contest was 2.5 hours instead!

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

Ignore.

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

What was the pretest 10 for Problem C?

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

Problem F was really nice, but it needs more time to solve.

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

Was O(n*sqrt(ai)) complexity in problem C too much or it could get AC?

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

    I used an approach with that complexity and got pretest passed in ~1500ms. Taken implementation into accounts, maybe? ;)

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

Does anyone solve E using mincost flow?

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

probably the way I solved B is the worst yikes ..

I can't look at my code so I don't miss more iq

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

The statements were clean and easy to understand, very nice :D

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

My approach for E:

First thought when looking at the problem: small n, lots of constraints, choosing vertices to maximize something, sounds like flow (this is CF so I am very skeptical of seeing flow because flow problems are very rare here, but I had a good gut feeling about this).

It's not immediately clear how to solve this problem using flow. For simplicity, let's imagine the problem with only one candidate and one set of demands. It does seem like some kind of choice-making thing, and one's initial thought might be to make a bipartite graph with demands on one side, and cities on the other, with edges from a demand to everything in its subtree of capacity 1, and edges from the source to each demand with capacity equal to the number of nodes required by that demand. The costs of the edges into city i would be  - ai. This, unfortunately, runs into some problems because there isn't any way to ensure that all the demands are met, and the flow for each particular city that gets chosen will be overcounted depending on how many demand subtrees that city is a part of.

Here comes what I believe is the key observation: if v is a descendant of u, then v's subtree is entirely contained in u's subtree. So, consider two demands (k1, x1), (k2, x2) where k2 is a descendant of k1. Now, for everything in k1's subtree that is not in k2's subtree, we can create an edge from the demand (k1, x1) to that city, and then we can create an edge from the demand (k1, x1) to the demand (k2, x2) with capacity x2. This way, the constraints from both demands are now taken into account and any compatibility issues will be reflected in the flow. However, one last thing is that we need to make sure that all the demands are met, so the way we do this is by making the cost a pair of ints, where the second number is the  - ai when appropriate and the first number is  - 1 if the edge is entering a demand node, and 0 otherwise. This way we will force our algorithm to use all the demands, if possible.

It turns out that adding the second candidate in is not bad, we simply create an identical graph but mirrored and add it as a third "layer" to our graph, with the mirror of the source being the target of course.

When we run MCMF, we first check to see if the first value is as negative as possible (this I believe should be the negative sum of all the x's in the demands) and if so, the second value should be the negative of our answer.

EDIT: I realize this explanation is not incredibly clear, but I think my code is pretty clear, so here's the submission: 46121195

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

Can Anyone explain how to solve B and C?

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

    Problem B:

    The order of the columns doesn't matter, so we can safely sort them in non-descending order. We can see that we must keep at least one block in each column.

    Let's denote Highest as the currently highest block kept, initially Highest = 0.

    Let's denote Max as the maximum height of all columns, s as the total number of blocks initially.

    Traverse through the sorted columns, with each column, update Highest by min(Highest+1, Height[i]).

    Let's denote the minimum number of kept blocks as Min, initially Min = n. Add Max - Highest into Min, thus, the answer would be s - Min.

    Problem C:

    This is a dynamic programming problem. Let's denote dp[i][j] as the number of valid subsequences that has i elements and the rightmost one is the jth one in the original array.

    Thus, the recursive function would be: .

    Obviously, we can't build an entire dp 2D-array (guaranteed TLE/MLE given the problem's constraints). Therefore, we'll only consider (and keep the dp values only in) the cases when a[j] is divisible by i. To do this, vectors and two-pointers techniques are required.

    You can see my solution for better understanding: 46075711.

    Hope these guides help! :D

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

      Hi iristran911, your explanation for Problem B is really nice but your implementation seems complicated.I followed your explanation and implemented it in a very easy way. see my submission: 46105126

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

        Nice one! :D

        I did mess up with things a little bit (kind of frustrated for submitting wrong B thrice previously), so the source code for B didn't look so good ;)

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

    C is dp + number factorization. At first find all the factors of arr[i] which are not more than i. f be the array of all those factors. For every number in f, the ans is dp[f[i]-1]. Update dp[f[i]] to dp[f[i]]+=ans[f[i]].

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

It was really annoying that formula for problem D was b — a instead of b — a + 1, which is more intuitive. Still, nice problem, good contest.

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

    Yes, that was nice. This contest was really well written. All tasks have pretty good and short solutions. Thanks to Ashishgup for that contest.

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

    It is just use x=x-y then it will be b-a+1

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

https://codeforces.net/contest/1061/submission/46079795

How can this code work for n = 1 and S = 10^9? It should give TLE since the loop is running 10^9 times. Can anyone explain this, please? It cost me 1 unsuccessful hack.

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

    Because the constant factor is super low. This isn't something with arrays and mods, this is just straight addition.

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

    And computers become faster and faster nowadays. It's not like 10^6 operations will take 1 second...

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

    The CF servers are really fast. That's it. If you do a for-loop of 1e9 iterations, it runs is less about 1 second. Also TL for A is 2s. You can try in custom-test.

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

Why is this code: https://codeforces.net/contest/1061/submission/46085323 giving RTE? Please help, thanks.

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

    Deleting elements directly on a set while you're working on that exact set will alter, or worse, mess up the entire iterators of that set completely. You should consider keeping the about-to-be-deleted elements in a dummy vector, and delete those after the traverse of that set is done.

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

    You are erasing and iterator from set. So when it do it++, it doesn't belong to the set. You should first move, and then erase. Some like:

    auto nxt = next(it);
    erase(it); 
    it = nxt;
    
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I never thought that O(N*sqrt(N)) be accepted on problem C. I just.. used all time to find better solution but failed.

Back to the blue ;(

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

Why in Problem A if you use Ceil test 35 gives WA?

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

    It should be ceil(s*1.0/n)

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

      But i used float?So, don't need to use this "*1.0". This is my code 46067360

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

        Daily reminder:

        1. Never use ceil() function. Instead of using ceil(n/k) use (n+k-1)/k

        2. If you want to use ceil() use it like this:

          (int)(ceil(1.0*n/k)+1e-9)
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks,but i changed my type o variable to double and the code receive accepted.And I understand your tip I'll use in nexts contests

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

    Use double instead of float ... 46090088

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

      I just realized this 1 min before you replied, but thanks for help.

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

random solution in F is intended? It seemed some people use random solution get accepted, and some get wrong answer on test 130~.

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

nice round realy thanx

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

In my opinion, the point difference between A and B should have been more than 500.

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

Really good questions and good contest by Jeel_Vaishnav

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

Test 43 of D- anyone knows what it is?

Update: I found the mistake.

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

    Could you tell us what is the mistake if we fail in test 43?

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

      I was maintaining a set of available tv's for a current time and this set was sorted in ascending order — the correct is descending as picking tv with latest finish time is optimal.

      Strange that it passed 42 tests!

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

        Thanks for your reply!

        I am also strange that I can pass 42 tests luckily...

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

        descending order according to the start time or end time? could you elaborate a little

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

          end time. I add a tv to set when it becomes free. It will get free at endtime.

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

            what I am is doing that for every tv i, I find that tv whose start time is greater than the end time of the current tv and continue this process until the set is empty or the cost of adding the tv to the current tv set is greater

            Solution link:

            https://codeforces.net/contest/1061/submission/46100043

            What is wrong in this approach?

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

I am unable to find what went wrong in B, I tried various tests but all of them are giving correct results. Since the test at which it failed is very large, I could not find the bug. Someone please help. Code
UPD: Got the mistake. :)

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

Well that was an embarrassing contest for me... I only solved A. But the problems were good!

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

Okay, so I got his problem while solving Problem C.

My code is NlogN where N is 10^6 (pre-computation). I have used an ArrayList (Java) to store all divisors for all 10^6 numbers initially.

It's getting time-out due to some reasons which I am not able to understand.

My code: my code

Can somebody look into this?

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

Someone know's why my sol: http://codeforces.net/contest/1061/submission/46083785 gets other answer on gnu and mvc?

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

WA in test case:43 of problem D

https://codeforces.net/contest/1061/submission/46100043 Couldn't find any error in the code.

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

嘤嘤嘤

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

Can anyone tell what is the error in test case 19? Please help me I have spent 1 day searching for the error but still could not figure it. https://codeforces.net/contest/1061/submission/46125841