Um_nik's blog

Codeforces Round #485 (div.1+div.2)
By Um_nik, history, 20 months ago, In English,

Hello!

I'm glad to invite you all to Round 485 which will take place on Tuesday, May 29 at 18:35 UTC+3.

There will be 6 problems in each division, 3 of them are shared between divisions. 2 of div.2 problems created by KAN, 7 others created by me. The contest duration is 2 hours. My problems were originally used in HSE Championship.

I would like to thank Merkurev and GlebsHP with whom I discussed the problems, I_love_Tanya_Romanova for testing, KAN for round coordination and Codeforces and Polygon team for these beautiful platforms. I would also like to thank HSE for organizing the event. Oh, and kb. for writing great legend for one of the problems (he will be surprised).

For those who for some reason like to know score distribution in advance:
div.2: 500 — 1000 — 1250 — 1750 — 2250 — 3000
div.1: 500 — 1000 — 1750 — 2500 — 2750 — 3000
But I didn't properly discuss it with KAN so this is subject to change :)
UPD: Discussed with KAN, scores for C and D in div.2 increased by 250.

Good fun, have problems, read all the luck. As usual.

Oh, and if there will be no bad things, round will be rated. I hope.

I'm very sorry for issues with queue. I understand that it could ruin the contest for many of you. But please be understanding. Bad things happen. It could be some network problems or some electricity problems. MikeMirzayanov, KAN and other people behind Codeforces trying their best to provide good service. But sometimes it's very hard for some reasons. I hope that you enjoyed the problems despite all the bad things.

We decided that round will be rated.

Editorial will be posted tomorrow.

div.1 winners:
1. tourist
2. OO0OOO00O0OOO0O00OOO0OO
3. Radewoosh
4. mcfx
5. LHiC

div.2 winners:
1. sminem
2. Fortza_Gabi_Tulba
3. cheburazshka
4. I_Love_KFC
5. CantGetAnyWaWhyImSoSmart

Editorial is up.

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

Comments Comments (590)
»
20 months ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

Good fun, have problems, read all the luck. As usual. Love how the words were jumbled and at last as usual :P.

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it -28 Vote: I do not like it

Meow ! :)

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

And also thanks to MikeMirzayanov for systems Codeforces and Polygon:)

→ Reply
»
20 months ago, # |
← Rev. 6   Vote: I like it -149 Vote: I do not like it

.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

KAN is my favorite

→ Reply
»
20 months ago, # |
  Vote: I like it +22 Vote: I do not like it

If KAN didn't invent easy tasks, we would have div 1 only round :D

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +327 Vote: I do not like it

    No, you would have bad div.2 round :)

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B and C in div2 have the same score ,Will they have the same difficulty ?

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +58 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      too many spoilers

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it -169 Vote: I do not like it
        Spoiler
        → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it -35 Vote: I do not like it

    Good Question. And nice observation.

    → Reply
»
20 months ago, # |
  Vote: I like it -28 Vote: I do not like it

so excited <3

→ Reply
»
20 months ago, # |
  Vote: I like it -95 Vote: I do not like it

could you please make the start time a 1 hour earlier (at 17:35 Moscow time) . we in egypt have fast breaking at (19:35 Moscow time) as we fast in this month from dawn to sunshine every day so we won't be able to compete :-). like if you agree

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +69 Vote: I do not like it

    Every hour there is muslims have fast breaking , not only in Egypt, i think that is the main reason for ones who downvoted your comment

    → Reply
»
20 months ago, # |
  Vote: I like it -17 Vote: I do not like it

GOOOOD LUCKK 4 EVERYONE :з

→ Reply
»
20 months ago, # |
  Vote: I like it +48 Vote: I do not like it

on 11-th line it is incorrect to say i didn't discussed because did is always followed by a verb in PTS(present tense simple)

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

    *in infinitive

    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Nice catch. Thanks. Fixed.

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

      discuss not discusse :)

      → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 2   Vote: I like it +50 Vote: I do not like it

      Ok then, you should say "If there are no bad things, round will be rated", cause it's first conditional.

      → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 2   Vote: I like it -12 Vote: I do not like it

      2 of div.2 problems created by KAN, 7 others created by me
      should be
      2 of div.2 problems were created by KAN, 7 others were created by me

      → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    successful hacking attempt +100

    → Reply
»
20 months ago, # |
  Vote: I like it -57 Vote: I do not like it

after 3 years of coding

i still fight in #Div_2 -_-

→ Reply
»
20 months ago, # |
  Vote: I like it -61 Vote: I do not like it

My comments will have more downvotes than upvotes on this post. Do Down Vote.

