djm03178's blog

By djm03178, history, 4 months ago, In English,

안녕하세요, 코드포스! (Hello, Codeforces!)

I'm glad to invite you to Codeforces Round #620 (Div. 2). The contest will start at Feb/15/2020 16:05 (Moscow time), and it is rated for all participants with ratings under 2100.

You will be given 6 problems and one of the problems has 2 subtasks. The contest duration is 2 hours. The score distribution will be announced later.

All problems are prepared by me, with huge help from the testers with developing great solutions.

I'll be on the community Discord server after the contest to share my thoughts and get feedback about the problems.

Thanks to 79brue, molamola., FlowerOfSorrow, evenharder, cs71107, Justice_Hui, rkm0959, chpark1111, imeimi, alswhp, gaelim, jh05013 (Good tester), yuto0518, N_jara, aryanc403, SnowGoose, --Someone--, surung9898, and ko_osaga for testing the round. I would also like to thank 300iq for round coordination, and MikeMirzayanov for the great Codeforces and Polygon system.

Hope you enjoy the problems!

UPD: The scoring distribution is 500 — 1000 — 1500 — 1750 — 2000 — (2000 + 1000)

UPD2: The contest is finished! Thanks so much for your participation! The editorial is here.

UPD3: Congratulations to the winners!

Div. 2

1: ltst

2: COVID-19

3: cosplay

4: sincerity

5: ChitandaEru

Unofficial Div. 1

1: wucstdio

2: ksun48

3: jiangly

4: uwi

5: teapotd

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

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

A Korean round after a long time.

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

Wow! Another Korean Round! I hope you enjoy this round. I am a tester of this round, and I think you would enjoy! Good luck and have fun.

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

I don't think jh05013 is a real newbie.If you see in his first two contests he solved 4 problems and then i think he just didn't care about his profile maybe because he likes being a tester more , so he just intentionally solved 0 problems.And no offence jh05013 but you are just 3 points of rating away,breaking the world record of the most newbie.

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

    he said in the linked thing that contests were too stressful for him (he was 1700+). Now he just don't care to mess up :)

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

      Moreover, in this link, he said he is willing to inspect contests(though these are other site contest), and said to call him a tester if someone wants to. Based on the positive response people have to this article I can conclude he is a good tester.

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

Finally a newbie Tester this time... So all colors tested this round...sweet

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

우왕!

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

colorful testers

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

Fan E AE YO

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

:v Testers in every ranks !

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

G

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

    Alright the time will be changed accordingly as cf revolves around your schedule :p (not rlly)

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

Editorials ?????

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

[Deleted]

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

Hope B will be clear this time. Past 2 contests Test Cases for B were very hard.

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

OwO,well...Korea round is my nightmare,hope pass C

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

As one of the lower ranked testers, I would highly recommend participation in this round. These are good problems, there is something for every skill level here!

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

I wish positive rating for every participant :)

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

    We all wish that but this is not possible.

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

    The total rating decreases after every contest, otherwise, ratings will become higher and higher because new users will join Codeforces with the initial 1500 rating points.

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

Round with subtask

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

팬이에요! :fan:

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

    Is Codeforces started to support the Korean language? Cool.

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

Can someone tell me what does one of the problems has 2 subtasks means? thanks in advance.

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

    I'm not quite sure, but it may be an easy version and a hard version of the same problem. Like C1 & C2 for example.

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

    One of the problems has an easy version and a hard version. You'll know which problem has subtasks after the contest starts.

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

expecting implementation problems in both A and B.

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

I hope the problem statements are short and clear.

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

Want to be Pupil today.Wish me good luck

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

I wonder what is jh05013's real rating.

Because when he became blue.I can only solve div.2B problems

Maybe he have a real rating of Grandmaster or higher :>

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

I found a really interesting thing that jh05013 and I have both the lowest rating -43 and after that, our ratings both increase 3.

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

Hope contest will be interesting like previous one

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

How to solve E?

