Vovuh's blog

By Vovuh, history, 6 months ago, translation, In English,

My session is almost done and holidays are just around the corner. It means that it's time for another one contest! Happy New Year to all of you!

<copy-pasted-part>

Hello!

Codeforces Round #529 (Div. 3) will start at Dec/27/2018 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD: After the contest, you can discuss the problems in the community Discord server. Maybe I will take part in the discussion.

UPD2: Editorial is published!

UPD3: I forgot to thank my friend Roman Ajosteen Glazov for helping me with testing the round!

UPD4:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 sai_150050066 6 114
2 Skeercg 6 167
3 golubtsowroman 6 167
4 phungtienminh 6 170
5 forloop 6 183

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MZuenni 219:-8
2 ______-__________-______ 105:-39
3 bacali 81:-66
4 Random456 15:-2
5 gamezovladislav 11:-2

549 successful hacks and 540 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A ChiIIi 0:01
B GreacaEgalLuluOri2 0:02
C ChiIIi 0:05
D ChiIIi 0:12
E hahahahaha111 0:13
F kuchnaahopaayega 0:16

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

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

Didn't we just have a div 3 this week? Instead, why not have an educational? Since the difficulty of these contests is comparable to that of div 3 contests and it would be rated for a larger audience.

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

    We have an educational round on 28th already :)

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

      Yeah, so the questions could have been used for an educational contest someday after good bye-2018.

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

Awesome Anyway I love Live Contests so much

Great Job for your efforts on Writing and testing the problems

Happy New Year for all

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

Just first div 3 contest was the real div 3. (in problem difficulty)

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

If the difficulty trend in Div3 rounds keeps going, we might have to expect IOI level problems.

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

    Hey, it's IOI jury's problem that their task was easy enough to fit into div3 contest!

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

Eden Hazard the best player in the world right now

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

Div 3 is easy for me, give me div 4

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

is it contributed?

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

Good luck!

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

is A FFT?

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

hope this round results in a higher rating to all my friends ... Good luck to all

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

Why I see the "<copy-pasted-part>" again...Could you pay more attention when writing an announcement?

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

    At least he is spending time for making the contest. Announcement is not important more important is how he settled all the div3 contests so beautifully.

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

      I agree with you,but I think a good announcement is also important.

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

    Meh, why would you need a different announcement every time? Announcement notifies you of contest (in case you only look at main page and not the schedule) and reminds you a bit of the rules. This one makes its job pretty fine, I guess. It feels like a waste of time to write it from scratch every time.

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

