halin.george's blog

Codeforces Round #381
By halin.george, history, 8 years ago, translation, In English

Hi everyone!

Codeforces Round #381 will take place tomorrow on the 23rd of November at 19:35 MSK.

The problems were prepared by Alexander Alexandr_TS Tsaplin, Maxim HellKitsune Finutin and me. I hope you will enjoy it.

I'd like to thank Gleb GlebsHP Evstropov, Nikolay KAN Kalinin and Yevhen MrDindows Zadorozhnii for helping me in preparing problems, Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

There will be five problems and two hours for solving them. The scoring distribution will be announced later.

UPD

Scoring for both divisions: 500-1000-1500-2000-2500

UPD

Congratulations for winners.

Div 1:

  1. jqdai0815

  2. FatalEagle

  3. izban

  4. LHiC

  5. Radewoosh

  6. Egor

Div 2:

  1. liumh8

  2. retired_coder

  3. fuboat

  4. v4lerich

A special congratulations to Petr for being the only contestant to solve the problem D in div. 1.

UPD

The editoral in english will be published tomorrow, but you can read it now in russian

UPD

The editoral was added for the first five problems.

UPD

The editoral was added for the Div.1 D and Div1. E.

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

Comments Comments (158)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it -166 Vote: I do not like it

Dont know why got downvote but hope it will be rated and fast judging

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -59 Vote: I do not like it

Obligatory comment: Is it rated???

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

Finally usual five problems two hour contest in a usual start time :D

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

Is it rated?

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

    Yes

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

    After thousands of "joky" comments about "is it rated?" I think we all need motto "Yes, it is f*cking rated".

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

Your graph is really inspirational halin.george :)

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

Will you put Greedy problem?

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

I think Six or Seven problems in Two and Half hours is more interesting. Because there at least four solvable problems to an Expert.

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

    there is only half an hour between the time for the contest with 5 problems and the time for the contest with 7 problems and this is not enough to solve the extra 2 tasks

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

I hope I can become red after this round. (Maybe a little bit difficult)

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

is it rated...! where is this guy there is one each time?

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

    Did you read like the first 5 comments?

    Also, what is the deal with you guys anyway? You see 3 "is it rated" questions being downvoted to oblivion, do you think the 4th time is the charm or something? What the fuck is wrong with you?

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

      Please don't swear on Codeforces. Someone said their ISP blocks websites with these phrases so they wouldn't be able to access the site if their ISP blocks Codeforces. Please continue making the world a greater place ;)

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

Wish interesting problems and more ratings :)

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

finally no "usual" word in the statement

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

Score Distribution? Its 16 minutes to start

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

    Your wish has been granted

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

I'm freezing now , it's just a little bit hard to code with a blanket on your whole body
maybe some hard problems can make me warmer

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

I think it's going to be a hacking contest. specially problem A div 2.

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

    Yeah, It will be. This is the first time I've seen my live rank bouncing up and down so frequently.
    Also once you lock in and check others programs, you can easily identify a mistake if you made one and then start hacking others who did the same as you.
    Here's an example of it happening to someone in my room:

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

Hackable contest

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

I wonder why so many people don't write bruteforce instead of dealing with lot of cases in div2A. Also, will mo's algo pass in problem D(O(N * sqrt(n) * log(n)))?

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

    we love complicated Solutions

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

    My solution was O (NlogN) in the problem D Div 2, or can say O (N) with lower_bound

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

it's a great feeling when you find your problem in a Codeforces round
link
you own me ECPC participants

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

Finally, I suffer from the problem that std::set has no way to count the number of elements < k ...

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

Hacks for Div2A

7 50 2 100

ans=50

7 50 100 1

ans=3

7 100 1 1

ans =2

Fingers crossed. Finally Blue. Maybe. :)

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

Problem div1 B looks very similar to Problem J in the last ACM-ICPC Egyptian national contest.

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

    Actually it is that problem, I have just ctrl+c ctrl+v the code.

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

      i did the same but the log^2 idea that passed in the ECPC didn't pass now :D karma...

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

        i have log^2 pretests passed .....

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

          o.o

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

            maybe you copied the slower log^2 :3

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

              actually i didn't know that return make_pair() returns in O(n) also copying is in O(N) and SOMEHOW this code got ac in the national problem , great testing O_O

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

                What does this mean? Anything related to make_pair ?

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

                  if u returned a vector with make pair it'll call the copy constructor

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

      i got solutions skipped because i ctrl_c and ctrl+v the code i want that status removed right now... not my fault they decided to ripoff the problem

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

    Also similar is http://usaco.org/index.php?page=viewproblem2&cpid=576

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

      That's an LCA problem, and is completely different from div2D...

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

        What I mean, is that techniques are very similar. Binary jumping and the prefix sums are both used in this problem, the only thing not included is the rewriting of the condition, but even that is a common theme in these tree query problems. This D was pretty much a subset of the usaco problem.

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

          Oh whoops my solution to D was pretty different but I guess you're right ;)

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

