vovuh's blog

By vovuh, history, 4 months ago, translation, In English,

<almost-copy-pasted-part>

Hello! Codeforces Round #617 (Div. 3) will start at Feb/04/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. 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 (or 8) 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 Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

UPD: Editorial is published!

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

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

Good Luck to all participants!

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

I know there is a Points Penalty of 50 points but what is the Time Penalty all about?

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it -18 Vote: I do not like it

    .

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

    Educational CF Round and Div.3 Round have no points penalty. Instead, they have time penalty, which depends on the time when a participant submitted correct submission and the number of wrong submission. In detail, if you solved problem k minutes after the start of the competition, your solved problem number increases by 1, and your penalty increases by 10×(the number of wrong submission on that problem)+k.

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

Looks great! Maybe this is the round when I finally become rated. ;O

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

    Why are you so eager to become green?

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

    you can't because this contest is only rated for trusted participants. And the criteria being trusted is

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

    and you didn't participate any contest till now.

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

      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.

»
4 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I registered when I was cyan (during previous Div.2 contest) and now my Handle in registrants list doesn't have a star(*) next to it . Is it gonna be rated for me and people like me or not ? If yes I hope you fix it cause I don't think it's gonna be fair this way.

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

    you can deregister yourself by going to the registants page and click the red x button :D

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

Come on!!!

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

Can my rating increase or decrease if I am an unofficial participant and I take part in this Div3 ?

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

Div. 3!! So it is vovuh xD

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

Vovuh and Codeforces div3 rounds.

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

Screenshot-from-2020-02-04-16-03-55)

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

what about the score distribution?

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

    Div 3 and Educational Rounds don't have score distribution.

    They have penalties on time

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

      What is score distribution?

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

        All problems score is same. which is

        A-B-C-D-E-F-G

        1-1-1-1-1-1-1

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

I am late some minutes. Is it not possible to register after contest has started?

I am not able to submit :/

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

A difficult one.

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

I forgot to register...

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

Can we hack any solution in this contest ? When does it start ?

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

How to solve E?

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

    Solution for $$$E2$$$:

    Firstly observe that the question asks to use minimum number of colors such that subsequence formed by each color is sorted.

    Consider the longest decreasing subsequence (LDS) of the given array. Observe that no two elements of this sequence can be given the same color, hence number of colors must be greater than or equal to the length of the LDS.

    Now, to find a coloring with number of colors equal to length of LDS, let $$$lds(i)$$$ denote the length of longest decreasing subsequence which ends at $$$i$$$ and includes the $$$i$$$th element. Observe that if $$$a_i > a_j$$$ with $$$i < j$$$, then $$$lds(j) > lds(i)$$$. Importantly, $$$lds(j) \neq lds(i)$$$. Thus, you can just assign the $$$i$$$th element the color $$$lds(i)$$$.

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

      But LDS will take n^2 time right?

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

        No. You can find LDS in $$$O(n \log{k})$$$ where $$$k$$$ is the size of the alphabet using binary search/fenwick tree/segment tree. Even a simple $$$O(nk)$$$ algorithm will work for this problem. Search online for LIS solutions.

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

    You can also just check that a letter can't be assigned to the same color of any letter that has greater value and appears before (it is an inversion). I assigned bitmasks to every letter and every mask will have a bit of the corresponding color active if there is a letter that was already assigned to that color.

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

What's the reason 70267449 'Compilation Error' in C++17 but the same 70270849 worked on C++14 ?

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

    Name collision with data function, which was added in c++17

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

    There's a template function in c++17 names "std::data", which makes your data variable ambiguous

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

I signed up for this div3 before the score reached 1600.Can anybody tell me that Will I be rated in this situation?Thanks~(I didnt find the star '*' beside my name during the competition)

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

STLforces :)

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

Can someone explain to me how does the Test Case #1 for question-d is correct?

TC:
6 2 3 3
7 10 50 12 1 8
Answer: 5

I keep finding 6.

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

    You need 2 tricks for 10 and 50 (10-2-3-2-(?)-2-(?)-2), same mechanism for 50. So you can't have 50 and 10 simultaneously

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

    first , fourth and fifth monster can be killed without secret technique . Last monster can be killed by using technique once and rest of the monsters can be only killed using technique twice .

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