→ Reply
»
20 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Two hours and we have problems worth 1750, 2500, 2750 and 3000. Is that best choice of duration?

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +139 Vote: I do not like it

    I just think that standard distribution is bad because you usually solve C on 0:30 and E on 1:55 -> they give the same points. Also we added easy problem so we had to increase scores of other problems. So, yes, I think that the difficulty is comparable to "average round" whatever that means. But I may be wrong :)

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      That's the answer I wanted to hear (y)

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

        I think you read it :)

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

          but he wanted to hear

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

            you know you are on CF, when the red gets +40 for stealing your joke, while you get -20. you guys really don't know how to apply your logical reasoning outside solving useless problems

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

          But maybe I wanted the very Um_nik to whisper it gently to my ear, but somehow stopped desiring it the moment whe he replied here to me? Hm? Have you ever thought about it?

          → Reply
»
20 months ago, # |
  Vote: I like it -72 Vote: I do not like it

kan gives t-shirt winner in the contests.

→ Reply
»
20 months ago, # |
  Vote: I like it -33 Vote: I do not like it

So rating 1953 will be rated in division 2?

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

    No, purple coders will be rated in Div1 as before. Nothing has changed for Div1 rounds.

    Just that purple coders can now officially participate in Div2 — only rounds (today's round is Div1 + Div2 so they are rated in Div-1).

    → Reply
»
20 months ago, # |
  Vote: I like it -86 Vote: I do not like it

I hope there are no problems from Graph Theory.

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

    Really??? I hope all problems will be related to Graphs. They are great!

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

      Indeed , I love Graphs !

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

        Very, very true ! I think all the problems will be great, not only the graph ones ! Anyway, there is no perfect contest if no graph problems or problems that are solved using data structures based on graphs are included !

        → Reply
»
20 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Oh, and kb. for writing great legend for one of the problems

Hope that's the only problem with legend :(

→ Reply
»
20 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Finally Codeforces round. Really the point distribution is great. Goodluck to everyone.

→ Reply
»
20 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Oh, and if there will be no bad things, the round will be rated. I hope. :D :D :D

Nice statement.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I see problems of past HSE editions?

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

    HSE is the university I attend. I made a championship for its students. As far as I know that was the first one.

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Happy to see you in the list of top contributors.

      → Reply
»
20 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I hope tourist will regain His position after this contest

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i cant registration ...

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hacks window not opening. -_-

→ Reply
»
20 months ago, # |
  Vote: I like it +77 Vote: I do not like it

terrible queue :(

→ Reply
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

queue:(

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

Extend the contest.

→ Reply
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

So Long Queue I guess Codeforces need to work on that, so that it occurs less often... Please See to that Admin.

→ Reply
»
20 months ago, # |
  Vote: I like it -18 Vote: I do not like it

queue is gone

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

After waiting 10 minutes for my solution to be judged I found out, I printed "um_nik" instead of "Um_nik".

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Submissions in queue!

→ Reply
»
20 months ago, # |
  Vote: I like it +65 Vote: I do not like it

Oh, and if there will be no bad things, round will be rated. I hope.

Yeah, you jinxed it right then...

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

if there will be no bad things, round will be rated. I hope.

→ Reply
»
20 months ago, # |
  Vote: I like it +31 Vote: I do not like it

After waiting for 20 minutes my solution starts being judged, passes 9 pretests, and then...Voila!!! It's "in queue" again!!! WTF is that???

→ Reply
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

So, we have to wait more than 20 minutes for verdict, but time is extended only 10 minute. Is it fair?

→ Reply
»
20 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Codeforces is crashed again and again and again. In queue ........ (20+ minutes later) Compile Error (because of different version of C++)

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

Another semi-rated round? lol

→ Reply
»
20 months ago, # |
  Vote: I like it +56 Vote: I do not like it

is it rated?

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    It should not be rated as many submissions(more than 40 pages) remained in queue even at the end of the contest.

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

    after a long time i see a comment "is it rated?" and that have upvotes (Wow)! :D

    → Reply
»
20 months ago, # |
  Vote: I like it +64 Vote: I do not like it

Nothing personal, but round must be unrated

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

    Submissions after 1:30 was in queue even after a long time after contest’s end

    → Reply
»
20 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Longest queue ever -_-

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

    I beleive u r new to cf

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

    I beleive u r new to cf

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      I believe you have poor internet connection.

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

        No, but my laptop is lagging too much today.

        → Reply
»
20 months ago, # |
  Vote: I like it +55 Vote: I do not like it

The most stupid thing ever:

Ouputted "Alex" instead of "Um_nik".

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

How to solve E?

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

    Basically the question is about checking whether a permutation is odd or even. If there are c disjoint cycles in a permutation, then the permutation is even if n-c is even, and odd if n-c is odd.

    (Source)

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

      My solution was on based on the fact that if that if there are n swaps to change an array then we can't do the same with x swaps if parity_x != parity_n. So I counted the number of swaps in bubble sort same as number of inversions in an array and checked its parity with n. If same, ans if Petr else Um_nik

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

The round was really good until Problem E appeared, it is bad problem and made the queue completely full

→ Reply
»
20 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I thought I (most probably) solved four problems (Div 2 A,B,C,D) and would be blue within this month but this is how my hope is dashed :'(

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

seems unrated to me :(

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

CF don't feels so good

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

how to solve Div2-D?

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

    A multisource BFS will do the job.

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

      can you please explain it a little more?

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

        Just push every starting vertex into queue, and do normal bfs.

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

        In a normal bfs, you put initially in the queue just one nod. In this problem you must put all nodes that have the same color, and run the bfs for each color.

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

          I am unable figure out the intuition behind it. If u don't mind can you please elaborate? thanks !

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

            We can get the distance from every point to it's nearest source of each color. After that, sort it for every point and add the first s elements together.

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

            You need to compute a matrix like this: dmin[i][j] -> minimum distance from node i to the closest node with color j.

            If this matrix is computed, we can find the anser by sorting each vector dmin[i] and taking the first s values.

            This matrix can be computed using the bfs described above ;)

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

            I based my solution on the fact that k is small (<=100), so an O(n*k) or similar solution is feasible. Basically, we can just let an array least[n][k] be the minimum distance to node n for good of type k. We can fill these array by using k BFS, one for each color. Then for each node i, we can just take all the distances least[i][k] for 1..k and then select the s smallest.

            → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
        ← Rev. 4   Vote: I like it +7 Vote: I do not like it

        Note that k is at most 100. Therefore, we can try the following:

        Denote dist[i][j] as the minimum cost of town i to get a good j from any town.

        For each type of good i, push all x such that ax = i into a queue, and set dist[x][i] = 0. Then, we do normal BFS to update the dist array. This has O((n + m)k) time complexity.

        Then we find the sum of s smallest elements in dist[i] for each i from 1 to n, which can be done by sorting.

        → Reply
»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

It's now the end of the contest but my solution from 1:38 is still in queue now. I did Mo's algorithm and how can I be able to now if my block size is not optimized? And how can I even debug my solution if I get a WA. I spent my whole contest doing this...

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

    UPD : I got RTE with the very first sample test which ran fine on my computer now. :/

    UPD2 : I should write idx[NP + 1] instead of idx[NP]. Really...

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

Should a k*(n+m) solution pass Div 2 D?

If so, could someone tell me what's wrong with mine?

Solution here (in Java): http://codeforces.com/contest/987/submission/38744336

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

    I think 'Collections.sort' is too slow to pass tests with big constraints.

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

      Dang, I was hoping klog(k) in the sort wouldn't matter that much. How could I get the s smallest values in the list without sorting?

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

    You are sorting the costs. -> therefore you have an additional log factor.

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

      How do we get the k smallest without sorting the costs?

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

        The selection algorithm does it in linear time.

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

          Thanks! Even partial_sort is good!

          → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was it slow or my internet connection became slow at the last few minutes??? :o

BTW. How to solve problem C?

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

    I used dp there.State of my dp were dp[n][2],dp[i][0] tells me what is the minimum cost in which I can select two displays(k and i) such that s[k]<s[i] and k<i. Now my dp[i][1] tells me the minimum cost in which i can select three displays such that the condition is satisfied therefore dp[i][1]=min(dp[k][0]+cost[i]) for all k<i such that s[k]<s[i]. Hope that it helped a bit :)

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

    CF was slow for me also! C can be done by Dynamic Programming.

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

    what I did is for every element, have 2 priority queues and add the cost[i] to pq depending upon the font size. Now the size of both pq has to be greater than 1 for answer to be present. check for the min. As the value of n was 3K, I think this should pass.

    → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    For every display i (i from 2 to n), find the display x[i] (x[i] from i + 1 to n) that s[x[i]] > s[i] and has the smallest price (you can do it with 2 'for' iteration. Then you run 2 'for' iteration (i = 1 to n - 2) (j = i + 1 to n - 1), update res with min(res, c[i] + c[j] + c[x[j]]). res is the result.

    → Reply
»
20 months ago, # |
  Vote: I like it +109 Vote: I do not like it

Sorry, guys :(

I completely has no idea what happened. One network service unexpectedly started to be slow (first time ever!). Probably, because of network/system issues. I worked hard since noticed an issue, but without any progress.

This fail is completely surprising for me (

Sorry, Um_nik. I hoped as much as you to host a great round. Very upset about the situation.

I continue to investigate the situation.

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

"Oh, and if there will be no bad things, round will be rated. I hope."

are system down and long queue considered as bad things?

→ Reply
»
20 months ago, # |
  Vote: I like it +48 Vote: I do not like it

Woah! Hey, Nobody mentioned that ranklist will be frozen during the last hour. Was away from cf for sometime, when did they introduce that?

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

My question is still in queue!??

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

Lol my hack is still in queue. Just a suggestion, for div2C a bonus problem can be included where n<=10^5. Just like Round 350. How to solve it in O(nlgn)?

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

    I don't know about O(n) but u can do O(nlogn) using Segtree

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

      Sorry edited my comment. O(n) might be impossible. How to do it in nlgn using segment tree?

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

        U got the n^2 dp ri8? dp[i][j <= 3] = min cost with j elements in increasing order.

        So dp[i][j] = c[i]+min(dp[k][j-1]) where a[i] > a[k],i > k

        Make a segment tree for each j, keep updating seg[leaf a[i] or whatever] by c[i]. Now take min 1..a[i]-1 as query

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

          Can the dp be formulated as dp[i][j] = minimum cost obtained upto position i with maximum size being at index j?
          I tried doing this way but got WA on pretest 7. Am I doing some mistake?

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

        You can use Fenwick tree with minimums

        → Reply
»
20 months ago, # |
  Vote: I like it +49 Vote: I do not like it

54 pages of queue right now. Make it Unrated please.

→ Reply
»
20 months ago, # |
  Vote: I like it +18 Vote: I do not like it

For D, I understand the solution is basically "find the smallest power of 3 >= N, N/2, N/4". But how can I find that power for constraints that are this insanely large? Even if I know the exponent and want to check if N isn't just a little bit larger/smaller than that power of 3, it seems impossible with these constraints...

Also, I can't post this comment, CF is broken again.

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

    Fast exponential + FFT for multiplication seem reasonable.

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      So that's plus the not-very-great constant factor of FFT? Note that I wrote "with these constraints".

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

        Well okay, fair enough. At least there are accepted solutions like that. Also my solution works in >10 sec. and I hope that's not the intended solution.

        → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    You should estimate logarithm by something like length * log(10) / log(3) and check constant number of integer values close to it (by computing this power for smallest of numbers we want to check, let it be (length — 1) * log(10) / log(3) — 1) and then try multiplying it by 2, 3, 4 in desired manner. You should group digits in some blocks to make it pass in TL with FFT exponentation (what I haven't done).

    Complexity of this is something like multiplying two polynomials on degree 200000 once. Note that in binary exponentation, in terms of complexity I can ignore all multiplications except last one because length grows two times with every step.

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

      Yes, I know I should estimate log, so I can check only ceil(log) and possibly ceil(log)-1 if the fractional part of ceil(log) is close to 0. Note that I wrote "want to check if N isn't just a little bit larger/smaller than that power of 3".

      If FFT exponentiation is actually the official solution, then this problemset would have massively benefited from having D removed from it. In that case, there wouldn't be any problems with stupid constraints, any boring problems (AFAIK), any problems that are only hard because of bigints, any FFT (AFAIK), the contest difficulty would be more appropriate for 2 hours...

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

I tried submitting in the last 20 minutes . but it only showed queued . Make the contest unrated. Its not fair .

→ Reply
»
20 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I cannot understand the statement in Div1D.. :(

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    ID is not a number, it — is an array of [a1, a2, .. am]. good luck.

    For example: n = 36, m = 3 b[] = { 3, 3, 4}

    so number of different arrays are:

    { 1 , 1, 1 }

    { 1, 1 , 2 }

    { 1, 1, 3 }

    { 1, 1, 4 }

    {1, 2, 1}

    ..........

    {3, 3, 4 }

    Total number of such arrays equal to 36.

    → Reply
»
20 months ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve Div2-F or div1-C?

→ Reply
»
20 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Still queuing the contest should be unrated.

→ Reply
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I feel stupid... for not solving B. Don't think I even have a valid clue -___-

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

D is easy to reduce to calculate ceil(log3(101.5e6)). Is it well-known?

→ Reply
»
20 months ago, # |
  Vote: I like it +66 Vote: I do not like it

Round is still rated? That's unfair. 30+ minutes queue at the end.

Atleast make it "semi-rated".

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

    yep, yep, you are right it must be FunRated

    → Reply
»
20 months ago, # |
  Vote: I like it +9 Vote: I do not like it

And people started to think it "unrated". Then came the announcement! ;)

→ Reply
»
20 months ago, # |
  Vote: I like it +28 Vote: I do not like it

No, it's not like D was everywhere million times, no. However this time with bonus in form of bigints. Yesterday I was making fun of Radewoosh reminding him how he got TLE on bigints because he used them in base 10 last time when Um_nik was a problemsetter. Today I did the same in D...

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +167 Vote: I do not like it

    Me trying to understand this comment

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Some nutella things

      → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      OK, slowly. Um_nik set this problem in the past: http://codeforces.com/contest/756/problem/E and it required bigints. Radewoosh more or less did this problem, but calculated bigints in decimal base instead of base 1e9 what led to significantly slower time of execution and he got TLE. He whined about this in comments and because of that he was kinda ridiculed by Um_nik for using base10. I reminded this situation yesterday to Radewoosh and laughed about it, but today I did the very same mistake.

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

    Maybe I just hate you guys :)

    I hope that it didn't ruin the contest for you (maybe some other things did haha).

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

      This is not a very glorious problem, but I think I am more angry at myself than at you. I think F is a very good problem, too bad I didn't have time to fully appreciate it. And B and C were cool as well.

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

        Thanks :)

        I agree that D is not very fresh, but bigints also require some small ideas (but yeah, more implementation).

        → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    So you wrote this comment not to let Radewoosh write it?

    → Reply
»
20 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Is it correct for E?

print('Petr')
→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 5   Vote: I like it +8 Vote: I do not like it

    n = 2 2 1 ans should be "Um_nik"

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

    Key to solve this problem:

    Parity of a permutation

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

      Can parity of a permutation be computed using this method: Count minimum number of swaps required to make the array sorted and if it is odd we can say that the permutation has odd parity else even parity. If not then can anyone provide some test case to counter this?

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

      xuanquang1999, dheeraj_1997 Can you please explain me how did you reduce the problem to finding Parity of Permuation?

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

        To be honest, this is just experience. I learned about parity of permutation in a TopCoder problem. When I meet this problem, I noticed that the parity of the number of swap in Petr and Um_nik are always different, and get reminded of this.

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

          I didn't get this. Can u please explain me how parity for Petr and Um_nik are different, with an example?

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

            Assume that n = 2k + r (k is integer, r is 0 or 1).

            Then the parity for Um_nik minus parity for Petr is:

            (7n + 1) - 3n

             = 4n + 1

             = 4(2k + r) + 1

             = 8k + 4r + 1

            which is always an odd number.

            → Reply
»
20 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Very end of the contest?:| Really?

→ Reply
»
20 months ago, # |
  Vote: I like it +52 Vote: I do not like it

If the test is generated via Alex's method print "Um_nik"

Cool trick bro!

TIM_20180519215120 TIM_20180504125939 TIM_20180503081312 TIM_20180528221431

→ Reply
»
20 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Is it even possible to solve Div2D in Java? Very few Java solves on it, and I saw people submitting in Java and then switching to C++ with the same code get accepted.

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

    I had to change my graph representation from List<Integer>[] to int[][] and change sorting algorithm to Egor's ArrayUtils.sort() and it passed systests.

    Before doing that I had TL6 like many others. Here is my accepted code: 38738273.

    → Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

I tried to solve B in the last 30 minutes after trying to solve C all contest. Not getting any feedback was not nice :/

Well at least I can participate in Div2 contests now.

EDIT: the reason my original submit didn't pass was that somehow I thought 3 * n was always even, and compared number of inversions % 2 against 0 instead of n % 2. Well this one is on me.

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

Despite the issues during the round, i enjoyed the problemset a lot. Thank you guys!

→ Reply
»
20 months ago, # |
  Vote: I like it -54 Vote: I do not like it

plzz don't make it unrated i got +154 this time ploxx

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

It was a good contest. The problem sets were cool. (Though I was unlucky and completely ruined my contest). Anyway I submitted C n D at the very end n I wish I could know if anything was wrong coz surely i think i could have corrected it. (even with weak pretests as they dont have any corner cases in my opinion)

I think it will be unfair to keep the contest rated (i dont know when the system started to become slow but i submitted my C on 1 hour 40 min n still no verdict).

→ Reply
»
20 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Are 40 minutes considered as the VERY end of the contest in which the actual rank of the contestant is decided and matters a lot in his rating

→ Reply
»
20 months ago, # |
  Vote: I like it +142 Vote: I do not like it

General announcement ***** We discussed the issue with the queue and decided that the round will still be rated because the queue only appeared in the very end of the contest. Of course all submissions in queue will be judged. We apologize for the issue and thank you for participation in the round, I hope you liked the problems.

Yeah, right, around 1 hour 35 minutes mark is VERY CLOSE to the ending of a 2-hour contest. Nice!!! Really nice!!!

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Div 2 C be done better than O(n^2) ?

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

    You can optimize it with Segment Tree or Fenwick Tree, but O(N^2) is enough.

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

    O(N log n) using the segment tree and compression

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

    this may help...

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

    Precompute (Si < Sj), adjust Si (smaller in range [1..3000] — I dont know how its called in English). in Si, mark the node[s[i]] in segmen tree as Ci, then Query from [Si — 3000]. Every not-filled nodes, mark them as INF.

    → Reply
»
20 months ago, # |
  Vote: I like it +38 Vote: I do not like it

How can this round be rated? Submissions were not evaluated for more than 30 mins towards the end of the contest. This is really sad.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem f, can we do it by creating binary trie? we insert each element in trie (by representing each element in 23-bit format). then for each element, we traverse trie bit by bit. if current bit of current element is set to zero we go either zero edge or one edge, else if it is 1 we can only go towards only zero edge(this way we traverse for all 23 bits of element). if we reach end of trie (while representing elements at last bit, i stored indexs) we can make a pair . then after all elements are done we can do a dfs to check connected components. will it work ?

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, the linear algebra class I attend this semester helped me to solve div2E/div1B easily:) Was literally looking into my linear algebra book during the contest

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

    How to solve E?

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

      It's about sign of permutation. Use the fact that

      1. the evenness of number of swap for generating a specific permutation from identity permutation is consistent(i.e.if a permutation is 3 swap away from identity permutation, it can never be generated by even number of swap from identity permutation)

      2. a cycle of length k in permutation is equivalent to k-1 swap (by "cycle", I mean, consider ith number in permutation as "the next node for ith node" like in a graph question)

      → Reply
»
20 months ago, # |
  Vote: I like it +21 Vote: I do not like it

How to solve C? My brain kinda stopped working after spending nearly entire contest thinking about it.

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

    We can simply rephrase the property "X&Y==0" into "X is submaask of inverted Y". Then simply for each element go through all of it's submasks :)

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

      I think that number of edges is still too big.

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

        Yes, but in the end you go through only O(2^N) states, if you remember the ones you already visited.

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

        We dont need to use DFS or BFS on graph to count answer. Just using DSU and DFS on the mask is fine.

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

          If the number of edges is big, DSU or DFS is still too much.

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

            I agree.

            But we are using DFS on the mask, not on the graph. So edges number is about 22 * (2 ^ 22), and vertex number is 2 ^ 22.

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

        I think we can improve it by dividing the vertices in a similar manner to SOS DP

        → Reply
»
20 months ago, # |
  Vote: I like it +43 Vote: I do not like it

I even cannot submit ( no respond when clicking on the submit button, refreshed a number of times ) during the last minute......

→ Reply
»
20 months ago, # |
  Vote: I like it -449 Vote: I do not like it

Hi, we apologize for the queue. We discussed the situation with Um_nik and decided to make the round rated because

  1. The round was going to end — it's very unlikely for a participant to solve two more problems since then, so he can test his only problem throughly.
  2. There are plenty of rounds and the rating always goes up and down, so you shouldn't worry about a slight change that may be caused by the issue.

Thanks Um_nik for great problems and thank you all for participation!

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +95 Vote: I do not like it

    I think it's unfair.There're a lot of solutions for Div.1 E which has a complexity that can tightly fit into the time limit (such as O(n^1.5logn) and O(nlog^2n),even O(nlog^3n)).We don't know whether it fits into TL and can't decide whether to make the program run faster or change to another problem.It will affect participants a lot.

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      Same for D. I do not know how much this queue affected Div2 Participants, but it was significant for Div1 participants.

      I have 4 submissions in Div1D because I did not know whether my solution was efficient enough and I did not get the verdict for a single one.

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

      I even lost my E for being RTE on sample test. What should we do with these undefined behavior cases of compiler without being able to resubmit it?

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

      There are also cases when someone got compilation error and learnt about it long after contest's end xD

      → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +38 Vote: I do not like it

    I think Rated is an acceptable result.

    But I don't like your first reason. It has been stuck for over half an hour. I waited for a long time and receive a MLE, eventually I had no time to fix it. Meanwhile, for those who stuck in the first or two problems, they are very likely to solve two problems in the blocking time if the queue is normal.

    Anyway, I think these problems are interesting and Thanks Um_nik and Codeforces.

    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    1) Больше 40 (!!!!!!!) минут не было вердиктов по сабмитам. На кф теперь такие правила? Почему не предупредили перед началом контеста?

    2) Может тогда время от времени рандомно давать +-100 к рейтингу каждому, ведь "есть много раундов и рейтинг постоянно меняется"?

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

    I wanted to try D using python (which might be TLE), and in case of TLE I would implement a C++ solution. And I saw lot of people submitting D in python. I think the long queue affected in this way many people...

    Beside this, it was a really nice set of problems.

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

    so

    30 minute of queue and system down are not considered as bad things.

    nice to know it

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

    I remembered similar case happened in round# 449(the long queue was like 30-40 minutes if I remember correctly) and the final decision is to make the round semi-rated. So why is the decisions inconsistent and how to distinguish when to be rated, semi-rated and unrated.

    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +94 Vote: I do not like it

    "There are plenty of rounds and the rating always goes up and down, so you shouldn't worry about a slight change that may be caused by the issue.". This was the worst justification I've ever seen LOL

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      Agreed. I can't believe that I heard this from a large coordinator on Codeforces.

      → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +46 Vote: I do not like it

      I think that logic can be applied the other way. There will be plenty of contests in the future so it won't matter that much if this one is made unrated.

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

    I submitted 4 solutions (if I had more 5 minutes, it would be 5) at last 30 minutes, and for all of them I didn't see the verdict. Now I see that my F got WA :(

    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +131 Vote: I do not like it

    Why so afraid of unrated round? Is it fair to submit several minutes after queue fuckup and receive RE1 because of UB, which can be fixed in 10 seconds? Point on rating going up and down is ridiculous, how the participant should estimate what problem to code if he doesn't know on which point the system is gonna go down? The rating of the comment shows what the audience feels about this, hope CF won't ruin the fun for participants this time.

    On the first point: in the announcement it was intended that the queue would resolve before the end of the contest, wasn't it? This ruins completely your first point.

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

    I got MLE on test 15 in div1C. I submitted ~3min after the end of the standard 2 hour round. This is fixable in a minute, but I had no idea it would happen until ~2hrs after the end of the round.

    One could argue I couldn't have submitted before the contest ended had the queue worked normally. One could also argue I could have checked if 22·222 > 256·10242. That's irrelevant — I'm arguing that a slow queue for a non-negligible part of the round makes the round unfair.

    A few minutes before the end? I could accept your argument (although squinting a lot) because it doesn't mess up a round significantly. Half an hour before the end, or more? No.

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

      Actually there will be at max 12*(2^22) edges, which is nearly 200Mb. What is even bad is that it was really close to memory limit and maybe reusing some vectors would had solved the problem easily.

      → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    "so he can test his only problem throughly" — There were quite a few problems with tight TL, and then it's very important to test the running time on CF with the custom invocation. I was impossible because of the big queue.

    The decision isn't terrible but I suggest making it unrated next time with similar circumstances.

    → Reply
»
20 months ago, # |
  Vote: I like it -55 Vote: I do not like it

দ্য হেক!!!!!! কন্টেস্ট রেটেড!!!!???????

আপনাদের কি রোজায় ধরসে?

→ Reply
»
20 months ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

I have a question. Will we face a penalty for extra submissions, when we didn't know the verdict of previously submitted codes ??

EDIT : I have submitted three codes for E in intervals of 5-10 minutes with some optimization, starting at 1:38, and the first solution has passed pretests. If a non empty subset of the other two pass as well, will it be skipped in system tests with a penalty??

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    Obviously (not that it makes sense, but it's definitely how the system works). I even think that technically they don't have the means to store the time when you saw the judgement result.

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

    Surely, we will. This is like this on Topcoder in every contest.

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

    His last submit got tle on pretests. And second last got pretests passed. So will it be judged in system tests? Atleast in tc, it won't be.

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

I'd be fine with round being rated if you hadn't announced that long queue will be resolved shortly tbh.

→ Reply
»
20 months ago, # |
  Vote: I like it +65 Vote: I do not like it

Very last period= 1:30+ I think it should be unrated becasue the influence is really big

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

In Div1 there was queue for around 25 minutes in the end (35 including the extended 10 minutes) , I think that's significant to not keep it rated.

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

Anyone solve C div2 using DP?

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

    Is there any other way of solving it ?

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

      add left and right in a heap and pop from them. the answer would be minimum when done for all elements. The added complexity of adding into a heap comes into picture with this but I think it should pass.

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

        There are two ways: Brute Force + RMQ (DP) or DP (LIS variation).

        Brute Force preprocess for each position i the minimum cost of any j > i such that ai < aj and fix i and j in a double for to get something like this:

        ans = INT_MAX;
for(int i=0; i<n; i++){
     for(int j=i+1; j<n; j++){
          if(a[i] < a[j]){
               ans = min(ans,c[i]+c[j]+RMQ[j]);
          }
     }
}

        DP uses a LIS variation such that memo[i][k] has the value of the minimum cost of using a valid sequence of length k ending in the position i:

        memo[0][1] = c[0];
memo[0][2] = memo[0][3] = inf;
for(int i=1; i<n; i++){
     memo[i][1] = c[i];
     memo[i][2] = memo[i][3] = INT_MAX;
     for(int j=0; j<i; j++){
          if(a[j] < a[i]){
               for(int k=2; k<=3; k++){
                    memo[i][k] = min(memo[i][k],memo[j][k-1]+c[i]);
               }
          }
     }
}

        Finally, get the minimum valid value from each memo[i][3].

        Both complexities are O(n2).

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

      Yes there is ! Fix j and then iterate over elements in interval 1-(j-1) and find the best of them(the c[i] minim that so v[i] < v[j] and i < j) and then the same with k(find c[k] minim that so v[k] > v[j]) and then update the global solution so you have a O(N^2) solution. Sorry for the bad english !

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

    What the complexity of your code?

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

    I think it is supposed to use DP.

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

This was the easiest div2 CF round I have ever participated in.

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

The submission for questionB in div2 stuck in the queue for the last half an hour,

Why couldn't you fix it?

I was vey dissappointed. It still says the the code is in queue -_-

→ Reply
»
20 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Worst div2A I have ever seen -_-

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

    Definitely

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

    Very, very true ! The story just didn't have anything to do with the other problems ! I think the writers focused on the harder problems because they knew that an Div. 2 A or B can be made in under a minute, so they didn't pay attention to make it good

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

I think System testing will be over after 6 hours, any one thinks more??? let's see who can guess correctly :D

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

    I'll bet for 3:15(UTC+8)

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

    It's still in queue. Guess Codeforces servers are working perfectly fine :-p

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

35 minute queue..... Do you want anymore??

→ Reply
»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Please leave it rated, round was great!

→ Reply
»
20 months ago, # |
  Vote: I like it +253 Vote: I do not like it

This is what happens when you forget to thank MikeMirzayanov

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 11   Vote: I like it +17 Vote: I do not like it

    yeah,it's seems that there are always some incidents occur when setters forget to do that.

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the pretest always contain tests with maximum test data?

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the last 15 minutes of the contest, I've waited for my verdict of D. But it's still in queue after half an hour of the contest. Even the hack page was not responding. And you're saying it's rated! Although, rating is not the purpose of the contest but making this contest rated is not fair.

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

    I also did not see the results of my submission + hacks did not work.

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

    Many of us agree, but there are too many comments of the same thing on this page ! Stop it ! There should be only one comment of this posted and the rest of us just upvote it ! Are you just farming upvotes or what ?

    → Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +115 Vote: I do not like it

Real reason why round is rated:

Spoiler
→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    yeah,that's a interesting take.

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2E/div1B (I will be getting WA but still in queue) why is this wrong

Find min number of swaps required to sort the array. let it be x. then if 3*n — x is divisiblle by 2 then Petr else Um_nik.

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

    I've done the same thing, but got Pretest Passed.

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

      I checked on some sample with OO0OOO00O0OOO0O00OOO0OO code and it gave wrong for me

      Maybe my implementation is wrong? I took the min swaps from geeks for geeks.

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

        I've done simply that iterated over 1 to n and put the ith number on ith index.

        Well also i guess for minimum swap u need to appy merge sort.

        → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Div2 D ...??

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

    For each type of product, do a bfs and find minimum distance between any node with type i and each other node Knowing costs for all the types, you can just sort each of the n arrays and take the smallest k values

    → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Try to find the minimum distance between every node i and a specific kind of good j,let's make it mind[i][j].all you need to do is run BFS for every j and sort mind[i] out. (maybe some stupid grammar mistakes,forgive me for that,please.)

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

Contest status queue is stuck again.

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

Too long queue to keep it rated. Everyone who submitted between 1:30-1:55 has a very big disadvantage because they have to check their solutions otherwise they can fail at PRETESTS AFTER THE CONTEST. Who didn't submit this time of the contest just gained 10 extra minutes to solve 1 more problem. This is unfair. Make the contest unrated.

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

    Agree ! But there are too many comments of the same thing on this page ! Stop it ! There should be only one comment of this posted and the rest of us just upvote it ! Are you just farming upvotes or what ?

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me hints or solution for Div2 D and E. The best I could think for Div 2D was brute and I'm clueless for Div2E

→ Reply
»
20 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Still my submission is in the queue and they want the contest to be rated.

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

    Mine too ! But there are too many comments of the same thing on this page ! Stop it ! There should be only one comment of this posted and the rest of us just upvote it ! Are you just farming upvotes or what ?

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

      Now there are too many comments from you about the same thing on this page! /s

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

    Same condition here .. 50 minutes still waiting for the submission to be evaluated

    → Reply
»
20 months ago, # |
  Vote: I like it +97 Vote: I do not like it

→ Reply
»
20 months ago, # |
← Rev. 3   Vote: I like it -20 Vote: I do not like it

emmm

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

It seems round was unfair to java users..

→ Reply
»
20 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Did anyone else also find time-limit too strict for problem div2 D? got TLE with N*K*logK solution.

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

    Er,I think the best solution is O( K*(N+M)+ N*(KlogK)(that is for sort) ) by using BFS.

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

      yes, I also had done the same. I had used heap(priority_queue) instead of sorting.

      But finally got accepted with (N+M)*K.

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

    Yeah happened to me . I would like to know if this is a problem specific to Java. I didn't use ArrayList for adjacency list , maybe PriorityQueue caused the issue. I think using just arrays everywhere instead of Collections could speed things up.

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It passed 1h after the contest,but my solution for Problem E(Submit at 123min after the contest starts) is still in queue...

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

Why does life have to suck so much? I got tle at problem E because of a stupid mistake i make,instead i have to wait till the end of the contest not know anything about my mistake. If the queue isn't retarded today i would have AC problem E. Thanks so much life.

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

    And why is cf so laggy nowadays,after the contest i can't get into the website for 2 hours.Stupid.

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanos's glove dissipated my rating.

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

    i have no idea why my code was showing wrong answer on pretest 1 even when locally the answer was right

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

sorry my good sir,

i just wanted to point out that my C got MLE on test 1 that i couldn't fix because i got the verdict after the contest ended :) .

AND NOW I AM TRIGGERED :) .

→ Reply
»
20 months ago, # |
  Vote: I like it +75 Vote: I do not like it
spoiler
→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2E, is it enough to consider only num_components % 2? I submitted when the queue was too long, and can not see how result is.

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

in div2E\div1B why was it given that permutation was random, or that n>1e3? it confused me so much :D

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

    So that you think twice before submitting. And It should look like it is div2E\div1B problem.

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

asymptotically my submission for problem Div2 D looks right can someone point out why I got TLE my submission

→ Reply