antontrygubO_o's blog

By antontrygubO_o, 5 weeks ago, In English

I hope you enjoyed the round.

While problem D1B was good for balance in Div1, it was too hard for balance in Div2. I apologize for this.

Problem D1B = D2D is by dario2994. Other problems are mine.

D2A
D2B
D2C/D1A
D2D/D1B
D2E/D1C
D2F/D1D1
D1D2
D1E
 
 
 
 
  • Vote: I like it
  • +250
  • Vote: I do not like it

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

Divison 1

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

    I can't find the test case.I got wa on 177th token of 2nd test.Please tell me the test case,this is my submission id:158470917

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

      Consider this testcase in Ticket 7727.

      What's special about this testcase? All numbers are in $$$[0, 3]$$$, and $$$sum(array) = Length(arr)$$$. Hence, if you partition the array at $$$1$$$, the AM would be $$$49/49$$$, which would convert all numbers to 1. Hence, the answer is YES, but your code prints NO.

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

        Thankyou so much,can you please tell me what's wrong with my code,as far as i see the logic seems to correct as well.But somehow the value stored in my 'ms' variable doesn't end up in it,and it doesn't get checked at all ,not until i try to print it externally.

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

    It says "Python supported has been temporarily disabled..." for Div2 A

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

      It's because I haven't added Python support yet. It's enabled in the development environment, but not in production.

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

    I cannot find the test case responsible for my WA.https://codeforces.com/contest/1685/submission/158616772 is the link to my submission.

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

Very good problems! I like this types problems!

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

I just realized on reading this that reversing a substring in D1C means actually reversing order of the substring, not flipping every bracket in the substring :(

Would have been nice to have a sample/statement exactly capturing that, though (I think none of the samples differentiate between these two interpretations?)

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

    I made the same mistake as well. I wrote and submitted a solution using stack that solves the flip problem (158461024). Not sure about correctness though.

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

    Silly in retrospect, but I also made the same mistake.

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

    the same as me

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

    I'm curious to know the soln to the flipping-version.

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

.

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

I personally like adhoc problems, and do best when the problems require less topic-specific knowledge, less coding, and more thinking.

Not everyone agrees, but I loved Div 2D.

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

    who tf asked?

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

      If every comment was something somebody asked for, codeforces would be a silent place, my silly friend.

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

      If you can't say something good, don't speak at all. -Eminem

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

I didn't like the problem names. They were boring.

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

How many constructives?

"Yes"

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

How did you write the checker in 1685E - The Ultimate LIS Problem?

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

    If exactly one of jury and participant found such k after some update, check if that k works, and return with WA or fail.

    Otherwise, look at the instances where ks found by jury and participant were different. Briefly, check random ~1000 of them.

    This approach doesn't guarantee that submission will give WA even if its output is incorrect, so we disabled hacks.

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

For 1686A - Everything Everywhere All But One, suppose the number to be excluded is at index $$$r$$$, we require:

$$$\dfrac{\sum_{i \neq r} a[i]}{n-1} = a[r]$$$
$$$\implies \sum_{i \neq r} a[i] = a[r] \cdot (n-1) $$$
$$$\implies \sum_{i} a[i] = a[r] \cdot n $$$

Therefore, the required condition becomes:

$$$\dfrac{\sum_{i} a[i]}{n} = a[r]$$$

Which is the same as asking the question

$$$\text{Is the average of the list present in it?}$$$

Nothing new here i suppose, but I found this easier to code than what's in the editorial.

Code

Complete code: 158477863

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

    This is how I solved it and I think this approach is much more elegant!

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

Problem D can be generalized further: given $$$n$$$ pairs of (arbitrary) integers $$$(a_i, b_i)$$$, find the (lexicographically minimal) permutation $$$q_i$$$ which minimizes $$$\sum_{cyc} \lvert a_{q_i} - b_{q_{i+1}}\rvert$$$. In this phrasing, this problem is quite similar to IOI 2016 railroad.

Consider the graph with 1 vertex per integer. Let's view the pair $$$(a_i, b_i)$$$ as a directed edge from $$$a_i$$$ to $$$b_i$$$. Now, we want to add the minimum number of directed edges $$$i \to i+1$$$ or $$$i+1 \to i$$$ so that we can form a valid Eulerian tour through all edges. To do this, we should first make sure that the number of edges crossing between each integer in each direction is balanced (in problem D, this is always the case, since all given vertices have indegree and outdegree equal to $$$1$$$). Then, we need to add the minimum number of pairs of edges $$$i \to i+1$$$ and $$$i+1 \to i$$$ to make the graph connected, which reduces to minimum spanning tree.

We can still find the lexicographically minimal permutation in $$$O(n^3)$$$ time by trying to add each possible next edge, and checking if it's still possible to finish the Euler tour, which turns out to only require checking some connectivity conditions.

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

    Good job!

    I also remembered this problem, but decided not to open the editorial (which was a mistake). I think this reasoning is much easier to understand than the one from this blog.

    To clarify, we have directed edges $$$(b_i, a_i)$$$ and want to construct edges $$$(a_i, b_{i+1})$$$ for some permutation to minimize length of euler tour. Turns out, for me it was hard to understand how to fulfill the condition that each node must have one ingoing and one outgoing edge (which is kind of necessary to construct a solution). The proof is: construct an euler tour (it is necessary to have balances zero and graph connected, and it is also sufficient — even with big edges $$$(b_i, a_i)$$$ that are actually not many small ones, because indegree is still equals to outdegree for nodes in between segment $$$(b_i, a_i)$$$), write down all edges $$$(b_i, a_i)$$$ in order of euler tour, now part of euler tour between $$$a_i$$$ and $$$b_{i+1}$$$ is some path in line graph, but since we minimize the length (which is key) this path must be straight segment, so its actually $$$|a_i - b_{i+1}|$$$ which is exactly what we need.

    Its a bit different from the IOI problem because we were allowed to travel back and forth, so the length might not be $$$|a_i - b_{i+1}|$$$, but again, because of minimization its always the case.

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

    Could you please explain a reduction from original problem to "we want to add the minimum number of directed edges so that we can form a valid Eulerian tour through all edges." in more details? The most unclear part is how to calculate the weight of the $$$q$$$ from the original problem using our Eulerian tour.

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

      We can think of $$$\lvert b_{q_i} - a_{q_{i+1}} \rvert$$$ as the number of new $$$x \leftrightarrow x+1$$$ edges we need to move from the tail of edge $$$q_i$$$ to the head of edge $$$q_{i+1}$$$. Thus, a particular set of extra edges and an Euler tour corresponds to the permutation $$$q$$$ of the original edges in the order visited, and the weight is the number of extra edges.

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

Why I couldn't see editorial in div2's Contest materials? plz fix it :)