Edited : Thank you to all who replied. Because I got TLE on pretest 14 during the contest, I'll try again using the faster LCA algorithm.

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

    Hint: The added edge is there for parity reasons.

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

      I know that, but I failed to optimize the running time.

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

      Do I need to know "LCA"?

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

        Yes.

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

          In fact,I have never solved any problem about "LCA".I need to learn more!

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

            That was the reason I got when I said E is a standard problem.

            300iq : "We thought it is not so standard for div2 participants."

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

            wai- how are you even cm?

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

      I know parity reasons. but I don't know distance between two node is long than k or not without time limit exceeded.

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

        With LCA you can find the distance between two nodes in a tree in $$$O(1)$$$ or $$$O(\log n)$$$ time (depending on which LCA algorithm you use).

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

        I think you need learn "LCA".

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

          Thank you, I catch a keyword. I'll study LCA algorithm.

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

            I didn't solve this problem as well,because I didn't know how to know the distance between any two nodes quickly.QwQ

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

    only three possible ways l = a -> x -> y -> b l = a -> y -> x -> b l = a -> b

    if l<=k and l%2==k%2 then we have a solution

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

      Did the same but didn't work :(

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

      I do not get it how to find the shortest possible path after adding x,y, we need that to check against k. Somebody explain?

      Edit: Or is it expected to do a BFS to find it? That would be to slow.

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

        You need to make use of precomputing depths, and LCA ( Least Common Ancestor ) of two nodes. Read more here.

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

          The LCA does not help if the path after adding the new edge x,y is shorter than the one through the LCA.

          Edit: After reading the other answer below I understand. We simply use LCA again to find path length from a to x and y etc. Thanks for explanation.

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

            Read my comment below. After adding the edge the shortest path will have to be one of the three alternatives. ( It can be proven ).

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

    The path between two vertices in the query may either go through the added edge or not. Analyze these cases individually, finding path lengths in O(1) using whatever fast LCA algorithm you prefer. Then if the difference between the length of the path obtained in some of these ways and the desired length if divisible by 2, answer is yes, otherwise no.

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

    Root the tree at an arbitrary vertex. Precompute depths of each node to give distances between two nodes in $$$O(log(N))$$$ time using LCA.

    When adding a new edge $$$(x,y)$$$, there are now three possible paths ( without going back and forth ), which are

    1. original path between $$$(a,b)$$$

    2. $$$(a,x), (x,y), (y,b)$$$

    3. $$$(a,y), (y,x), (x,b)$$$

    Now, if any of these paths can reach $$$b$$$ from $$$a$$$ in less than or equal to $$$k$$$ steps and has same parity as $$$k$$$, then answer is YES.

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

    First we do not consider added edge. We can 'hang out' instead of actually making meaningful move as much as we need — which is, if we can arrive $$$b$$$ at $$$t$$$, we can hang out some even number of steps loafing back and forth.

    Then we consider new edge. Since new edge form a cycle, it opens new possibility — by loafing around in cycle. If cycle length is $$$l$$$, we can arrive at

    $$$p + a\times l + 2b$$$

    for any arbitrary nonnegative integer $a, b$, where $$$p$$$ is shortest time we can arrive at $$$b$$$ using the added edge. (If we are not using the new edge, we can't hang out on the cycle).

    All we need is careful casework (there aren't many) and computing distance in trees using LCA or some other fast methods.

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

Am I the only one who solved A with binary search instead of much more obvious 1 liner solution?

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

    If there is the point to which we get after $$$k$$$ steps from both $$$x$$$ and $$$y$$$ is

    $$$x + k \cdot a = y - k \cdot b$$$ $$$k \cdot a + k \cdot b = y - x$$$ $$$k\cdot (a+b) = y -x$$$ $$$k = \frac{y-x}{a+b}$$$

    So, if $$$(y-x)\%(a+b)=0$$$

    then answer is $$$k$$$, in other case the answer is $$$-1$$$.

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

      I realised this simple solution when I revisited problem A for locking it, after solving up to problem D.

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

      this is owsam explanation but I used binary_search here

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

    me too, was wondering how others solved it so fast

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

    I used binary search too, and needed the editorial to make me think of manipulating the equation :)

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

    You are not alone, binary search was the first idea I thought of.

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

How to solve C?

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

    After each customer comes in, you have an effective range of temperature, let it be (x, y). For the next customer find the intersection of (x — t, y + t) (where t is difference between entry times) and his temperature range. That is your new effective range. Initial range is (m, m). If all the intersections are non-empty you can satisfy, otherwise no.

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

      Thank you, it certainly makes sense to me now

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

      I did the same thing but I got WA in pretest 3

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

        I got the same result in the beginning. Apparently, I was breaking out of the for loop without taking all of the input.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • Group all customers attending at a given time t.
    • For each group check if there is an overlapping temperature range and store that. For instance if the ranges are [(1, 4), (2, 5)], the overlapping range is (2, 4).
    • If it's not possible to form an overlapping range at any t, then it's not possible
    • Assuming each t has a range, check if it's possible to move from range at ti to range at ti+1. Also update the range of temperatures possible at each step.
    • If possible range at step i is (lo, hi), Then possible range at step i + 1 is (lo - (ti+1 - ti), hi + (ti + 1 - ti))
    • Just check if that is acceptable for all customers at ti+1 and update lo and hi. (Not sure if this step can be optimised further but it passes the problem limits)

    My submission 71152069

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

    I have a solution that is easier to implement in my opinion.

    Loop through all pairs of customers. If it is impossible to reach the second Customer's range from the 1st Customer's range in the time difference between them, then the answer is impossible.

    O(N^2) solution.

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

How to solve C and D guys ?

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

    For C

    Let's say that we have minimal and maximal temperatures with which we can get to the next consumer, and if the intersection of our range and range (l,r) is not empty, then it's okay, now we just update our range — basically it would be equal to intersection of ours and (l, r).

    My submission: 71146715

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

      Thanks, I only know how to solve case (x < l) and (x > h) but not (l <= x <= h) :<

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

        Ahh, so you needed to have a lower range and upper range... I tried recursion which in one case i try to reach the lowest possible temperature, in other the highest, tho i couldn't implement it fully :D

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

      good explanation thanks Mr.Hakimov

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

    For D

    The main idea here is that for minimum we should build our array in such a way that bigger numbers have lower indexes and for maximum bigger numbers should have bigger indexes.

    You can chek out my submission: 71159214

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

      Thanks. But can I solve D problem using prefix array & suffix array ?

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

        That's a good question, but I don't think that there is a necessity in them :)

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

          If I use prefix-suffix array, what should I approach

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

