vovuh's blog

By vovuh, history, 6 years ago, translation, In English

<copy-pasted-part>

Hello!

Codeforces Round 506 (Div. 3) will start at Aug/24/2018 17:50 (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 awoo Piklyaev, Maksim Neon 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>

UPD1:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 problem_destroyer420 5 209
2 syh0313 5 225
3 VinceJudge0 5 230
4 SaIah 5 234
5 EctoPlasma 5 241

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 506:-92
2 antguz 121:-20
3 Anguei 50:-11
4 taran_1407 41:-1
5 zdw1999 41:-2
6 applese 40

1217 successful hacks and 926 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A i_f_y_m 0:03
B SaIah 0:03
C SaIah 0:13
D _kawaii_neko_ 0:17
E syh0313 0:43
F iamunstoppabIe 0:19

UPD2: Editorial is published.

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

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

just have strong pretests because then only hacks make sense

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

Will be original cf round on September 1st?

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

How are you going to detect the people who hack solutions having some if statement to remove them from standings table? Is there some algorithm?

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

    I'll try to check all peoples, who will hack their own submissions, manually and check if in their code will appear parts like if (n == 1234) return 1; and similar.

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

      Why is it even allowed for people to hack their own submissions?

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

        Not all hacks of their own code are such as I say above. Many hacks of your code can be useful because there are can be not complete testsets in the contest. But hacks of kind if (n == "blablabla") return 1; are useless and make no sense.

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

          Few contests back, there was a comment mentioning a person hacking someone else in the same room but both the accounts probably were being used by the same person. This way it won't show up in the list of people who hack themselves but this practice needs to be curbed.

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

            We are trying to undermine all such cases but it is very hard to do that without any mistakes or omissions.

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

          Ah, so you build a tricky/big case and let codeforces check the correct answer for you. Never thought about it, makes sense!

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

      People do like this mostly for dropping their ratings purposely. That is repulsive addiction。

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

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

move contest time 3 hours later .. this time is not good

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

    Why did you change your profile picture?

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

Well Well Well

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

Warning, this is a joke, don't feel bad if you are div 3.

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

    yeah didn't even felt the joke.

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

      yeah, it seems is not funny, I just wanted to hide in a subtle way a sad truth

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

        don't underestimate anyone,who knows an extremely low rated div.3 guy is doing some other wonders.

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

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

    Too real

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

DIV3 ROUND! It's time to challenge your coding skill together with coding speed!

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

coming expert , i wish .

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

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

Hope there will be strong pretest. Don't want the codeforces changes to the hackforces. Thank you very much.

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

Hope that I will become expert after this contest. :)

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

Why the 15 minute delay ?

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

    standartno

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

    So that no of registrations crosses 9k mark...

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

    For few seconds, the website crashed as well. Maybe the delay was to fix the issue

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

Delay :(

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

The Wait!!!

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

00:00:15 -> F5 -> 00:15:00

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

Someone please make a Codeforces Delay Predictor -_-

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

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

how to solve A?

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

Before:00:00:15 before start, Now:00:08:00 before start, Will-be:This round will be unrated :)(JUST JOKING)

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

Hackforces, Delayforces, Memeforces, Mathforces, who's next??

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

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

Is it Div 3 contest? I think it's too difficult

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

<copy-pasted-part>

<copy-pasted-part>

.......ANNOUNCE.....

</copy-pasted-part>

</copy-pasted-part>

You may do in such way, we'll understand

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