Please, someone who passed C but had WA #4 before that, tell me what you have changed :)

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

    Stupidly forgot to use long long instead of int in one of the variables... cost me 50pts.

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

      Shit, my lazy array should be long long! Thank you! :)

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

Harder version of Div.2 D/Div.1 B

dist(v, u) ≤ Au => dist(v, u) ≤ Av

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

    I misunderstand problem and solve the harder version in contest :(

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

      Me too. :|

      By the way how did you solved the harder version? ( Merging Treaps? )

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

        I did it too -______-

        I used segment tree with value compression...

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

        Just realize I read the problem wrong after implementing it. :'(

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

        O(n log n) with BIT.

        Let di be the distance from i to root. Precalculate all value of ci = di + ai and sort these values. Then visit tree with dfs order. When we visit a vertex x, we can know it will contribute answer to which vertices by by binary search on sorted array c.

        Please see my code for the detail: http://codepad.org/Q2NDUqDi

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

        Simply by doing the dfs order, the problem reduces to finding the number of values <= x in a range, which has a nice known solution using BIT in increasing order of values.

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

          How do you find the number of values <=x in a range using BIT? Can you please explain?

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

            Sort the array values and queries values, together, then if an array value comes (v,0,index) update(BIT, index, +1). Else, for (v,1,index) query [l,r] answer = read(BIT, r) — read(BIT, l-1). This is a well known solution to this problem.

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

    when I first saw the problem, I think it is the difficult version, and it takes me 20 minutes to realise

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

Can somebody explain C to me? I assume that mex is always length of the smallest subset + 1, but I have no idea how to make the array. Can someone explain? Also, hacks on A saved me, would've had a terrible result otherwise :D

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

    Div2. Of course

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

    Denote M = mex

    Make array like this : 0 1 2 ... M — 1 0 1 2 ... M — 1 and so on. Any consecutive subarray of this array contains all numbers from 0 to M — 1

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

      Ah, damn now I feel stupid. Thank you!

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

    Let l be the smallest length of the subarrays. Then a[i]=i%l. It's pretty easy to prove

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

I can feel the power of Alyona's mother

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

-

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

I think it would be better if in div2 B : n, m <= 1000*1000

by the way thanks for contest.

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

Div1 B is exactly the same with ECPC 16 J.

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

    B — rewrite the condition and apply well-known tehnique

    C — apply Maximum subarray problem for segments but with another combine function.

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

      How to solve DIV1B? What's the well-known technique (Atleast I am unaware of it).

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

        Yeah these comments are driving me crazy because half the discussion is about Div1b/Div2d but noone explaining how it works :)

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

          For a given node i, let's find what's the closest node to the root that still controls node i. In other words, we need to find the closest node j such that i is in j's subtree and dist(j, i) <= A_i. This sounds like a job for binary search. I implemented the process of finding j using skip-lists. The lowest node that controls i, is i's parent. The farthest node from i that still controls i, is j. So every node that lies on the path between j and i's parent control i, or in other words parent[i], parent[parent[i]], ...., j. This can be calculated using the same technique as in partial sums' updates. If for a node x, parent[i] is in its subtree res[x] += 1. If parent[j] (first node that doesn't control i) is in its subtree as well, then res[x] -= 1.

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

Petr using C++, what has the world come to???

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

    Free CLion evaluation ends in 5 days, will switch back to Java soon :)

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

      Petr, I'm happy you've solved D. It was my idea of the problem.

      Codeforces has hosted Kotlin Unknown Language Round and got few licences for free. I'll be glad to make you a gift: one year 100% discount for any JetBrains product. Each time in a year if I'll see your "Accepted" on C++ I'll be glad to think that there is small part of our contribution there :)

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

        Well, I think they pay enough in Google so that issue is not in having the license :)

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

          We are going to end up with battle between Egor and riadwaw for users with their respective products CHelper and JHelper :)

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

some hints for problem C?

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

    Check this comment .

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

    find minimum length interval len = (r - l + 1) obviously answer can not be more than that. So just print 0, 1, ...len - 2, len - 1, 0, 1...

    you can see that for every interval mex will be equal to len

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

      It was not "obviously".

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

        Maybe you are right, but at least it's something which does not require too many steps in thought process. Either you see it or you don't, it's not like you have to think of A then B and then come up with conclusion as in many harder problems.

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

      Shit !!

      I used binary search on mex! :P Shame on me...

      But got AC... This Shouldn't be allowed ! :)

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

OMG!!! I had two bad performance in two contests, I think i should take a break for a while :(

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

    Or the other way around — train more intensively before the next contest, which will be in this sunday :)

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

      Too much pressure is not good...

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