how to solve D?

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

    For Min: starting from the first '<', start at n and go down but if there are <<<< or something sort that subarray then for the rest just go down by 1 each time so say for the 2nd sample, my answer would be 5 4 3 7 2 1 6

    Max: for max it's the same thing but all the numbers after a < are going up so 5 4 3 6 2 1 7

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

Thanks for the contest, have a good day problem setters <3

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

In Problem B of DIV2. the problem statement mentioned that the string can be "REORDERED" and not "REVERSED" but my code was failing the first testcase here : https://codeforces.com/contest/1304/submission/71145055

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

    No, you can't reorder a string. You can reorder the list of strings.

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

      Ohh Okay. But this got me very confused and thus wasted a lot of my time.

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

    strings can be reordered not a particular string !

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

    I can't see your code, but "Strings can be reordered" means order of concatenation can be changed, not the strings themselves

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

    The list of strings can be reordered, not the strings themselfes.

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

    My AC solution outputs the test case: 2 2 aa aa -> 2 aa. When I think it should be aaaa, 4. Can somebody explain me why !?

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

      It is an invalid input because all strings must be distinct.

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

Can someone please tell me why this code for C is giving rte. The only place where an exception can be thrown is the assert in which case the test cases are wrong. https://codeforces.com/contest/1304/submission/71155599

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

    Perhaps it has to do with your usage of the word "time"? I think it's a reserved keyword that can still do arithmetic with integers. You're right, the code itself doesn't seem like it can segfault as far as I can see.

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

      I had submitted the same code without the assert line. That gave wa.

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

        That doesn't necessarily imply much; undefined behavior is still within your set of possibilities. In fact, I'm much more inclined to think that you have UB somewhere; this would probably cause a segfault sometimes and a WA at others.

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

          The thing is that I have been getting RTE only when I have included assert in the code. I have submitted the same code without assert thrice (introducing one useless variable each time so that it allows me to submit) and got WA in all those.

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

            I've gotten several questions regarding this.

            The problem is that you're "returning" the function while you haven't gotten the full test case yet. Some people used 'break' inside a loop. These codes generally got incorrect on pretest 3.

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

              Yes that's the mistake. Thanks for pointing out and sorry for wasting your time.

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

    I got similar Runtime error in Problem B today. It was resolved by removing #define int long long. I couldn't figure out Why it happened today, I haven't faced any problem due to this statement earlier.

    My Submission link: Submission

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

    You are returning from function, "solveTestCase", before taking all inputs. Instead return only at the end of the function.

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

      Okay yes. That is the error. Thanks for pointing out!

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

Every time........!

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

Thanks for the round, hope pretests were good enough.... I wish everyone to increase their rating ;)

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

Oh,just five minutes after the contest over my solution passed all the examples.:( The code for the round are a little bit long. I think a longer time will be better.:)

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

Why does codeforces skip main test and don't take the best submission? I missed my chance of becoming Master today.

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

I don't understand what is wrong in my submission, the answer is printed but still it shows run time error. Here is my submission 71154644

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