I am getting wrong answer on test 1 problem A and can't even figure out why. :'( edit: figured

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

How to solve problem D ?

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

    I didn't actually give it a go, but I believe you should calculate ((V[i] * 10 ^ j) % K) for every i and j and then, for each j, build a frequency array / map of these such values. After that, it's easy to see that for every V[i] the amount of elements you can pair it up with is freq[j][K — (v[i] % K)].

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

this is not div.3 contest

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

    i hate vovuh

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

      This is sad :(

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

        Although I found the problems harder than the last div3 contest, I still enjoyed it! At the end of the day, I'm sure I'll come out of this round knowing more than I did before(once the editorials are out of course xD)

        So a relatively difficult div 3 contest(compared to past div 3 contests) isn't necessarily a bad thing :)

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

        Vovuh why not increase the time limit to 2.5 hours because i think most probably div3 contests have a large fraction of people who always thinks that if i could have given 15 more minutes i could have definitely done one more problem(i m one of them).. i mean this just boosts up the confidence and belief.. this suggestion may be immature but i feels at least 2.5 hours should be given for 6 problems to do justice with the contest,those who solves first will have better rank whether the time is 2 hours or 3 hours.. although these contests are awesome always if one try to solve problems before or after contests .

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

I try to solve Problem B with a solution of upper_bound(a[i]*2) but fails. How to solve this?

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

    You miss read the statement.

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

    I solved it with sliding window

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

      Even I tried the same but got wrong i case 4

      int ans=1,i,j=0;
          
          for(i=1;i<n;i++)
          {
            while(a[i] > 2*a[j])  
            j++;      
            ans=max(ans,i-j+1);    
          }
      

      Could not find what is missing. Please help. Thanks

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

In problem F, what does this mean : "all tiles of at least one color would also form a rectangle." ?

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

    At least one color must form a rectangle i.e if you remove red, blue must form a rectangle or if you remove blue, red must form a rectangle

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

    I also was not able to understand the problem statement because of this. According to Firastic, the intended meaning is quite different to what they wrote.

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

What is pretest 4 for B?

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

    A pretest of this type: your solution should be based on the statement and not the samples.

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

      Got it, but that was still a shitty statement. Could be framed better.

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

Welcome to Codeforces Round #506(Div.2)

Edit: only A isnt a Div.3 A problem.. B is easy but the trap in reading the statement is just so unexpected

other problems are Div.3 problems

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

pretest 6 in A. I want to know that sh*t and yea, i still hate vovuh and his friends who always writes shity contests. (I'm not afraid downvotes)

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

How to handle the case in D when 2 | k or 5 | k. Is there an easy way to do this than to calculate modulus for all possible factors of k which still aren't coprime to 2 or 5

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

    Your approach seems not to be on the correct path. You may want to think it differently.

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

What's pretest 7 on C? I can't figure out where I screwed up.

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

    My guess is that it is something like this:

    300000
    1 100000000
    2 100000001
    3 100000002
    ...
    300000 100299999
    
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

There should not be hard deadline time to end the contest, atleast 20-30 seconds extra should be given, given the initial load on the system. I missed the D by 1 second today.

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

    Same here, I putted the code and clicked submit and there was almost 10 seconds, but it wasn't submitted :(.

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

    Then that hard deadline should have a hard deadline. xD

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

I solved C with Segment Tree, is there other topics solve this problem? because I feel that it is easier than SegTree when I saw someone solved it quickly.

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

    only the top 2 numbers matter.


    sort(l , l+n); sort(r, r+n); reverse(l, l+n); int ans = r[0] - l[0]; if(!notin(l[0], r[0])){ ans = max(ans, r[1] - l[0]); ans = max(ans, r[0] - l[1]); } else ans = max(ans, r[1] - l[1]); cout << max(0,ans) << endl;
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I will see your submission for more details.

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

        Initial idea is that if you consider all the segments, the intersection is formed by lowest right end and highest left end.

        Now, if you want to improve your intersection, you would want to either:

        • Extend the right end of some segment
        • or Extend the left end of some segment.

        Now think about which one would you choose.

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

          Yeah I got it now, thank you very much :D

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

    Easy O(n log n) with multiset 42096347

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

can someone plz tell me what is wrong in this approach for E? A node ( > depth 2) may be reached through child or parent who has a direct edge or there is a direct edge to this. SO, a) if i want to reach this node from parent, then for each child there must be a direct edge or any of their children must have a direct edge. b) if i want to reach this node from children, any one can have a direct edge and others can have direct edge or their children can have a direct edge.
c) if i have a direct edge to this node, then i can take the min( a, b, c);

Can someone plz tell me what is wrong here, here is the link, https://ide.geeksforgeeks.org/Nn0MdojmeD

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

Will an O(10 * n * logn) solution pass systests for problem D? Link

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

