Golovanov399's blog

By Golovanov399, 6 weeks ago, In English

Sorry for the issues with a couple of problems

Problem A of tc/div2 (Finding Sasuke)
Problem B of tc/div2 (A New Technique)
Problem C of tc/C div2/A div1 (Perform Easily)
Problem D of tc/D div2/B div1 (Shurikens)
Problem E of tc/E div2/C div1 (Solo mid Oracle)
Problem F of tc/D div1 (Roads and Ramen)
Problem E of div1 (A Convex Game)
 
 
 
 
  • Vote: I like it
  • +146
  • Vote: I do not like it

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

almost got the idea of DIV2 C :(

»
6 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

div2 D was way easier than div2 C !! anyways great contest indeed !!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't agree with this. I solved Div2 C in less than 15 minutes, and couldn't solve Div2 D at all. IMHO, the second part of solution in editorial is more difficult than it could be, because after sorting the pair array, we can simply use two pointer method

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

Explanation for some questions are not upto the mark.

»
6 weeks ago, # |
  Vote: I like it +83 Vote: I do not like it

I think proof of Div1 D looks incomplete. You should also consider a case when diameter and optimal path intersect, I think they are a bit different.

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

    Please mark your comment with spoilers. Some participants might want to upsolve without spoilers.

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

      Well, reading comments under editorial is a bit reckless if you want to solve problems without spoilers

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

      ahahaah he destroyed you nub

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

    Yeah, little bit.

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

    Correct me if I'm wrong, but I think it still holds when $$$C = D$$$ (optimal path intersects diameter) and when $$$D = F$$$ (optimal path begins somewhere on diameter), so that should cover all the cases. The proof does not make assumptions on edges existing between nodes in the diagram, so setting paths have zero length should be fine.

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

      If C=D then everything is fine, but if diameter and considered path have some edges in common then it is a bit different

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

        ah, i see. i agree that it's incomplete then, there's no way to cover that without another case.

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

Golovanov399 why my sol for div2 D getting tle https://codeforces.com/contest/1435/submission/96683823 please help...

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

    Try taken.lower_bound() instead of lower_bound(all(taken))

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

      Why does this work?

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

        In simple words lower_bound(all(v)) uses random access iterators and works well only for vectors, arrays etc. whereas s.lower_bound is a function built to handle binary search for sets, multiset etc where elements cannot be randomly accessed. there is a blog about this, try searching if interested further.

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

        In c++ set or multiset, it is better to use the in-built lower bound function as in the worst case, it has logarithmic complexity. The other one has a quadratic worst case time complexity.

»
6 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

Is tourist's submission for problem E somehow rejudged?

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

    Yeah, it was stated that $$$v_i > 0$$$, while in fact it was generated (and then validated) that they can be zeroes. It turned out that the second Gennady's submission failed just because of that (and then he wasted the last hour finding out what was wrong).

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

      He came first without having to solve D, so it is all good. Otherwise, the round would have been unrated for him right?

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

        I guess yes.

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

        He doesn’t need D and he can be the first.

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

          If someone had solved all problems, I'm pretty sure tourist wouldn't have come 1st. If the statement was correct initially, he would have probably spent the last hour on solving D maybe.

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

      What a good way of preventing someone from AKing your contest.

      (Just kidding. )

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

There's O(n) solution for div2 D using stack. See my code.

But it's hard to explain for me..

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

Did anyone solve D2C with DP? Is it even possible?

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

    I did and got FST :(

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

    Yes I tried Div2 C with DP, but it failed on test-case 25. But I realise now that it is not possible to solve it using DP. Here is my submission 96694460

    Atleast in the way I have defined my DP states.

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

      Same pretest got us :(

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

      I believe my solution has the same idea 96688698, but why do you think it's not possible?

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

        Because in DP solution answer of current state is dependent on previous state and we minimise the difference between minimal and maximal fret. But consider the 25th Test case.

        101 146 175 if we subtract 1 96 100 respectively from it we obtain our answer.

        But DP solution will choose :- 96 96 100 for subtraction, because difference between 5 and 50 is smaller as compared to 100 and 50.

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

          Lol, I combined our solutions and it got AC. That's weird. I also added sorts to my solution as you did 96712200

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

    I have a DP + Greedy solution. Here's my submission.

    Explanation — First comes the greedy part. By observation, it can be seen that after sorting both the notes and $$$a_{i}$$$, it will always be optimal to first choose some elements from the first string, then some from the second, and so on. So, after choosing a particular string $$$k$$$ for some $$$i-th$$$ note, the $$$(i+1)-th$$$ note will be always from a string $$$j\ge k$$$. This can be implemented using DP.

    In my solution, $$$dp_{i,k,j}$$$ is the state where the $$$i-th$$$ note is being considered to be assigned string $$$j$$$ and the $$$(i-1)-th$$$ note has been assigned the string $$$k$$$. The second.first, second.second and first fields of the states represent the minimum value chosen till now, maximum value chosen till now and their difference respectively.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks very much for the code. Codes speak for themselves

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

      Can you elaborate this point of yours? — it will always be optimal to first choose some elements from the first string, then some from the second, and so on. So, after choosing a particular string k for some i−th note, the (i+1)−th note will be always from a string j≥k.

»
6 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

I am confused about div2 C.First I got WA then WA on pretest 7 and Then WA on pretest 9. It sucks :(

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

Was able to solve B today but not A :|

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

    Me too, feels really bad. Another bad thing is stuck on C but then find D so easy after contest

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

Div2C : Each note can be played on a specific range of frets. So out of all such ranges, find the minimum end point (at least one note cannot be played using a higher numbered fret) and the maximum start point (at least one note cannot be played using a lower numbered fret) and output max(0, max_start — min_end). Can anyone point what is wrong with this approach and provide a simple counter test?

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

    I did the same..

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

    Firstly, it would not work on test:

    Test #1
    Answer

    And also consider this testcase

    Test #2
    Answer

    I hope I understand you correctly.

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

can someone tell my why I am getting tle https://codeforces.com/contest/1435/submission/96685352 in problem D.

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

    Your solution is O(N^2).
    final.size() will become N gradually. Since the outer loop is running 2*N times, complexity is O(N^2).

    Note: 1+2+3+...N = N(N+1)/2 = O(N^2)

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

Problem D2C/D1A has a DP tag in it. I would really like someone to help me with the DP solution for D2C/D1A if it is possible. Thanks in advance !

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

i got TLE with N*M complexity on B, helllooo? what's wrong with this " https://codeforces.com/contest/1435/submission/96705114 " ??? i got accepted with " https://codeforces.com/contest/1435/submission/96705022 "

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

Super easy solutions and implementation for problems Div2 D and Div2 E: Div2 D: 96705496 Div2 E: 96705529

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

    D is much easier that the one u linked, just one stack and O(n).

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

      Yes, I see. Complexity can be further reduced to O(N).

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

      Thanks for the solution, mate! Very nice observations

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

can some one explain me the solution of div-2 D...?

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

Why problem-B is getting Time limit exceeded on python. I tried to submitting others code which got correct during the contest but still, it is getting Time limit exceeded. I am using python-3 and also tried using pypy.

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

In problem Div2D, if we are getting queries of form "— num", we are updating the lower bound , what we need to do when we get query of type "+" ? I didn't understand this line from editorial "and remove any one of them, because we cannot remove any other shuriken"

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

Question D div2 can be solved in O (n) rather than O(n*log(n))with simple stack and easier implementation, here is an ac solution. https://codeforces.com/contest/1435/submission/96693538

(Only the solve1() function is the code for this qn)

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

4 + - 1 + + - 4 + - 2 - 3

I have hacked my own solution for Div 1 B/Div 2 D with the above test case. My submission:- 96706130 Systems tests are so weak Golovanov399 amethyst0 Endagorion AndreySergunin

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

    Wow, I'm really surprised by that considering how easy it is to make good YES tests: just make a bunch of small random YES tests and it's really easy to combine them into 1 big test(just increase the numbers in each small test by the sum of $$$n$$$ of the small tests before it)

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

    each price from 1 to n occurs exactly once

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

Div2 D O(n) solution explanation: note that

  1. if we have several consecutive -x, they must be in an ascending order (otherwise we say NO and stop instantly)
  2. if we have + and a -x after it, we can collapse them (it's not hard to understand that if the answer is YES, we can act this way, just a simple mindfulness exercise)

Bingo! We've just solved this problem in O(n) using stack (going in the reversed order, putting goods on a stack and then taking them from the top of the stack and putting on the showcase). The only tricky moment left: you must pay attention to the amount of shurikens to avoid the lack of them (e.g. example 2 from the problem).

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

Someone please tell where I went wrong 96696335

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

Can anyone tell me why my submission for Perform Easily failed pretest 9 : 96698325 ?

My logic :

The maximal and minimal frets are obviously useful frets i.e. they are used by some fret. So I first sorted the notes and then fixed the "minimal used fret" by using the frets required by the first note by the various strings (the logic being that the smallest note will use the smallest fret from all possible combinations). So out of the 6 frets usable by the first note, one of them should be the "minimal" fret of the optimum set. Then I just binary search for the right hand side by checking if all notes can be played for the specified minimal fret.

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

    Please anyone please help me out why this submission failed testcase:9

    Code
»
6 weeks ago, # |
  Vote: I like it +118 Vote: I do not like it

Div1 D can be solved via top trees without analyzing the problem.

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

    It seems to be difficult to find any information regarding top trees. Do you have any article regarding this?

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

      Please anyone please help me out why this submission failed testcase:9

      My Code
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      At a high level, top trees are just link-cut trees but with a BBST of light-children at each vertex, which allows you to do subtree queries. If you don't understand link-cut trees, learn those first.

      The main paper for the popular splay-tree-based top trees is "Self-Adjusting Top Trees" by Tarjan and Werneck. This also contains references to alternate works by Frederickson and others which have alternative (but more complex) constructions, so you can read those for more background/theory.

      I submitted a top-tree solution to this problem 96759325, but it's rather complex and not a great way to learn. The quintessential top-tree problem is SONE1 at http://www.lydsy.com/JudgeOnline/problem.php?id=3153, but the site seems to be down right now.

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

      https://negiizhao.blog.uoj.ac/blog/4912

      Here is a brief introduction of top trees (with some applications I could come up with), but it is in Chinese. I may supply an English version later.

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

How to solve Div 2D using priority queue ?? I don't understand this line from editorial. Otherwise, for all shurikens that had a lower bound of something less than x we increase it to x, and remove any one of them, why do we have to remove any one of them when we exactly know which one to remove , how to handle the other type of operation "+" type .

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

    You can check this solution 96682108

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

      can you please explain the idea behind your solution .

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

    We can iterate an array in a reverse order. (Example 1)

    +
    +
    - 2
    +
    - 3
    +
    - 1
    - 4
    

    we can create an array like this [-1,-1,2,-1,3,-1,1,4] where -1 indicates that the element was inserted(+ sign). Now maintain a min-heap. Iterate backward on this array, we will keep on inserting the elements. We will first insert 4 and 1. Now whenever we land on -1, it means at this point, some shuriken must have been added on the showcase) which can only be either 4 or 1(Since they are sold at the last). So, we can safely remove the minimum element from the heap and add it to the answer. If the heap is found empty at -1 or if we find one of the element in the heap is less than the element to be insert then the array is inconsistent. Also, we can check if number of +'s is equal to n. If it is not equal then the answer is "NO". 96748102

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, can you elaborate this part we find one of the element in the heap is less than the element to be insert then the array is inconsistent. ?

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

        The element x which is currently being added indicates the element was sold at this moment and the elements in the heap stores the element already sold out. It also means that at this point, the elements which we have on the showcase are x and all the elements in the heap. By what question says, x has to be the minimum as the customers purchases the minimum element on showcase, but in this case, there is some element in our heap which is less than x and the customer have purchased x instead of that minimum element in the heap. So, it is inconsistent.

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

      Thanks for the great explanation. In the problem it says, It's guaranteed that there are exactly n events of the first type, and each price from 1 to n occurs exactly once in the events of the second type. So, you don't have to check if no. of +'s == n

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

Div2 D problem can be solved in O(n) time using stacks. Code — https://codeforces.com/contest/1435/submission/96718560

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

Why my submission link1 getting TLE but when i changed vector size to (n*m + 5) it get accepted link2 ?

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

    This is a common mistake when there are multiple testcases. It may take 500*500*t if you create/initialize 500*500 arrays every time, and that's about $$$2.5 \times 10^{10}$$$. The statements said that "Sum of $$$nm$$$ over all test cases does not exceed $$$250000$$$" so the second submission could pass.

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

About Problem 2E/1C: I didn't like this problem at all. It was boring and a detail-finding kind of problem where you know right after reading the problem that you can get to the solution if you are not lazy enough.

about the $$$-1$$$ part, we can just see that since $$$a>bc$$$, for each spell, whether complete or not, contributes positively to the damage. Hence the damage can be arbitrarily large. No need to think about overlapping parts, as is done in the editorial.

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

Linear time solution of div1B:

Consider the queries backwards. Then — x actually means adding shuriken with value x to the showcase, and + means deleting some shuriken. So we can maintain the sorted stack of all shurikens at the moment. On + we will delete the minimum from the stack (it's easy to see that it's always the best option), i.e. top element, and add it to the answer array. On — x we will check that x is less then the value on top of the stack and add it. If we successfully looked through all the queries we will just print the reversed answer array, and otherwise there's no answer. My code 96667703

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

    I had a similar idea , which unfortunately didn't work. can you please explain what's the flaw with with the following logic.

    Initialise cnt to zero . While processing the queries backwards , if we see + we increment the cnt variable by 1. When we see — x , we push x in the stack if x is less than top element otherwise we can pop atmost cnt number of elements from top of the stack such that now either the stack is empty or top of stack is greater than x.while popping from the stack we decrease the cnt by 1.

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

There is something I can not understand in the proof of 1D.

Tutorial says "Let AB be a diameter of the tree, and the optimal answer be EF." But it seems that in the given tree, AB is not a diameter.

Did I understand what the tutorial wanted to express wrongly? Could anyone explain it for me? Thank you in advance!

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

    This is for the sake of brevity. You can see that the edge CB is a little bit longer than AC. Apparently that means that there are some nodes on a path between B and C

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

can someone explain to me whats wrong with my algorithm 96738918 in D2C? i know my idea is wrong,but im confused whats wrong with it

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

    The answer may not always be abs(b[n]-a[6]-b[1]+a[1]). An example:

    1 3 6 8 100 1000

    3

    1003 1250 1500

    According to your code, the answer must be 502, but the correct one is 398.

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

      thanks dude,but i still dun get the idea of the problem C,can u explain more??

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

Even though my rating dropped . I loved the problems and the NARUTO theme . Nice contest!!!

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

Can someone explain A?

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

    If have any query..please ask.

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

      Originally I thought this was meant to be solved with LCM and was having trouble. This approach is really easy to understand thnx!

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

Can someone please tell me why my solution is wrong for Div2. A... 96650687

I printed all 1's if the sum of all elements of original array is 0 and I got wrong answer on 10th Test.

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

    if the sum ever does happen to be 0, then you're printing 2 valid answers which is why you're getting WA. Just add a return statement.

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

Could anyone recommend similar problems to div2C&|D?

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

How to approach the problem E with ternary search( Proof of maximal value being a convex function) ??

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

Was div.2-D a standard problem? Everybody is saying that the problem is very easy but I could not come up with a simple idea for the problem. I was thinking of a heavy implementation solution.

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

    The idea of problem D:- 1) pair every "+" with below "-" using upper bound. 2) check the order of elements with given order using stack

    for better understanding, check out my code

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

I think there's also a O(n) solution for Div2 D using list and it's easier to explain.

We consider matching the '-' operations with '+' operations from "- 1" to "- n".

After we matched a '+' operation and a '-' operation, we remove them from the operation sequence.

So, when considering the operation "- x":

If the previous operation is "-", it's impossible to meet the requirements because we have already removed all the numerically smaller "-" operations.

Otherwise the previous operation is "+" and we can easily match this "-" operation with it.

This can be maintained with a list by recording the position of each "-" operation in the operation sequence.

My code

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

All problems(DIV2) are good and do not need a hard data structure. some observation and you can solve.

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

    Except the one about ramen

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

      I was talking about DIV2

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

        Oh i was doing the original Technocup and there we had that problem about ramen, so i thought it was in div2 too

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

Div2 D can be solved going through the reversed query with a set. Every time we meet a "+" we can just say that the woman takes the one with the least price back. So if set's size is 0 the answer is NO. Else erase that element and add to the answer. Else if we meet a "- x" then x must be the less then the least element in the set now. If not, the answer is NO. If yes, insert x. 40 lines of code.

p.s. reverse the answer in the end

96676641

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

Can anyone tell me why am i getting TLE in div2B? An n^2 solution should have been fine ,right? 96669009

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

    I think n^2 should be too slow (2,5e5)^2 is a lot

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

      Oh. Can you kindly explain your approach for B then?

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

        Oh i see the problem. Im sorry thought it was (nm)^2, but after seeing ur code i saw it's nm, which is ok. The problem must be creating a huge array vis, since all other things have a good time complexity.

        p.s. I got ur sol accepted with changing vis size to n * m + 1

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

          Thanks a bunch. It worked after using a map instead of vis array

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

can someone tell me why my code is giving wrong output?? my code is 96679812.. this is code for Div2C..

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

A simple solution to Div2 D using a stack and a priority queue : 96756883

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

I don't know why I TLE in B :(( somebody help me, please!!!!!!! MY SUBMISSION

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

Div 2 : Problem D

It seems hard to explain my idea clearly. I would add some test cases, which might be helpful to understand.

Case 1 : From test case 2 , at any moment, if the number of sold items "- x" is greater than the items (+) we already have, then the ans is "NO"

Case 2 : Checking The contiguous blocks of "- x" is in the ascending order or not. If the contiguous block of "- x" is not in the ascending order then the ans is "NO".

On this point my thinking was, if we have something like this, For n= 4 : (+) x1 (+) x2 (+) x3 (+) x4, where the particular item has been sold just after it has been placed in the showcase. Then for any sequence of xi, ans is possible.

Now extending the idea, for example n = 6 : (+) (+) (+) 4 5 6 (+) 1 (+) (+) 2 3. In this case one of the possible solutions could be (6) (5) (4) 4 5 6 (1) 1 (3) (2) 2 3.

Here I considered a case where for every block of sold items we have equal numbers of empty places. Items 4th, 5th, 6th are sold means those items have been placed earlier,and also he brought the items choosing the minimum once in each purchase. Hence, items 4th, 5th, 6th could be placed in any order.

Now think, if the sequence was (+) (+) (+) 5 4 6 (+) 1 (+) (+) 2 3. Then it means items 5th, 4th, 6th are sold, whereas he brought 5th item whereas item 4th was already there, which is not possible. Hence, the output would be "NO"

Case 3 : Now consider the case. For n = 6 : (+) (+) (+) (+) 3 4 6 (+) 1 2 (+) 5. Here for every block of sold items we do not have equal numbers of empty places : (4 empty place) 3 sold items (1 empty place) 2 sold items (1 empty place) 1 sold items

Then if we put the items like this (+) (6) (4) (3) 3 4 6 (1) 1 2 (5) 5. 2nd item still needs to be placed. The only remaining place is at the beginning. If we put 2nd item there, then the ans would be "NO"

However, similarly if the given sequence was, for n = 6 : (+) (+) (+) (+) 2 3 4 (+) 1 6 (+) 5. Then one possible solution could be (+) (4) (3) (2) 2 3 4 (1) 1 6 (5) 5 . Here we can easily put the 6th item at the beginning, which will maintain the condition.

I have used stack. For checking the case 3, I stored the sequence in a vector. My submission 96765725

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

https://codeforces.com/contest/1435/submission/96662042 can someone tell me what I am wrong?? I can't find anything wrong with my code. please...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the first matrix given gives you the column of the number and the second matrix gives you the row of that number

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

How to solve div2E with binary search?

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

I thought the title of Div2 E was dota2 reference.

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

https://codeforces.com/contest/1435/submission/96788248 What is wrong in my code for shurikens?

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

How could anyone in A saw the row of array like: -a2, a1, -a4, a3, ..., -an, an-1. I mean, no advices on that path weren't given, is anyone sorted out how this works?

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

    n is even, and you want to make two adjacent elements make a sum of 0.
    if you have the array a1, a2 — make the sum a1*(-a2) + a2*(a1) = 0.
    If you do it to every adjacent pair, the total sum will be 0.

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

      Yeah, I understand that I need sum = 0, but I hadn't sorted out how to achieve this at the competition, so that's quite bad. That's pretty hard for me to find easiest ways to solve a problem.

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

        Emmm. What you need to do is just practicing more and thinking more. I believe you can solve such problem quickly in a nearly future.

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

          Thanks. I hope, I will :)

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

can someone tell me why i am getting runtime error https://codeforces.com/contest/1435/submission/96803170

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

You can solve KOIREP from SPOJ if you have solved Div 2C/1A

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

Can someone explain me DIV2 E/DIV1 C. Not able to get the way written in the editorial. Can someone get me through that . Thanks in advance.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain the solution of the div1E?I'm totally confused with the conclusion “the outcome of the game is defined by the index of the last move and the last difference between the elements”and“ if we fix the last index and gradually decrease the last difference, the grundy value will not decrease. ”

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why we used set<pair<int,pair<int,int>>> in div2C why can't we just keep track of the value(0-5) in an array of n

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

Could anyone please tell me some other solutions (except two pointers) of the problem Perform Easily? There are so many problem tags for this problem, so I guess there will be some interesting solutions (such as binary search).

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

    I thought of a different approach and used lower bounds and upper bounds but it is failing at test case 9 can you tell me whats wrong with my code? you can go through this I posted this earlier Can Someone tell me why I my code fails at test case 9 96809688 I have used the approach that after sorting the notes the there cannot be a fret smaller than difference between first note and first string then I took two case 1. I found all the frets for every note which is just smaller or equal to the smallest fret. 2. I found all the frets for every note which is just larger or equal to the smallest fret. then I found the Min of differences obtained from these two.

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

      Sorry, I don't understand your approach. However, there is a set of small data that your code can't get the right answer, maybe you can try to discover your mistakes through it.

      Input

      1 1 1 96 99 100

      3

      101 146 175

      Output

      50

      Your answer

      74

      Good luck!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No this case will work but I get it why my code is not running for test case 9

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone tell me why I my code fails at test case 9 96809688 I have used the approach that after sorting the notes the there cannot be a fret smaller than difference between first note and first string then I took two case 1. I found all the frets for every note which is just smaller or equal to the smallest fret. 2. I found all the frets for every note which is just larger or equal to the smallest fret. then I found the Min of differences obtained from these two.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

5 minutes left time to be ready : )

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Round!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

O(N) is possible for 1413D — Shurikens My solution

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thx for this round!