here i come #808080

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

really sad, failed B on test 13.

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

It was such a good contest for the beginners. As the problems were not so hard as before :) But I think it should be harder, especially the Problem F.

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

My color is going to change. I love these questions!!!

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

Thank you for strong pretests!

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

Question B : Why there is run time error coming in https://codeforces.com/contest/1304/submission/71161367 this code can anyone tell me?

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

    because of this loop for(i=v.size()-1;i>=0;i--). v.size() does not return int value.

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

    The problem is multi-case. which means you can't puts("NO") then simply return, or as the input continues, in fact your program will read the wrong data.

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

What is the mistake in this code, I am getting wa on prestest 8

code: https://codeforces.com/contest/1304/submission/71165457

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

    If you erase elements in a set while iterating through it, especially your current pointer, you might end up skipping a few elements. This is shown when you run your code on the following case:

    4 2
    ab
    cd
    ba
    dc
    

    A different approach is to scrap the set entirely and instead use an array of strings, with boolean markers that say if you've used that string already (example, with the mk array).

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

      Thanks a lot man!

      But why does it skips a few elements?

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

        I didn't realize that you called a vector s, but it functions the same as a set in this context. My bad.

        Imagine your vector like this:

        ab <- (pointer)
        cd
        ba
        dc
        

        Now you find ba to be a match with ab, so you erase them both. Where does the pointer go? It can only advance to cd:

        cd <-
        dc
        

        Now you increment the pointer, and it ends up at:

        cd
        dc <-
        

        Since you only check ahead of your current iterator for matches, you don't find anything else and terminate. There's probably a topic on StackOverflow addressing this issue, but the basic premise is to only increment when you don't erase.

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

          Thanks for the wonderful explanation man. Fully understood it! Thanks once again for your time and have a nice day!

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

I believe test cases for D are a bit weak?I changed my code for D a bit during contest as it had 1 mistake, but after the contest, it still passed....

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

71166353 works on pretest 4 on my machine, and on ideone link but failed during contest and also on custom invocation. MikeMirzayanov djm03178

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

    71177225 unordered_map -> map => WA -> AC

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

      the same code gives correct output on my machine and another ide and on codeforces if used with c++17 but fails with c++14, i want to understand why is that the case, exactly what is not working in this case.

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

        have you figured it out?

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

          no, changing the order of input strings makes the test case pass in custom invocation on cf, when i tried to debug in cf custom invocation it was weird, somehow the entries in my unordered_map were getting corrupted during the execution. AK18

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

          AK18 however the logic is same, unordered_map -> map should make no difference really, to me it seems like deep magic

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

My solution of B is failing in this test case but somehow it managed to pass system testing —
3 3
tab
bat
tab

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

I think it is good blog when i saw in my life

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

where i am wrong? https://codeforces.com/contest/1304/submission/71174871 problem C

i am iterating in reverse, finding the largest intersection possible so that both current and previous customer are satisfied with temperature

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

Not sure if I should be posting this here, but:

I just got a message saying that my solution for problem E coincides with that of some other participants. This is likely because I used the CP Algorithms implementation for LCA which you can find here: https://cp-algorithms.com/graph/lca.html

Although I added a few additional methods in my source code, a big chunk of my solution was for the LCA structure. So I guess that could've set off the response. I hope this clears things up.

If you need any more information, please let me know. MikeMirzayanov

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

Anyone can help me debug it? here I was trying find max and min possible temperature at every next moment when customer appear.

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

    Nevermind, I managed to repair it thanks to one of solutions, so... -->here It seems that I like to complicate simple things. That things happen when I try to rush too much, and type faster than know solution.

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

I am not sure whether I should comment here . but i just got a warning about coinciding my code with another user.Since I am new here , I dint know about the codes copying from ideone . I was using IDEONE in default setting. My code is https://codeforces.com/contest/1304/submission/71137281. And the guy who copied my code is https://codeforces.com/profile/8bit_thug I request you not to do this. this kills contest spirit. And yeah Since He submmitted code after 3 minutes when I submitted hence it is cleared that he copied my code. Moreover all his submissions are skipped. Do I need to provide more information? MikeMirzayanov

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

My solutions for this contest were skipped most likely because I used the implementation of LCA from here which is probably where some other participants picked the code up from.

djm03178 can you look into this?

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

Мое решение 71159863 по задаче 1304E совпадает с решением другого пользователя, так как видимо мы использовали один и тот же источник, а именно https://e-maxx.ru/algo/lca.

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