upd:now I can see it, thanks for fixing it!

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

Best contest I've ever wrote. Really nice problems!

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

I hate linguistics now.

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

For some reason, understanding the explanations in this editorial itself seems difficult, for me :(

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

Really wondering how the top 100 come up with

Key observation: It's always possible to get a balanced sequence in at most 2 operations.

in contests in a couple of minutes...

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

    It is pretty well-known problem, so we can easily get how to make it under 3 reverses. Then we just have to think if we are able to make it in less reverses. D1C is actually a good problem, unfortunately I didn't manage to solve it during contest because of D1B...

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

      What well-known problem?

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

      Perhaps I find it. Is it the cyclic shift in editorial of E?

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

"wrong answer Jury found the answer but participant didn't (test case 1435)" this verdict on 3rd problem test case 2.

Where did I go wrong? Submission--> 158448669

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

    I got the following test case using CF Stress.

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

      Thanks!

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

      how to check this?? because i want to check test case 21950

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

        You probably cannot check this large numbered test case on Codeforces. If you want to find out some other test case where your solution is failing, you can visit CF Stress and stress test your solution there.

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

Implementation ?

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

Awesome contest.Thanks antontrygubO_o

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

How can one notice that the answer is at most 2 in D2E/D1C? I wouldn't have ever guessed that if I didn't look at the solution. How to come up with this myself?

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

    Personally I didn't come up with this during the contest (I solved this problem in a different way). But I think this is how you could come up with it: You see the opening brackets as +1 en closing as -1 and look at the prefix sum. This is the first thing you should always think about with these kind of bracket problems. Draw a few graphs of these prefix sums and see what happens if you reverse a sub string. The first thing you can notice is that it rotates a part of the prefix sum graph by 180 degrees. The second thing you can notice is that if the part of the sub string you reverse starts with a prefix of 0 and ends with a prefix of X, then if there is no prefix greater then X this part of the sub string will have a prefix where every value is greater then 0. (Because of the rotating by 180 degrees) Because of this you can always find an answer of 2, by reversing everything before the greatest prefix sum, and everything after that.

    For my solution I made all of these insights, except the last one that the answer is at most 2.

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

    The easiest (but boring) way is to write a brute force.

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

Hey can anyone tell me what is wrong with my code, it is giving wrong ans on pretest 2 sort(all(arr)); vi a; fori(i, 0, n / 2) { a.pb(arr[i]); } vi b; fori(i, n / 2, n) { b.pb(arr[i]); } if ((n % 2) == 0) { fori(i, 0, n / 2) { if (!i) { if (a[i] >= b[i]) { noo; return; } } if ((a[i] >= b[i]) || (a[i] >= b[i — 1])) { noo; return; } } yess; fori(i, 0, n / 2) { cout << a[i] << " " << b[i] << " "; } nl; return; } noo;

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

Problem (1686A — Everything Everywhere All But One) can be solved simply by computing the average of that array as avg (type: double), then searching for avg in the array (normal search: O(n/2), binary search: (O(log2(n)), although the normal search is enough to accept. Isn't it simpler than the tutorial?

P/S: sorry for my bad English, I translated it myself.

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

    Two points I would like to highlight:

    1. You could use data type int instead of double. First check if the remainder of the division is NOT 0. In that case, the answer is NO. If the remainder is 0, compute the integral quotient and search for it in the array.

    2. The binary search approach would be more expensive than a linear scan as it would require an O(nLogn) sort prior to the search.

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

      Thank you for your reply, I personally found it really useful for me. I totally agree with you the second point. About the first one, I tried use int datatype but failed (because it rounded avg), then I used double I got accepted.

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

        Yes, if you directly store avg in an int variable, you would have a problem with rounding off. That is why I suggested to first check if the sum is divisible by n. If it is not divisible, the answer to that test case would be NO directly. If it is divisible, then the quotient is an integer anyway, so you wouldn't face any rounding errors. Here is my implementation for more clarity: 158422758

        UPD: Added a link to my implementation

        Hope that helps :)

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

          Wow thanks a lot for your comment! It actually better than mine. I will remember it! Thank you again :]

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

    Can you explain why this approach works? I'm unable to figure out the maths behind it. I mean, why it works for second or third iteration of the operation?

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

      When the array equal, there will be at least one element left unchanged, and the average of the array never change so we have 2 things that never change, then we can use it to solve the problem. P/S: sorry if you can't understand the above, but I can't make it more clear for you as English is not my native language.

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

Can anyone please help me on how to solve problem D, in Div2?

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

    Actually D is easier than it looks.

    If you are confused on proof part, here is an intuition. If you want to take BA from Type 2, it'll be better to take it from larger sizes as 1 will be wasted everytime you take from any. So while taking AB from type 2, take from smallest everytime. That's exactly what he is proving.

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

I am going through question Div 2 question D and I am literally so confused. I used the stress test and it said: 2 2 5 4 BABABABABAAABBABAABBAB is YES while my code gives false I tried grouping it by hand but I literally can't find how this is true.

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

    okay sike I literally figured it out lmao it is (BA)(BA)B(AB)(AB)AA(AB)(BA)(BA)(AB)B(AB)

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

Can someone help me with Div2 C

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

Thanks for the contest, I enjoyed it a lot! Why in the "Linguistics" task we don't check the same initial condition for the letter "B"? Moreover, in the editorial it is said we are sure that the number of characters A and B is correct because of the initial check. I imagine a=1, b=0, c=1, d=1, and a string AABBABBBB. a + c + d = 3, it passes the initial check. But we see we don't have enough B's.

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

    If the count of A is correct then count of B will always be correct because $$$a+b+2*c+2*d = len(s).$$$
    In the example you mentioned, the above condition is not satisfied, so it's not a valid test case.

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

      ooook, that's, actually, given to us as a condition. Thanks a lot!

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

would you please tell me about the test case 1435 in test case 2 of problem C from div2? :(

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

    Wait, mine 1432 is wrong. And I compared my solution to the solutions accepted. It kinda looks similar.

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

    6

    2 2 1 1 0 0

    6

    3 2 1 1 0 0

    Here mate.

    1435 and next one

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

    Bro same issue I'm facing.....my 1435th token in test case 2 is giving WA. If u get it please tell me too

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

My solution for problem D(Linguistics) and an attempt to explain it.

Approach
My Submission

This is my first time explaining a solution in writing on Codeforces. Suggestions are welcome and please point out the mistakes.

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

    The number of values from type I will always be zero right as there are no A's

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

      No, there will be such chains, these are the indexes which are already disjoint that is they have no neighbouring A.

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

**I can't find the test case. I got WA on the 1435th token of the 2nd test. Please tell me the test case,this is my submission id:158613119 **

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

The round shows that it has become unrated. Is it true?

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

For anyone trying to upsolve D1D2: In the editorial for problem D1D2 it gives a list of criteria that is sufficient, but when I tried implementing it I got wrong answer. I think they forgot one constraint: "There is no $$$x$$$ such that there is a left segment $$$i$$$ with $$$l_i < x < r_i$$$ and a right segment $$$i$$$ with $$$l_i < x < r_i$$$.

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

Can anyone tell me that in the proof part of div2D,what's the meaning of "+" and "$$$\sum$$$" in

$$$\sum_{u\in U}f(u) + \sum_{v\in V}f_{AB}(v) + \sum_{w\in W}f_{BA}(w)$$$

,are they equivalent to $$$\cup$$$ here?

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

    I think, it means following:
    Suppose we have two multisets of pairs of numbers A and B. For exapmle, A = {(0, 1), (0, 1)} and B = {(5, 2), (0, 7), (3, 11)}. A ∪ B = {(0, 1), (0, 1), (5, 2), (0, 7), (3, 11)} (size of this multiset is size(A) + size(B)). But A + B is a multiset consisting of all such pairs (x, y) that there exist a pair (x_a, y_a) ∈ A, pair (x_b, y_b) ∈ B and x_a + x_b = x, y_a + y_b = y (i.e. (x_a, y_a) + (x_b, y_b) = (x, y)). In my example A + B = {(5, 3), (0, 8), (3, 12), (5, 3), (0, 8), (3, 12)} (size of this multiset is size(A) * size(B)).

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

      Thanks for reply.You are right,it means that (c,d) must be in the multiset of all possible combinations of valid pairs from three types of strings.

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

Div2, Problem A

https://codeforces.com/contest/1686/submission/158501965

I got WA in the 2nd test. Can someone kindly tell/give an array where my code won't work?

My logic was, for a sorted array the mean value will be at the center. So I considered the middle value and checked if the (sum-mid value)/(n-1) = mid value. If not, then answer is No, else Yes.

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

    n=5, a=[1,1,1,2,5]

    It should answer yes, because 2 is the array mean and it is present in the array, but your code will answer no because 2 is not in the middle.

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

    You mixed up mean and median. In this problem mean is the average of some values, not the middle element.

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

      Yes my logic was not correct. I had to check all the elements. Thanks.

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

For Problem C(DIV-2) , check for this test case , 1 2 3 3 5 6 .

you will get the answer. Thank you!

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Sounds crazy, problem F in div.2 we can solve it in $$$\mathcal{O}(n\log n)$$$ just like the editorial. But the limit of $$$n$$$ is $$$\sum n\leq400$$$. It's really crazy!

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

I'm getting Time limit exceeded error on test 2 of Circular local minimax(D2C) problem. Can anyone help me how should i reduce that. I'm typing in java. import java.util.*; import java.io.*; public class Minimax { int[] circ(int x,List ary) { int i,j; int p,c=0; int a[]=new int[x]; int b[]=new int[x]; int z[]={0,0}; for(i=0;i<x;i++) a[i]=ary.get(i); if(x%2==1) return z; else { Arrays.sort(a); for(i=0;i<x/2;i++) { b[2*i]=a[i]; b[2*i+1]=a[i+x/2]; } if(a[x/2]==a[x/2 — 1]) { for(i=0;i<x;i++) if(a[x/2]==a[i]) c++; if(c>=x/2) return z; else return b; } else return b; } }

public static void main(String args[])throws IOException{
    Scanner sc=new Scanner(System.in);
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   long n=Long.parseLong(br.readLine());
   int i,j,x,y,z;
   List<int[]> list;
   List<Integer> ary;
   list=new ArrayList<int[]>();
   ary=new ArrayList<Integer>();
   StringTokenizer st;
   Minimax a=new Minimax();
   for(i=0;i<n;i++)
   {
       y=Integer.parseInt(br.readLine());
       st=new StringTokenizer(br.readLine());
       for(j=0;j<y;j++)
       {z=Integer.parseInt(st.nextToken());
       ary.add(j,z);}
       list.add(a.circ(y,ary));
   }
   for(i=0;i<n;i++)
   {
       int arr[]=list.get(i);
       x=arr.length;
        if(arr[1]==0)
        System.out.print(" NO");
        else
        {
            System.out.println(" YES");
            for(j=0;j<x;j++)
            System.out.print(" "+arr[j]);
        }
        System.out.println();
   }
}

}

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

159346667 I am getting an error in the 1435 test case. I'm not able to figure out whats wrongs. would appreciate if someone could help. [problem:D1A]

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

    Sure, take a look at Ticket 10244 for a counter example.

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

    your approach is wrong ,the correct array construction is like that:
    if sorted a=[1,2,3,4,5,6] then split a into two halves like that a1=[1,2,3] and a2=[4,5,6] .
    then fill the circle alternatively between a1 and a2 starting from a1 ,so answer = [1,4,2,5,3,6].

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

In d1D2 I think a condition is left out by the editorial: for $$$1\le i\le n$$$, if $$$i$$$ is covered by two segments (we know they are a left segment and a right segment), it's an endpoint of one of the two segments. This guarantees $$$i$$$ is in the correct cycle in graph $$$G$$$.

For example let's consider $$$p=[1,4,3,6,5,2]$$$, and $$$[1,3,5]$$$ as a prefix of $$$q$$$. We have a left segment $$$[1,3]$$$ and a right segment $$$[1,3]$$$. $$$[1,3,5]$$$ is a possible prefix for an optimal $$$q$$$ according to the five conditions in the editorial, but in fact we see $$$1$$$ and $$$3$$$ make up a cycle without $$$2$$$. By the way, the answer of $$$p=[1,4,3,6,5,2]$$$ is $$$q=[1,3,6,4,5,2]$$$.

The proof that the six conditions are enough is left to the reader as an exercise. x

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

This is my submission id 160783559 for problem number 3 : Circular Local MiniMax.please show me the wrong test case(test case 2 : 1435th).

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

    int32_t main(){ fast

    int t=1; cin>>t; while(t--){ll i,j,k=0,s,a,b,c,n,x,y,z; vectorv; cin>>n; ll arr[n+1]; fl(i,n)cin>>arr[i]; sort(arr,arr+n); if(n%2!=0||arr[(n)/2-1]>=arr[(n)/2])cout<<"NO"<<endl; else { cout<<"YES"<<endl; for(i=0;i<n/2;i++){ cout<<arr[i]<<" "<<arr[n/2+i]<<" ";

    } cout<<endl;

    }

    } return 0; }

»
5 days ago, # |
  Vote: I like it +10 Vote: I do not like it

For the D1B proof, shouldn't the $$$k$$$ in $$$(c, d) \in f\Bigg(\sum_{u\in U} k + \sum_{v' '\in V\setminus V'} (v' ' - 1) + \sum_{w' '\in W\setminus W'} (w' ' -1)\Bigg) + \bigg(\sum_{v'\in V'} v', 0\bigg) + \bigg(0, \sum_{w'\in W'} w'\bigg)$$$ be $$$u$$$?

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

    I'm also a bit confused on the function $$$f$$$ used in that proof. In the three subcases, you define the input to $$$f(k)$$$ as $$$\lfloor \frac{|t|}{2} \rfloor$$$. (ex. $$$|t|=2k+1$$$ for case 1) However, in the equation $$$(c, d) \in \sum_{u\in U} f(u) + \sum_{v\in V} f_{AB}(v) + \sum_{w\in W} f_{BA}(w)$$$ and subsequent lines, the entire length of each string is plugged into $$$f$$$. As defined, $$$U$$$, $$$V$$$, and $$$W$$$ are "the multisets of lengths of strings of the first, second and third type respectively."

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

      @dario2994 I guess

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

        Fixed the typo "$$$k$$$ instead of $$$u$$$" in two places. Thank you for pointing it out.

        You have misunderstood the definition of the function $$$f$$$. $$$f(k)$$$ is not a number, it is a set of pairs (as defined in the editorial).

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

          Thanks for replying! Just to clarify, I wasn't asking about $$$f(k)$$$, but rather about $$$k$$$ itself. Based on your initial definitions of $$$f$$$, shouldn't $$$(c, d) \in \sum_{u\in U} f(u) + \sum_{v\in V} f_{AB}(v) + \sum_{w\in W} f_{BA}(w)$$$ be turned into $$$(c, d) \in \sum_{u\in U} f(\frac{u-1}{2}) + \sum_{v\in V} f_{AB}(\frac{v}{2}) + \sum_{w\in W} f_{BA}(\frac{w}{2})$$$?

          Sorry if I wasn't clear the first time.

          Also, your fixes aren't showing up in the above editorial for some reason...

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

            You are totally right, my mistake. Now it should be fixed (changed the definition of the sets $$$U, V, W$$$).

            Sooner or later my fixes should be propagated to this post. If it does not happen in a couple of days, I will try to fix it.