****_ahaahaahaahha bad contest you have brain or no? wtf?_**** ****_Div1+Div2=Div3_**** ****_Eden Hazard the best player in the world right now_**** ****_is it contributed?_**** ****_hello i live in a very rural part of czechoslovakia and i am wondering if the contest is contributed and or rated for me thank you_**** ****_are you ssure? i cant find it x(_**** ****_ahahahahaha one two three 123_****

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

Just first div 3 contest was the real div 3. (in problem difficulty)

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

I hope it is not like the previous contest

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

I will do my best and I want to get gray

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

Good luck folks!

Image

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

Good luck to the server

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

Thanks vovuh for div 3 again. I like the higher frequency for div 3 these days.

Hope it's a great contest.

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

How to hack a solution.

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

    Go to standings then click on any + sign

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

Got 2 WA using pow() in C++ :( in problem C.

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

    Try to use byte shifts. For example (1 << 5) is equal to pow(2, 5). This is only for powers of number 2.

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

      Yes, I had corrected it in the last 2 minutes :)

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

How is there 100% systests already? O_o

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

    Maybe because it has already the pretests passed, I guess the test should happen after the hack phase is over, otherwise, maybe the machines were ultra fast today

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

Please help me with Problem E. Any hints?

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

    Yeah you can use a segment tree for it. The leafs should store the count to open and closed brackets.

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

    If a '(' represents 1 and a ')' represents -1 then the bracket sequence is valid if and only if every prefix sum is non-negative and the total sum is 0. When you change a '(' into a ')' it subtracts 2 from every prefix sum starting from that point. The opposite change has the opposite effect. Now just figure out which of these changes make the prefix sums non-negative and the total sum equal to zero.

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

thanks for an actual Div 3 round!!! on a side note, does anyhow know how to D? I struggled at it quite a bit.

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

    If two integers are in the same line, this means they're adjacent in the graph. The input gives you all n edges in the graph (though maybe not oriented correctly).

    Arrange the edges to form a cycle. You may need to reverse your output if the edges are facing the wrong direction.

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

      that's the problem I'm facing — how do you know if the edges are in the wrong direction?

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

        Look at the first 3 values. If they match what's given in the input, then the solution is facing the correct direction. Otherwise, reverse the output.

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

          I checked that reversing conditions for all n, if it's true i incremented the counter variable.At last if that counter having value equal to n i reverse the output else not.I got AC.But don't understand the reversing condition.Can any one can help?

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

      i tried topological sort but it gave me WA on test 3

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

        Topological sort doesn't guarantee a unique tree, which is what you want (as you'd be breaking the cycle otherwise). The generated trees depend on the order in which you visit the neighbors, which explains why you got WA on the third test.

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

    The approach I used is slightly different: if a and b are on the same line, then either b occurs on the line of a or a occurs on the line of b. We check which of these two is the case, and immediately know whether there is an edge from a to b, or from b to a. By doing this operation for every line, we calculate all the edges with the correct direction. The only problem with this approach is that it may give incorrect answer for n = 3; but outputting 1 2 3 always works if n = 3, since the all the inputs for 1 3 2 would be correct for 1 2 3, as well.

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

    ezaf dude, if a[a[i]] == b[i] or b[a[i]] == b[i] then next_to[i] = a[i], else next_to[i] = b[i]. then print 1, next_to[1], next_to[next_to[1]], ...

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

    Since n>=3 Consider if we are at node "a" and we know by input that node "b" and node "c" are its next nodes So, case would be like

    Case-1 : a->b->c Case-2 : a->c->b

    To verify which is the case , simple check that if "c" comes in the next_nodes_list of "b". Then it will be Case-1. If "b" comes in the next_nodes_list of "c", then it will be Case-2

    If it is case-1 , then it is sure "c" does not contain "b" in its next_nodes. If it is case-2 , then it is sure "b" does not contain "c" in its next_nodes.

    Use this above condition and put nodes in order.

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

    I solved it in the following way —
    1) every number will appear exactly 2 times, one in the vertex to which it is next and and secondly in the vertex where it is next to next.
    2) lets look for the vertices for which we get 1, and let then be called vertex a and b. so the order is either a b 1 or b a 1.
    3) we go to vertex a and look for b , if b is there it means b comes after a so the order is a b 1, or if not present the order is b a 1.
    3) After getting the order of first 3 element we will look for the adjacent vertices of vertex at index 1 [ 'b' in case of a b 1, and 'a' in case of b a 1], the vertex other than 1 will be the vertex at index 3, after we will repeat this process for all the vertices up to index n-3.
    my submission, time complexity O(n)

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

Problem E was almost the same as BRCKTS problem from SPOJ.

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

Easy round, I solved all problems

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

    You mean you consistently got WA on testcase 2 on all problems?

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

Does hacking help my rating?

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

    Yes, it helps your rating

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

    You don't get points for hacking in Div. 3. It helps you indirectly by making you place higher in the standings.

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

!(my last comment) = I love div3 rounds :P

anyway how to solve D it looked like a graph problem to me

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

    There is no need for graph. Using 1 as the first number, find the first 3 numbers with brute force. Then its easy implementation.

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

    It was a simple implementation problem.

    1. You just need to find a possible permutation of first 3 elements. lets say, p1, p2 and p3.

    2. Then you can easily find the rest elements.

    How?

    Finding part 2 is easy,

    As you know p2 and p3, you can easily find p4 because, only number after p2 other than p3 is p4.

    In other words, a21 = p3 => p4 = a22; And so on, we can find p5, p6....pn

    For part 1,

    Fix p1 lets say '1'; now p2 and p3 can be either a11 or a12. How to fix them?

    If a21 = p3 or a22 = p3 then p1, p2, p3 is correct; else p1, p3, p2 is correct;

    Check my submission: https://codeforces.com/contest/1095/submission/47575058

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