GreedyForces

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

My rating is less than 1600 now, but why I'm not in the official standings of the contest?

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

    May be you have not registered for the contest...

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

    Maybe you have not registered for the contest... Sorry commented again

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

    You were expert, the time you registered for the contest. So you are out of competiton.

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

hello I'm new to CF great problems! I like E2 and F very much

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

Fun fact: if you change statement of E2 so that you have to color all occurences of a fixed letter the same color and let alphabet size vary, you get an NP-complete problem by reducing to graph coloring.

UPD: no, that's actually wrong. Reduction I was thinking about was associating every vertex a single letter and then finding some permutation such that the graph is what you want. But that is wrong: there are $$$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n $$$ permutations but $$$ 2^{C_n^2} $$$ graphs and there is no way to have a surjection.

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

What is wrong with thislink for problem A(div3).

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

my solution to C

can anyone tell why this fails on test case 6? I transformed the string into integer array and used greedy approach to find the smallest sub array with 0 sum.

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

    Using +2 for "UP" and +1 for "RIGHT" means that your program thinks "ULL" is a net-zero sequence of moves. You could do some approach like this, if you did +N for "UP" and +1 for "RIGHT", then there would be no ambiguity because it would be impossible for enough L's to cancel out a U. Or you could just keep track of the sum into two parts, a netVertical and netHorizontal.

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

      but i am never considering odd sized subarrays, I am only checking for even sized subarray starting with 2, hence, I will never check for ULL.

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

        See nathan_drake 's example, even if it is even, you can still fall into that situation

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

    1 6 UULLLL

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

    just replace 2 with 10^6 but your code will still be tle, try hashmap, changed solution of yours it passes test case 6 my solution with hashmap with linear time complexity

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

Any good testcase for hacks ?

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

I didn't solved a single problem, I feel so dumb right now...

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

    everyone didn't solved a single problem at the first time... cheer up man practice hard and get ready for the next contest.

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

    @Ernis In the Codeforces Educational Round #81, I am also not able to solve a single problem. But in this contest, I performed decently. So just compete and don't give up.

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

    Try to upsolve problems after contest has over ..its better for U

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

Are there some extra spaces in Test case 6 of problem C? Using s.length() in C++ was giving runtime error while replacing it with n gave wrong answer.RE WA

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

    may be the run time error because s.length type is unsigned integer so when the length is 0

    1 — length equal to unsigned integer max not -1

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

      input string is not empty as n is greater than 1

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

        i mean this s.length()-4 in your code

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

    Print s.length()-3 and check the value then your questiom will be "how it passed 1st 5 cases?"

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

can we solve E1 by using bubble sort to generate a graph where there is an edge between two letters if we have to swap them, then check if this generated graph is a bipartite graph ?

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

Any hacks for D?

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

How to solve F?

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

    Sort the query asked by passenger in increasing order of minimum distance in path.

    now let for query(a,b,g) if i already assigned all edges with cost less g and assign all edge in path from a to b with g(if any edge is already assigned with less cost then reassign it with g) then minimum cost for a path can't be less than g. Since i am assigning the cost in increasing order then it might be the case that minimum cost in path from a to b can be greater than g(let after reassigning all edge with cost>g). So assign cost to all edges that come in path for every query in increasing order of cost and after processing all query check the minimum cost for every path in query if it doesn't match then there is no valid answer. if every query matches then we have the answer.

    here is my submission

    I solved it in O(n^2) but i am curious to know any soln with less complexity.

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

in d) why ((x-a)+a-1)/a where x is remainder when divided by (a+b), please help?

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

How to solve C?

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

    Store current location During iteration, you can start (0, 0) to increase the values ​​according to L, U, R and D. Store the last locations viewed in a map or group, and when you reach a point you have seen before, store the difference between them and type the smallest distance

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

please give idea to solve C & D

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

    For C

    Store the current location while iterating you can begin at (0, 0) increase the values accordingly for L, U, R and D

    Store the last seen locations in a map or set and when you reach a point you've seen before check if the distance between the current index and index of where you last met the point is minimum and save it as your result.

    For D

    Calculate the number of tricks (the secret technique) you will need to gain points from each monster ignore if 0 (add 1 point to the result since you already earned it) sort the other trick values and pick from the minimum while k is sufficient

    You will need a trick if h mod (a + b) = 0, you need exactly ceil(b / a) tricks for that

    Or if h mod (a + b) > a let's call the remainder rem you need exactly ceil(rem — a / a) tricks for that.

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