Can someone tell me about solution for problem E ?

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

    DP d(i, j): i represent the index of the nodes, j represent the depth of node i; http://mirror.codeforces.com/contest/1029/submission/42054107

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

    The complexity is O(n)

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

    Root the tree at 1. Sort the nodes by their depth in descending order (so we start with leaves). Make an array to store if we can reach a node in <= 2 steps. Loop through the nodes by depth and if not marked create a connection to the parent of that node and mark all the neighbors of the parent in the array.

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

    I was trying it with dp, though couldn't complete the code within contest. My idea was to consider states if there is an edge from 1 to v or not. if there is an edge from 1 to v, then there can be edge from 1 to childrens of v or not. if there is no edge from 1 to v, then there must be an edge from 1 to atleast one of child of v

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

Seems like problemsetters have been missing how problem A should be :D for the last few contests.

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

Am I the only one who misread the problem statement of B? I guess no.

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

problem F, finished in 10 mins after contest :((

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

    during the contest I coded it in 8 minutes but I got WA37 did you get the problem in this test?

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

      the same problem, in the last 5 minutes of the contest, I knew my mistake but i did not have enough time to code :|

»
6 years ago, # |
  Vote: I like it 0 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

    The intersection length of n segments is min R - max L (invalid if it's negative), so just ignore each segment and evaluate length, i used multiset to insert/remove in O(log n). I'm doing this for n segments, so the total complexity is O(n log n).

    Code: 42096347

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

what's wrong with 37'th in problem F ?

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

    Small infinity(got wa on 37 too).

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

    2 large prime numbers, so only rectangle with side 2 will pass

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

    the area (a + b) can only be divided by 2, some people have the answer 6179835302 because they devide it by 64728, but we can't color the rectangle like this because " all tiles of at least one color would also form a rectangle ". The solution is check that are there any divisor of a (or b) (called i) that i <= (divisor of S (called div)) and a/i <= (S / div) so we can have a rectangle with size div * (S / div).
    my code : https://ideone.com/3bFclD

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

Nice contest : )

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

for me the statement on b,c are very confused after explanation b become clear and I'm solve it, c after contest solve it its easy but not clear with this statements.

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

Is it possible to share ideas of hacks with other people before the end of the hack phase? Does it violate the rules?

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

Honestly, when I saw problem A, I thought for a second if it is really Div 3 (and I haven't passed A). It was quite good, except they were a bit too hard for newbies (like me), and frankly some problems were more suitable for Div 2, or even Div 1 instead. Still, I appreciate the hard work of today's contributors for thinking up the problems!

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

is it a rated contest or not ? also i can't understand the General announcement, which say (We will publish separate standings for trusted participants after the contest.)

:) :) :)

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

 I wish I could code this fast XD. Parallel Programming :P

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

seems like another halyavin day , nearly 450 hacks . wow again .

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

    I can't comprehend how do you even hack. There are too many solutions and most of them are fully correct.

    Can somebody explain, please?

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

    It seems he is the one brought done the submissions of D for ~640 to ~150

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

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

    lol,halyavin is really good at hacking,I have been hacked by him for many times. But I maintain it also help me develop my skills,because the probability I will be hacked decreased more now at least.

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

      can you please explain your code for E?

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

        Firstly, we get a tree rooted by 1. We get dep[i] to express the depth of i in the initial tree, and let's call a vertex is right if the distance to 1 equal or less than 2. Obviously, if a vertex i with dep[i] <= 2, then the vertex is right. Our goal is to make all the vertex right. Consider we link 1 and a vertex i, it makes all the vertexs which are adjcent to i right. So in my solution, we first sort all the vertex in the decreasing order of dep[], and consider them one by one. If we find a vertex i is not right yet, then we link 1 and fa[i], which fa[i] is the father of i in the initial tree, and it will make all the vertexs which are adjacent to fa[i] right. It can be proof that in this way we use the least steps. XD

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

          why do we choose the vertex with largest depth first?

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

            Because we have to deal with it, if we don't solve it this time, we must solve it next time. And solve it from down to up do not influent others, because all the vertex in this subtree are right.

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

    Can I have the original picture plz?

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