Can I get a hint for problem C:Powers of 2

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

    Check the binary representation of the input

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

    First find the binary representation to know the minimum powers necessary. Now, if we can represent n using x powers of 2, then we can also do it using x+1 powers of 2, provided x < log2(n). Think about how to get x+1 powers from x powers.

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

      Can you elaborate further by taking an example?

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

        Suppose you have x slices of pizza, but you want to have x+1 slices what do you do, divide one of the slices into 2, now you have x+1 pizza slices.

        Similarly, if you have minimum powers of 2 necessary to make a number. you can keep on dividing the numbers till you get k numbers.

        you can also do it recursively. See my codes: 1) Recursive 2) Iterative (Using a queue)

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

          i cannot understand why u use k-=mn; then func( x, min(k+1,x) ) in your code can you eloborate please

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

            Well, it's hard to explain because I have done it in a messy way, What I am just doing is that for each number in binary representation of n, I keep on dividing it till I have k numbers. For example: Take n=10 it can be represented in minimum powers as: 8+2

            I keep on dividing 8, then I go to 2 then I keep on dividing it. When I have k numbers I stop dividing.

            You can build your own logic for this.

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

Wonder why Problem F if there are Multiple index have smallest cost pick any of them to build edge to is ok

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

    you can refer to MST Algorithm like Prim and Kruskal

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

      i means the given a1~an may have multiple of them have same smallest value and why i pick any of them build edge connect to others the answer will be same

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

        you can consider why MST Algorithms like Prim and Kruskal do not care about that

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

    Assume we've already chosen which special edges will be present in our tree. We need to figure out the cheapest way to join the connected components that they induce.

    The total weight for the other edges is some expression of the form ai1 + ai2 + ... + aik. We have to choose at least one vertex from each connected component induced by the special edges, so the minimal possible value of the expression for fixed k (ignoring any other restriction) is obtained by first adding the smallest ai from each component, and then adding the smallest ai of them all however many times. By choosing any vertex with minimum cost we will get exactly this value for the expression, so it doesn't matter which one we choose.

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

Can F be solved by Prim's Algorithm?

I thought this is MST problem, but how can we find MST when we have so many edges? I know we can use binary heap, priority queue and some data structures on Prim's algorithm, but I don't get how to fit in time and memory.

Plz let me know if I'm missing something.. (I'm not even sure if this is a MST problem or not)

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

    It is MST, with an extra idea. It turns out the only edges with costs ax + ay that we need to consider are the ones that involve the vertex with minimum cost.

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

    It is a MST problem. Use the set 1 as the given edges. find the smallest ai and make n-1 edges this vertex to other vertices. Call this set 2 of edges. combine both sets and apply prim's algo.

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

Any one can help me with problem E! I have no idea how can i solve the problem!

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

I'm getting a wrong answer by the checker but if I compile it elsewhere I get the right solution.

The checker's log read: wrong output format Unexpected end of file — int32 expected

Can someone explain what is happening Submission

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

    It means that your solution just terminated when jury has some output left to check.

    In your submission, jury had one more integer number to check, but your execution ended without giving an integer.

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

      But if I compile the same code elsewhere I'm getting a correct answer as per the jury.

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

        Can you specify about your machine or where you compiled?

        I mean, some links to online compiler or you machine's OS, editor, complier

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

    Should I report it to someone?

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

In Problem D, can the permutation be in any cyclic order (clockwise or anti-clockwise)? Like for this test case 5 3 5 1 4 2 4 1 5 2 3

is this 1 4 2 3 5 also a valid answer?

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

    No. 1 4 2 3 5 is invalid. You must consider the order. (i.e standing in front or back matters)

    You should check clockwise or counterclockwise. After that, starting point doesn't matter.

    1 5 3 2 4

    5 3 2 4 1

    3 2 4 1 5

    2 4 1 5 3

    4 1 5 3 2

    These are the only valid answers for first example.

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

      I tried to think of making a bi-directional graph and then apply a DFS. But it didn't seem to work out. Not able to figure out how to determine the order?

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

Problem D is ambiguous, I cannot understand what he want. can anyone help me please. thanks in advance.

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

    There's a directed circle(a premutation p), giving the two vertexes behind every vertex, you should print a valid order.

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

Why all Java solutions on B are getting hacked? Although they all seem correct.

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

    MZuenni on fire!

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

      Java's DualPivotQuicksort used in Arrays.sort is deterministic and therefore in O(n^2) they all get timelimit by that...

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

    May be for this reason : Link

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

      yes thats correct. p.s. for all people writing me direct: i have reached my codeforces message limit and therefore cant respond for the next hour...

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