Maybe codeforces's computers are too fast! Div1. E:22443543 This submission just uses an O(n^3) and passes !

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

    Lesson learnt: brute force even the obvious solution looks a bit too slow :(

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

http://mirror.codeforces.com/gym/101147/problem/J

is similar to today's div. 2 D. I got AC in Gym, but the same code didn't pass today's system test. :'(

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

    shame on me
    I've prepared it's tests very well
    can your please give me your code ?

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

      hello i did this problem J one time and i just did the same process as that time i solved J since i already solved the problem, i used my own code as a guidline (since is gym obviously i am basically guiding myself) and send it , now i got skipped obviously because you guys are flagging me as cheating, remove it. If you are going to ripoff a problem without any twist don't expect us to do something different if we already solved it before. Thanks.

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

When system testing will start ?

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

it's nearly not fair that the people who solved the ECPC problem j only paste their code in problem D div2 and got accepted

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

By-by blue.... :(

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

so hacking :)

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

Omg, D is so tedious. If I'm not mistaken it can be simply solved by linear greedy, but that requires big amount of ifs and a lot of stupid boring code.

EDIT: Okay, I was wrong. So easy to get head messed up at this one.

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

    Hmm, I had similar thoughts initially, then I realized I was wrong. The solution I came up with uses maximum matching.

    EDIT: After getting it accepted, I can safely say that even though it isn't greedy, the solution still requires a shit-ton of special cases :D Or maybe I just lost my touch...

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

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

How to solve problem E (Div2) ?

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

    Probably seg tree + lazy propagation

    For each interval, keep the left hill, the right hill and the answer. When you merge 2 intervals, the answer will be:

    max(new left hill elements, new right hill elements, hill in the middle (you merge the right hill of the left and the left hill of the right), max answer of the smaller intervals)

    merging the hills needs a bit of time to code but it's not hard to think about the answer. You will need to save the left number, the right number, whether it has reached a peak, whether it is decreasing/increasing, etc.

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

can Anyone describe the solution of problem D in Division 2? i got nothing other than O(n^2) solutions.

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

    I can tell you how I solved it.

    Build sparse table on a tree. You have every 2^kth parent and for every 2^k parent sum of all edges on path.

    Now, for every vertex we want to find the farthest parent such that our node is controlled by this parent. Notice that sum along path can only increase, so it's binary searchable. In this part we use 2^k parent, which we have from sparse table. Let's call that farthest node V.

    All nodes on path [V -> our node] controlls our node. Then we use little trick: add 1 to parent of our node and -1 to parent of V. Now with standard DFS we can finally make answer.

    Of course, I've omitted implementation details.

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

      I was working on this problem but got stuck on how to add +1 to those nodes that control the current node, how does the "little trick" work it's not clear at all? Thank you.

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

        We have an array where we want to sum v on intervals l<=i<=r.

        Let's first process the intervals and then get the array. The array "a" first starts with all 0's and there will be an auxiliar array "aux". When we want to update the range, we make aux[l]+=v and aux[r+1]-=v.

        But why? If we consider the cumulative sum of all elements of aux until i, we will get exactly the value that we added on i. So to get the answer we do aux[i]+=aux[i-1] and a[i]+=aux[i]. Why does this work? Because on the range l<=i<=r, you will have v on the sum and from r+1 onwards, you will have excluded that v, as needed.

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

      Can you help in figuring out the mistake ? (the test case is big) . My approach is exactly same as yours. http://mirror.codeforces.com/contest/740/submission/22459911

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

I had a greedy solution for Div1 C but it was splitting into a large number of cases. How to improve the solution?

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

    For problem c:find the minimum gap among all the l and r ranges...val=min(val,r-l+1) run this for all m subarrays and now just start off with a variable x=0 and print it modulo val and then increment x after each iteration

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

super fast system testing

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

Hack-round

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

Hello, why in the world my submissions are "skipped"? , it is not my fault that you decided to ripoff a problem from the Egyptian ACM contest, my solution is exactly that , you can't argue i cheated in the contest. If i solved the problem the same way i did in that contest is not cheating, so please remove the "skipped" flag on my submissions... thanks.

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

My name disappeared from the final standings and I found my submissions transformed to skipped on my profile. MikeMirzayanov why did this happened?

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

    I see cheatCount=9 in database in your profile. So I simply even do not want to answer.

    Same solutions: 680A: Joe_Pacha/18303346, just_fuck_you/18303475
Same solutions: 682B: Joe_Pacha/18550753, _underr/18552489
Same solutions: 697A: Joe_Pacha/19113420, _underr/19114661
Same solutions: 699B: Joe_Pacha/19238676, zackblick1234/19239332
Same solutions: 699A: Joe_Pacha/19235514, zackblick1234/19235986
Same solutions: 706C: Joe_Pacha/19799607, BaiBatyr/19802891
Same solutions: 716B: Joe_Pacha/20688209, pashka921/20688382
Same solutions: 724A: Joe_Pacha/21281037, humblecool/21281540
Same solutions: 740A: pashka921/22428017, Joe_Pacha/22428028
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +26 Vote: I do not like it

      Hello can you check mine? you can even check on the GYM the solution my team and i did for problem J sadly the setters decided to do the same exact problem, so i just used that solution which is ours. But got flagged as "skipped" , sir i never ever cheat on this contests, i beg you to check i don't want to miss my chance to get back to blue and be treated as a shady contestant which i am not.

      Contest is ACM Egyptian Collegiate Programming Contest 2016

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

      I opened the profile of "_underr" and couldn't find a submission with ID "18552489". Also user "just_fuck_you" logged in 4 months ago, so how does this relate to me and to the contest? Please give me more details about why this happened.

      MikeMirzayanov I appreciate if you could give credit back to my solutions, as seriously the solutions you mentioned don't belong to me and I don't know anything about them. I've been competing actively for many contests and I never cheated.

      You can re-check my submissions, and for example, I submitted the 'A' problem very early from first time (maybe after 3 or 4 minutes from the contest) so it's not logical that I was cheating.

      Thank you.

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

For Div1 A, a[i] = i % ans did not strike me. So I thought of removing the intervals which subsume at least one interval. Now, sort the intervals according to the left end. Now, you can fill in O(nlogn) by only checking for those elements which do not overlap with the just previous interval. Did somebody go down this line?

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

    http://mirror.codeforces.com/contest/740/submission/22453551

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

      Can you please explain little more in detail. I was thinking in similar lines. Thanks :)

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

        Triveni sir, if you remove all the intervals that subsume another interval, then it would not matter, because the smaller interval will have all the numbers from 0 to ans — 1. So, step1, remove such intervals.

        Step2, sort intervals by left end;

        Let the intervals be a1, a2.....

        Then you have to understand that ai.l <  = aj.l and ai.r <  = aj.r for all i < j. So, when filling ai you check for overlaps with ai - 1 and fill the part only in ai with elements only in ai - 1. In this way, you fill each position at most once, so O(n). We need O(logn) to check if an element is already in the interval or not, so O(nlogn).

        TLDR: we fill part of each interval that is not contained in the previous interval.

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

Can someone provide a hint on how to solve Div2 D?

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

    dist(v, u) <= a[u] <=> dist(u) — dist(v) <= a[u] <=> dist(u) — a[u] <= dist(v)

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

TooSimpIe beats Petr!

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please update the ratings with the same speed as the system testing so i get to know how much will my rating decrease :(

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

When will be editorial?

Nice contest :D

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

Ehhh, out of seven ACed solutions to E, four are obvious O(n^3). Will this ever stop? Give me my deserved TOP5 :<.

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

Problem C was a mess to implement. Problem D was worse, as far as I saw. Problem E seemed the cutest one, but could be squeezed with N3 complexity. I'm not blaming anyone, I just hope the next rounds will be more balanced.

Here is proof: http://mirror.codeforces.com/contest/739/submission/22452983

By the way, what is the solution for problem E?

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

Can anyone tell me why this code for Div1 A gets WA but this code gets AC?

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

I sent a PM to MikeMirzayanov i found out new information but i don't want to spam him, so i will copy and paste the PM here:

"Hello sir, since nobody is addressing my petition to check on my submmited codes nor answering why i got flagged as a cheater, i will then send this message and hope you can answer me. Sorry for the inconvenients but i am really mad about this situation.

Problem D div 2 is the same exact problem as problem J in the ACM Egyptian Collegiate Programming Contest 2016, me and my team solved this problem around 2 weeks ago or a little more.

Since it is the same exact problem without any twists i just used my already AC solution, it is not my fault that the problemsetters did not want to place any kind of twist to the problem nor i care, if the problem was that and i did not copy it from anybody in the contest i am 100% sure that can't be counted as cheating, so please remove the skipped flag since this makes me look like a shady contestant, but i have never cheated in any CF nor any contest in my life, actually i am fighthing about cheating in ACMICPC since a long time. So please check, i guarantee you, you will find out everything is ok."

Now to the new.

A friend of mine user poiuyt2022 , found out that there is a user that ripped off my solution for problem D from the contest, which it is indeed cheating, but had nothing to do with me, link to the submissions:

http://mirror.codeforces.com/submissions/_underr

Can you please put me back into the contest?.

EDIT again: The issue was addressed, thank you so much for reading and helping, hope everything goes fine with this.

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

And when will this Tomorrow for editorials happen?

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

Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).

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

Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).

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

Why does everybody use binary lifting? I just used the merging sets technique + priority queue. It's quite fast tbh.

→ Reply