Did anyone solve B using dp and implicit segment tree? I guess it's an overkill, but to me it seemed better than to guess that the solution is always a continuous segment.

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

    I guess that this solution would be the best if the sequence was not in increasing order.

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

    You can try to prove it during the contest. Just imagine you have already some subset, with the last element at index i (the array is sorted, and all of the elements with indexes > i are bigger). Now you want to try to add another element to this subset, suppose you added element j (j > i+1). Now you can see, that if element a_[j] <= a_[i]*2, the same applies to other elements in an interval [i+1, j-1] and it's always worth it to take smaller element. But why? Consider x as the smallest integer in the subset we consider at the moment. It's easy to see we want to minimize the largest integer in our subset (lets name it y), so 2*x >= y. This strategy applies to every element we consider in our subset — concluding — our subset will always be contiguous (if the array is sorted). Please correct me if I made some logical mistakes.

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

in problem B 2 1 2

how is the answer 2 ?

i knew that the statement contained <= but i thought that it is <

how isn't there any pretest to check this ?

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

Just curious, how could someone (or to be precise, antguz) confidently hack my O(10 * n * log(n)) solution of problem D to successfully give a TLE verdict?

My hacked solution: 42049909

My re-submitted one (with some slight optimizations, still TLE on other similar tests, which gave the conclusion that my solution ran at somewhere around 2.5-3s): 42071241

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

    I had the very same issue as you so I thought of helping. TLE will go if you use unordered_map. Link to your submitted solution.

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

      sigh Ah yes, unordered_map... Thanks! :D

      P/s: Still seeing that got TLE is insanely weird :-P

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

    I think the issue is not in usage of map instead of unordered_map, but it is in that you used the operator [] when you wanted to add values to the result.

    Instead, you should check if a key you want to add its value was already existed in the map by the member function count(), and if yes, then add the value of that key to the result.

    Because when you use [], if the key in [] is not existed yet, this operator will create it, so the size of the map will increase by one, and so on. So, the time needed to access the map will also increase with the increasing of its size, thus you will get TLE.

    Check my submission for more details.

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

      Well, just as I was discussing with one of my friends about this exact issue.

      Yeah, I was critically careless in that, thinking O(10 * N * log(10 * N)) will do no harm. I was stupid :-P

      Guess this should be a huge lesson for me from now on. Thanks! :D

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

      Thank you very much!

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

Can anyone please point out why my code is giving TLE for problem D? I have tried all the optimisations I could think of at my level. It would be really helpful if someone can help me out here. Thanks in advance !!

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

Are there any better solution in problem B? I use dp and RMQ to solve this problem, but I think it's too complex for the problem B in div 3 contest :((

I use F[] with the meaning that F[i] is the answer ending at i. I use lower_bound to find the minimum value that more or equal A[i] / 2 (called j), than find the maximum value of F from j to i — 1.

P/s : If the array isn't in increasing order, what should we do?

Edit: If the problem like this : find the maximum length of a subsequence ( by delete some elements ) (like LIS) but a[i] <= a[i-1] * 2 in this subsequen. what will we do?

eg:

Input n = 3 array[] = {2, 1, 4}

Output 2 ( 1 and 4 )

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

    You can traverse greedily in O(n): find the longest increasing subset that the criterion aij + 1 ≤ aij * 2 holds true.

    So, of course, if the array isn't sorted yet, we can just sort it beforehand — nothing special.

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

      Thank you.

      If the problem like this : find the maximum length of a subsequence ( by delete some elements ) (like LIS) but a[i] <= a[i-1] * 2 in this subsequen. what will we do?

      eg:

      Input n = 3 array[] = {2, 1, 4}

      Output 2 ( 1 and 4 )

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

    Excluding the last element (i.e., the biggest), you can just calculate the length of the largest interval I = [L,R) such that I[R-1] <= 2 * I[R-2] holds.

    So L starts at 0, R at L+1, keep increasing R until the property I[R] <= 2 * I[R-1] is false. Then reset L = R, and repeat the process until R >= N. After doing that, the answer is the max R-L difference you've found in this process. There is one corner case: N = 1.

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

Freakin' A Again >(

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

In problem D, using unordered_map gives TLE while submission with map gets accepted. I can't figure out why.