Why did my solution for F Link failed?? Update:Solved

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

    your variable mst_cost is int.... it should be long long

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

for problem D, why WA??? Judge says wrong output format Unexpected end of file — int32 expected

link to my code is Your text to link here... please someone check it...

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

    You should be printing 5 numbers and you only printed 2

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

      yes, that's the problem. IDE prints all the five values but, judge shows only two. I'm not getting the reason.

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

        1) I had the same issue before, that happens because the current compiler makes some "corrections" to the code at runtime, to see the exact result on your ide (in this case Codeblocks) you should make it follow the C++11 standard as seems in this link

        2) About your code, I got it working removing adj = new list<int>[n + 2]; and vis = new int[n + 2]; but instead delcaring adj and vis like this list<int> adj[200001]; int vis[200001];

        It's a good practice to declare your variables as globals and at the same time with the max length posible since that way only you can be sure they are fully initialized (the default compiler in our machines does some tricky stuff when a variable is not propelly initialized and instead of giving an error it tries to make it work which makes us think it works propelly meanwhile codeforces and other evalutaros don't do that)

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

A lot of people got hacked on Problem B, including myself. Does anybody know what the issue could have been?

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

    Hey:)

    So Java's Arrays.sort() uses quicksort, and the average runtime is nlogn but worst case runtime is n^2. The hack is an anti-quicksort hack. To fix this, you should declare the array as Integer[] rather than int[], since merge sort is used to sort objects, which runs in time.

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

      Thanks! I'll remember that for future reference.

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

What does this statement mean in problem "F. Make It Connected"?

You don't have to use special offers: if there is a pair of vertices x and y that has a special offer associated with it, you still may connect these two vertices paying ax+ay coins for it.

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

    If an offer with cost w is included, the cost of building an edge connecting x and y can be either ax + ay or w, it's up to your choice (yet obviously if you're really going to build that edge you would want the minimum value between them).

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

    For two vertices x and y, there may be some special offers. You may potentially use one of these offers during the construction if you want to connect x to y. However, you can connect x to y without using any of these offers, as well. In that case, the cost of connecting x and y is given by ax + ay.

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

Today during contest I got WA on test 1, for problem D. While it ran well on my IDE with correct answer. My submission: https://codeforces.com/contest/1095/submission/47569625