I got a message from User system regarding code similarity about the E problem (71164831). I have used the code for lowest common ancestor from this site (same code published in the site mentioned by other affected users) which was last updated on 15th June 2018 (here) which is conclusive evidence of this being published well before the contest.

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

I hope this is the right place to put this, otherwise, please tell me where I should write this. I received the following message:

Attention!

Your solution 71159069 for the problem 1304E significantly coincides with solutions ksun48/71134293, hoke_t/71152328, Venia/71156816, hanga97/71159069. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

For the solution of problem E, I used the RMQ (range minimum query) and LCA (lowest common ancestor) implementations from https://github.com/kth-competitive-programming/kactl/

Specifically from https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/RMQ.h and https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/LCA.h

This code was online long before the start of the round, so I hope, this issue can be resolved.

Thanks for the round btw. I enjoyed it.

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

Can someone answer why the compiler of Codefoces gives run time error if i have not type casted size of a vector whereas most of the other compilers don't give that error. In this contest only i got stuck in problem B due to this error.

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

    Me too

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

    the .size() function returns an unsigned integer, so when you try to do.size() — 1 when the size is 0, it overflows and causes runtime error.

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

      Got that...but when i did this for(long long i=a.size()-1;i>=0;i--), it gave me run time error but for this for(int i=a.size()-1;i>=0;i--) it did not. Can you tell me why this happened? And thanks in advance :)

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

        Because 0ull — 1 is much larger than 0u — 1?

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

Can someone please explain how I am getting a different output for E on my local compiler than the codeforces judge.71178404

I am the getting the expected output on my machine. I believe the logic is correct. https://ideone.com/LfR13i Expected output with same input

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

Nice problemset!

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

Hello MikeMirzayanov, I have received a message about being disqualified from the contest, because of plagiarism. I have used the LCA calculation from cp-algorithm. Here is a link to the web archive, as evidence, that the code has been published before the contest. I have not used any online IDE. Kindly look into this, Thanks a lot!

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

Hey,
My solutions were skipped because one of them coincided with solutions of other participants.
It was 100% caused because of this implementation of LCA, which I use for a long time.
Regarding rules, one can use publicly available implementations posted before the round.
MikeMirzayanov can you do something about this?

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

Me in this contest:

Firstly, solve problem C, and then B-A-D-E-F.

After solving all the problems, I looked at the standings, and found rank 2 is only 61 points lower than me, and he has locked all his problems and started hacking.

So I locked my ABCDE and started hacking too.

When I opened a solution to problem B, I was surprised to find there was a very silly BUG. A code with such silly BUG wouldn't pass the pretests.

So I took a look at the statement, only to find that I had misread the problem. I thought I can reverse any strings as well as reorder them.

1000 points! If I had not made such a silly mistake, I would probably get on the 1st place, but now I couldn't resubmit because I had locked my problem. So I poured out my sadness to jiangly, who had solved all the problems too and become rank 3 at that time.

Here is the chat history:

Yes, I misread the problem again. I forgot that all the strings are distinct.

So from my story we can conclude that it's very important to read the statement carefully, but if you misread the statement, you still have chance to pass the problem.:)

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

    Lol same. I also thought I need to check the length of the only palindromic string I will add in the middle and changed my code in the last minute of the contest. And after 5 minutes comes the realization that all the string have the same length. Lost 500 points and went from +45 to -13.

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

    I just found out that I also misread. Thank you.

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

Problem B would not have been much harder if the restriction on the strings having equal lengths were dropped.

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

can anyone explain why my code is failing on testcase 8 in problem B. LINK to source code :: https://codeforces.com/contest/1304/submission/71215931

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

    I don't really know, only fast checked, but do you think is it safe in the last iteration? I'm aware s.begin()+i+1 seems to be higher than s.end()?

            vector <string>::iterator it=find(s.begin()+i+1,s.end(),a);
    

    I think it's better iterate to s.size()-1

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

In problem D, you can solve for max LIS and re-use it to find min LIS by manipulating the string, ie. reversing and inversing — replacing $$$<$$$ and $$$>$$$ with one another. Here is my solution.

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

Great contest!

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

congratulations to the winners of this round

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

My contest history for this contest is suddenly deleted.Why this happened?

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

    Rating changes for the last round are temporarily rolled back. They will be returned soon.

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

apology for poor english

where were you when top rate dies

i was sat at work writin code when telegram ring

'top rated is die'

'no'

and you???????

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

hello in solution B try this 2 3 AAA AAA and it will answer you 3 AAA i think it should be 6 AAAAAA anyone can help me with this i can't see in description that say the same string doesn't count