http://mirror.codeforces.com/contest/1029/submission/42051858 (AC code)

http://mirror.codeforces.com/contest/1029/submission/42063201 (same code with unoedered map)

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

    Some special data can make the complexity of unordered_map become O(n).(like test 64. I used pb_ds and got accepted after the contest. :P

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

      knew this thing but ignored it don't know why -_-

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

    42061028 this got hacked(map) -> tle verdict on hacking 42073938 this got tle at test 66 unoredered map

    any reasons?

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

    Unordered_map is implemented using hash table. So due to collisions in the worst case it can be O(n) for accessing an element. But map guarantees O(logn) for access.

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

CodeForces is the worst. Solution 1 Solution 2 Both solutions are the same. So during system testing, my correct solution fails only because of the load on CF server, which is basically CF's fault. So now I've to pay for it to settle for a worse rank.

And I know even tagging MikeMirzayanov won't do anything because these kinds of crap has happened before and nothing was done.

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

    Your solution was already borderline. Also, time is actually calculated by the no of clock cycles your solution takes to finish execution, and not wall time, so I don't think it has anything to do with server load. +-100ms in similar code execution can be expected

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

      Yes I know it was borderline. It had passed test 7 in 2.8 s during the contest. But I think it's the server load only because I've read more such cases in a few contests held earlier and my solution to D also took more time to execute than it took during the contest.

      In general I have observed that borderline solutions fail only during system testing leading me to believe that load during system testing is the only reason, because otherwise they still pass.

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

When will ratings get updated?

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

I don't know why this submission for problem C 42040684 got hacked and then I again made the submission 42076792 with the same code and it passes all the tests, this seems to be a serious issue, as its the fault of the system which gives different execution time for the same solutions and unexpected time penalties. I think the hacked test case is the last one #71 ..Plz have a look at it.....

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

Was the time limit too strict for problem D?

42055423 Uses unordered_map and gets a TLE; 42076582 Uses cc_hash_table and gets an AC.

Time complexity of both solutions is O(11*N).

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

Problem D makes me very sad.

I write a O(n * logn * 11) then get a TLE on test 28.

I make some optimization to O(n * logn * 10) then AC.

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

When will ratings change?

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

How to solve problem D?

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

when will the editorials be out??

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

The same code for Problem D running on G++11 gives TLE on test 50, and with G++14 gets Accepted. I don't think such stiff time limits give fair assessment.

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

How to solve D? just an idea will be helpful

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

    Assume you are at a point ai and assume ai is l digits long. Then ai gives a solution when there exists aj in the array with the property 10l × aj + ai. has a remainder 0 when divided by k. With a bunch of precomputing you can find how many ajs have this property. However you have to be careful to remove the case when i = j. Also for the precomputing using 10 maps or unordered_maps for each of the powers of 10 you need seems to lead to TLE. You can avoid this issue by instead sorting and using a binary search.

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

UPD: Sorry I got it, the answer of my idea is 2 + 2 * (a + b). So, never mind.

In F, is there any statement in the statement denys us from coloring the tiles as a rectangle with dimensions (1 * (a + b)), so the answer will be a + b + 2?

Because in the given samples (and all testcases I guess), the answer with my idea is always less than or equal to the answer from these samples.

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

For Problem D — TLE issue

People here find the Time limit strict ( even I did ) , but actually it isn't that strict. The only issue while using map which almost everyone is facing is :

If u simply do ans += mark[digits][requiredmod]; then even though that required mod doesn't exist in the map, then also it will be added to that map and now the size of the map = (actualsize+1), and if you do this n*10 times the size of the map would increase and therefore the time to search as well

So what u need to do is first search whether that element is present in the map and then add it to the answer, as shown below :

if ( mark[digits].find(requiredmod)!=mark[digits].end() ) ans += mark[digits][requiredmod];

This is the only difference in my accepted and TLE solution.

Accepted Solution : http://mirror.codeforces.com/contest/1029/submission/42081763 TLE Solution : http://mirror.codeforces.com/contest/1029/submission/42082128

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

    "then even though that required mod doesn't exist in the map, then also it will be added to that map and now the size of the map = (actualsize+1)". It is your assumption or document that says so ?

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

      No it is not my assumption. Very simply, you can compare the memory of both of my solutions. Why open the documentation when you can code... LOL.

      map < int,int > mark;
      mark[1] = 2;
      cout << mark.size() << endl;
      int val = mark[0];
      cout << mark.size() << endl;
      

      Output :

      1

      2

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

      Tried everything and still got TLE on different tests. After that, I read your comment, changed that line, and got AC with 342 ms. Incredible :P

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

      It is true, whenever you wanna create a new element x in a map you can just do

      M[x];

      This is the same case, doing

      ans += M[ x ][ y ];

      Will always create a new element [x][y] if it didn't exist.

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

    For me, changing unordered_map to map helped me solve the TLE issue.

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

DP Solution for Problem E

DP state : (node, cur, par)

node -> The index of the node

cur ( 0 or 1 ) -> Whether the given node either has or is supplied with an extra edge connecting it to the root

par ( 0 or 1 ) -> Whether the parent of the given node either has or is supplied with an extra edge connecting it to the root

Now 3 cases arise :

cur:1 -> sum over all children {min(solve(child,1,1) + 1, solve(child,0,1))}

cur:0 par:1 -> In this case the current node has a path of length 2 to the root by going to its parent and then from parent to the root. sum over all children {min(solve(child,1,0) + 1, solve(child,0,0))}

cur:0 par:0 -> This is the most important case. Main Point : This node doesn't have a path of length atmost 2 to the root, so it has to make use of ATLEAST 1 of its children*

Case 1: Leaf node -> You need to make an edge straight from here to the root. ans =1

Case 2: Internal node -> Select atleast one child from which you will make a direct edge to the root. Code for this :

vector < pii > vec;
int sum = 0,idx = 0;
for ( auto child : adj[node] )
{
    vec.pb({solve(solve(child,1,0)+1,solve(child,0,0)});
    sum += min(vec[idx].first,vec[idx].second);idx++;
}
int ans = INT_MAX;
for ( auto child : vec )
    ans = min(ans,sum+child.first-min(child.first,child.second);
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For E does greedy approach like this work? Take any leave. If its distance to root in the input tree is <=2 we are done for this leave. Else connect parent of this leave with the root and delete this parrent and all his sons and his father from the tree.

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

Could you please publish a tutorial for the contest !

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

Can I get a tutorial for this contest?

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

Could you please publish the results, the best hackers and the tutorial?

And we know, the best hacker is halyavin as usual.

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

It's sad having problem E with all tests except samples n = 200000. Have WA8 and don't know how to debug)

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

    Why don't you attach your code? I think you were wrong while not interested if addition edge from 1 -> v then we could go from 1 -> v -> parent (v).

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

      You're absolutely right. It's just about "aaarrrgghhh why I can't just copy failed test?"

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

I think the ranklist has something wrong.

Such as the participants VinceJudge0's solution for D was failed during the system test, but the ranklist shows that he/she solved 6 problems. Is this a bug?

vovuh Please check it. :D

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

42038360 He use “for(int i=1;i<=floor(sqrt(a)+0.5);i++)” .He got TLE on my computer because calculate sqrt() many times is much slower than calculate it at first. But codeforces maybe use -O2 -O3 or something and he Accepted. :(

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

Can someone tell me why I'm getting TLE in D? my submission

I read all the comments but can't figure it out.. :(

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

    Honestly i don't know, i tried playing with your code for a bit but i still got TLE. If it helps, my TLE on-contest submission used about 80k memory, and then it went down to about 10k with the Map.count(). Yours is still ~80k for some reason

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

      Thanks. I think my code structure is the problem. Compare to editorial and accepted codes, I insert ten times more nodes.

      That might slow down map operations and maybe larger memory consumption itself can be a problem.

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

Why does this TLE?

Can't find the reason.....

The time complexity should be O(n*log(10n)) (Correct me if I'm wrong) http://mirror.codeforces.com/contest/1029/submission/42107686

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

    std::map is not O(1),and log10(n)=log2(n)*log10(2) so your code is O(nlog^2(n))

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

you should probably change the time limit of Problem D.

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

Hope that the contest page doesn't show "starting in 15 minutes" after 3 minutes