Can someone hack this

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

Round has ended recently and now I'm really can't explain why my E2 solution works

Interesting experience :D

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

where is the editorial for this round?? [contest: #617 (Div. 3)]

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

I've found few Guys Rampantly Cheating during Contests. Can Anyone please guide me, how to take this forward and make sure that this is seen by MikeMirzayanov , and there accounts are banned!

Manthan_144

and

rajan_ladani

Here are the Submissions they did in Codeforces Round #617 (Div. 3), and it clearly Shows that they are Big Cheats!

The Submission Of E1/E2 is clearly copied, and several redundant while loops have been added in order to escape from the copy-checker mechanism!

Manthan_144 :: 70282306

rajan_ladani :: 70294414

Apart From this they have also copied A,B,C,D

Guys please dont be cheats, and respect the community!

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

70254356 Why doesn't this solution end up in TLE? If we consider the number of operations it should be slow. I tried the same solution in GNU C++ 17 in custom invocation and this solution ends up in TLE but in MS C++ 17 it passes easily. Is there some kind of optimization in MS Visual C++? What am I missing here?

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

    Interesting, if someone could throw a light it'd be great.

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

.

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

So someone replaced D with C .

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

Any ideas on how to solve C in C#? My 70280505 with Dictionary looks correct in principle but too slow.

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

    So, it was a bad idea to use struct as a key in Dictionary because the hash generation is slow.

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

How to solve E using graphs ??

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

I feel that C was comparatively difficult than D.

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

What is the hack case is F? pajenegod

UPD : It TLEed

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

    I was doing TLE hacks. In the end I was able to hack more than $$$100$$$ submissions with the same hack. My test was just to construct a tree in the form of a line, then do queries from one end to the other with weight $$$10^6$$$. To make the queries a bit heavier I made all the labels random and never asked the same query twice.

    One fun thing to note was that my test case hacked the checker for the problem.

    I've seen my hack take $$$46$$$ ms submissions to $$$1.3$$$ s, so my test was far heavier than the original test cases. Honestly the reason why my hack was so effective was because the original $$$267$$$ test cases were really sub-par. Not only did they not test the obvious max case, there were also obvious patterns in the data. For example if you made node $$$1$$$ be the root, then parent[i] < i in every single one of the original $$$267$$$ test cases. dorijanlendvaj noticed this pattern after I showed him a $$$46$$$ ms submission that I had made TLE. He figured out that the code got stuck in an infinite loop if parent[i] > i, which never happened in the original test cases.

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

      Honestly, I did not expect such weak pretests.

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

When will the ratings get updated? I think i'll get a pretty good boost! xd

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

Don't know about you guys...For me this is the best contest ever...

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

Why are some experts getting rated ?

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

My submission was TLE on System test. https://codeforces.com/contest/1296/submission/70275201

I submitted same code and got AC. https://codeforces.com/contest/1296/submission/70355834

Does this happen often?

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

    It happens often if your solution runs closer to the TL. Runtimes can vary quite a lot (maybe up to 200 ms), but usually 30-60 ms.

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

    Just so you know, you could have just done c[x,y] instead of c[str(x) + "," + str(y)]

»
4 months ago, # |
Rev. 4   Vote: I like it -22 Vote: I do not like it

.

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

in question C for 3rd division cant we use prefix-sums and check for sum of 'L' & 'R' for size 2 and sum of 'L'+'R'+'U'+'D' in the string and print the index where we get it.... what is wrong in this approach!!! on which edge case it might be wrong!! please help

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

Can anyone explain the tutorial of prob E2?

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

Well problem F is clearly overrated :|

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

Hello, could someone help me check my submission for problem F? It got time limit exceeded on test 271. I already check it in my computer with a line graph, and it is slow (took around 7 seconds). I have no clue why it happened. Submission link: https://codeforces.com/contest/1296/submission/71952020. Thank you!