Later after 20 mins I realized, I had left a return false; statement inside the check() function. After adding the line it got accepted. (https://codeforces.com/contest/1095/submission/47575058). If it wouldn't have worked on my IDE I would have fixed it and submitted in matter of seconds, rather than 20 mins of trying to find some error which still works fine on my IDE. Any ideas why it worked fine for all sample cases plus my own custom cases, on my IDE but not on cf server?

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

    It's called "undefined behaviors".
    Since the function return a non-void value and you left its ending ambiguous (not stating explicitly if it would return true or false), so depending on the compiler and environment of your PCs, IDEs or online judges, the returning value will fluctuate.

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

declare the round unrated for java users whose B was hacked!

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

      why should that happen?

      there is no difference between getting hacked or failing the system tests (there are also enough problem setters who directly include such testcases for systemtests so no hack is needed).

      And you will learn from this and will think about this the next time you use Arrays.sort...

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

        but that works perfectly well with c++, as it is faster

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

    they gave the java users only 1k ms they should have given 2k ms

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

For java we are allowed 2000 ms for a problem in which the limit is 1000ms but here we got a tle at 1000ms

submission here: http://codeforces.com/contest/1095/submission/47602564

please rectify this

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

      the problem is NOT that java is generally slower! the problem is that you used an algorithm which is in O(n^2) which is clearly to slow!

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

        So according to you what could be an alternative to Arrays.sort() for getting O(nlogn)?

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

        According to the documentation of Arrays.sort()

        Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

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

        hey i read your blog. Thanks for the information, I got what you were trying to say.

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

I Learn a very important thing in this contest. DO NOT FEAR to read hard problems. I am able to solve problem F easily with kruskal, but i didn't solve it during the contest because I always thought that if I can't solve easier problems (problem C and E), i can't solve the harder one.

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

Hi Everyone,
I got a runtime error due to wrong evaluation of log(n)/log2 by the CF compiler, but it is being evaluated fine in my own ide, and a number of online compilers. Isn`t it unfair for me. my submission,problem c. For input 8,1 CF compiler is evaluating it as 2, where as it should be evaluated as 3

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

    Nope, it crashes in your while

    while((k-cnt) != 0){ ...
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes, but that`s because 'sz' was evaluated as 2, if it would have been evaluated as 3, I would have got "YES 8"

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

        Gotcha, it's weird behavior. As to why, i guess you should consider that doubles aren't exact just as the result of log() isn't, so the division isn't exactly 3. You should avoid doubles whenever possible, in this case when you want to check over log in base 2 you should use bit operations.

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

    Try using log2(n) instead of log(n)/log(2). Idk, it may work or not, but you should have gone for ceil value anyway.

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

When will the ratings change?

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

I love Vovuh's Problem set...He is making Div3 great

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

My Submission 47584196 was rejected by Codeforces compiler because the values of INT_MAX and LONG_MAX are apparently same on codeforces it works perfectly on my laptop! Isn't this unfair to me? What can i do about this now?

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

Could someone help me with problem E? I think I have not understood what is a regular sequence. In the first example — (((()) , can I change the second bracket to get ()(()) or change the 4th to get ((())) ? I can insert 1 and + into them such as (1)+(1+(1+1)+1) and (1+(1+(1)+1)+1) but why are they not regular ones?

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

    Please read the description carefully!

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

What is the solution to Problem B? I am getting WA on test case 6.

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

    There is 3 cases. The first one is to take one element that is not minimum nor maximum: The instability doesn't change. The second case is to take one element that is maximum: The instability will be the maximum of the new array minus the minimum of the array. The third one is to take one element that is minimum: The instability will be the maximum of the array minus the minimum of the new array. So the answer is min(second case,third case).

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

In problem C, Many solutions are getting runtime error on test case 10 that is 1 1 But it is showing right output in almost every other compiler/IDE

Here's my code. https://ideone.com/qVAsiL

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

    I suspect that it is Undefined Behaviour. For test case 1 1, you pass 0, 0 as your arguments to the function rec(). It will return when y == 0 part without actually initialising vector V. So when you are executing this line fn(i,V.size()-1,0), V.size()-1 gives random big values and can be machine dependent.

    EDIT: I was right. Solution. It passes after removing ambiguity I mentioned.

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

Is there any editorial posted for this Div3 Round?

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

Can we have the editorials?

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

How to approach problem E?

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

    try to think when flipping a single character will make the whole sequence good , character can be "(" or ")" at each position so just two case, see what should be the number of EFFECTIVE "(" and ")" on both sides of concerned index. there difference must be one(you can verify). but we must be careful that either left or right side should not have parts which cannot be balanced either. while going left to right(maintain array A) try to maintain the net effective number of "(" at each index, means for all 0<=i<=n-1 store number of free "(" from [0->i] , and do same for ")" while going from right to left(maintain array B) maintain num of free")" for each i .

    on which indices we should perform the tests because other indices may give positive test instead of them they are wrong->

    if for any l>=0 A[l]=-1 then we should not check for indices greater than l (convince yourself by examples) because they will never effect left part in any better way so range to check will be [0,l] l can be at max n-1 ,similarly in array B for index i<=n-1 check till you approch 0 or where it is negative first time.

    check should be made finally on intersection of [0,l] and [m,n-1] :)

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

    Calculate balance of given string. Let bal[i]=balance of substring [0;i]. (Balance is a sum of opening and closing brackets). Now go through this array and check:

    1) if bal[i-1]<0 at any moment, then you can stop and print answer, because you won't be able to make correct bracket sequence later anyway.

    2) if s[i]=='(' then by changing it to ')' balance will decrease by 2 from [i;n-1] in bal[]. So you need to check that minimum in bal[] from i to n-1 is >=2 and bal[n-1]==2. If it is true then increment answer variable.

    3) if s[i]==')' then same logic. Just check if min>=-2 and bal[n-1]==-2.

    To find minimum on interval you can just use multiset. See my solution

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

      Your solution is pretty clear and easy to understand..Thank you. I understood the logic behind the problem.

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

      why we have to check min???