isaf27's blog

By isaf27, 5 months ago, translation, In English,
Tutorial is loading...

Jury solution: 54047380

Tutorial is loading...
Jury solution: 54047416
Tutorial is loading...
Jury solution: 54047456
Tutorial is loading...
Jury solution: 54047487
Tutorial is loading...
Jury solution: 54047513
Tutorial is loading...
Jury solution: 54047561
Tutorial is loading...
Jury solution: 54047626
Tutorial is loading...
Jury solution: 54047665
 
 
 
 
  • Vote: I like it
  • +62
  • Vote: I do not like it

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

Hard B, trivial C and D, cool E. And I completely understand that it's easy to misjudge the difficulty of B.

I don't like limits in F and I want setters to take some things into consideration in the future. Here, the jury solution (attached in the editorial) takes 40% of TL what is quite tight, especially considering the fact that it does all modulo efficiently — avoiding the % operator if possible, doing if(x >= MOD) x -= MOD instead. You should do that in brute force solutions and make sure they still don't pass, but the author solution shouldn't be written very efficiently. Remember that participants won't necessarily implement everything in the same way. Do you really want to penalize them for writing a code that is twice slower? And let's remember about a bit slower Java, though maybe it wasn't an issue here — because modulo was the heaviest operation. TL 8-10s and ML 512MB look much better to me (the author solution takes 118MB and it would barely pass after replacing ints with long longs).

Tight limits can be forced by a dangerously fast brute force and maybe everything was chosen as good as possible in this problem, I don't know. Even in that case, I think that my post still can be of use for future setters.

Remember this: limits should be chosen in such a way that naive solutions don't pass. If this condition is satisfied, it's great to make TL to be much much more than twice the running time of your solution.

And limits in C were too tight as well. Reading $$$500\,000$$$ numbers and possibly doing something with a set or a segment tree? That takes some time, especially in slower languages. It's good if easy problems are solvable with Python. Just make TL to be 2s or 3s. Why not?

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

    I don't agree that B was difficult. If you implement brute force solution which just runs through all possible strings of length n and play around with it for a while you can clearly see the pattern.

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

    In problem C, segment tree/set takes $$$\mathcal{O}(n\log n)$$$ time, and author's solution is $$$\mathcal{O}(n)$$$, so such a tight TL could be the result of one of following considerations: 1) the author didn't know about $$$\mathcal{O}(n\log n)$$$, so he didn't see any difference between $$$500\,000$$$ and $$$200\,000$$$ and chose arbitrarily, or he tried to avoid participants sending unoptimal unpredicted solutions; 2) the author knew about $$$\mathcal{O}(n\log n)$$$ solutions and didn't want them to pass. Actually, in this case he didn't perform the clipping perfectly as the segment tree approach turned out to be productive for some participants, but my segtree failed the system testing (though changing the vectors to arrays and switching compiler from С++17 to C++14 let me gain an ok in upsolving in 998ms).

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

      I don't know about your claim — I implemented C in $$$O(nlogn)$$$ using priority queue, and I got AC in 327 ms.

      Code is here

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

    C can be solved in O(n)

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

    I'm still beginner, but I think that any Div1 participant must be able to optimize his code to the fullest

    PS: In fact I love down-votes

»
5 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Amazing Problemset <3 Fast Editorials <3

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

can anyone explain me div 1 C with more detail how to solve this with set/segment tree.

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

When will the editorials of rest of the problems be translated to english?

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

    BTW, is it only me who is thinking that after AtCoder in japanese and Codeforces in Russian, Codechef will start publishing editorials in Hindi and will refuse to translate them?

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

Please translate

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

UPDATE: Answered here

In Div2E/Div1C.
Does anybody know why this 54049263 gives MLE? When I change stack to set I get AC in this 54047364

My Approach: Construct a directed graph where edge (u,v) means a[u] < a[v] and then do topological sort on that graph.

The way I construct it is if nxt[i] = j that means there is an edge(i, j), also there is an edge between all elements [i+1, j-1] and i since all of them must be less than i. I only keep track of the least previous element.

Here's an example where ix, jx means nxt[ix] = jx:
i1 i2 i3 ... j3 j2 j1. Edges are (i1, j1), (i2, j2), (i3, j3), (i2, i1), (i3, i2). I don't add (i3, i1) since it's redundant.
In a case like i1 .. i2 .. j1 .. j2 In the MLE submission I exit immediately and say that it's impossible. In the AC submission with set I let the topological sort handle it.

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

isaf27 why no english editorial ?

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

    I'm sorry, before the round I've written only Russian editorial. Now I should translate it, but I have a very hard time at university. Before the end of the week, I will finish. You will see the update in "Recent actions" section.

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

      First of all, thank you for having prepared a CF round. It helps the community and it requires a lot of work. ... But, why couldn't you write the editorial in English from the beginning? In that case you wouldn't have to spend extra time translating.

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

        Yes, I wanted to do this. But I started working on test cases shortly before the round and was busy doing test cases. Next time I will definitely begin from doing statements and editorials because it is usually hardest work for me :)

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

Where could I find the solutions in English pls

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

English solutions please!!

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

Can anyone help, what is 'l' in the explanation of D above?

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

    It is from the statements — any position of the string t occurrence.

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

Now editorials in English are available, sorry for waiting. If something isn't clear you can ask in comments.

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

in problem c (The Party And The Sweets) in test case 1 what is wrong in this ans: b1- 1 1
b2- 3 4
b3- 1 1
ans=11 ??

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

    It was really the most popular question during the round :) Check the formal explanation of the problem, a minimal number in the second row is wrong.

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

    In the problem statement it has been stated that 'For all 1≤i≤n the minimal number of sweets, which i-th boy presented to some girl is equal to b[i] ', which means that b[2] has to present a girl with 2 sweets, therefore b[2] can either be 2 4 or 3 2 and not 3 4, and further on as 'for all 1≤j≤m the maximal number of sweets, which j-th girl received from some boy is equal to g[j] ' therefore if we choose 3-g[1] 2-g[2] for b[2] therefore some other boy (b[1], b[3]) has to give the other girl (g[2]) 4 sweets (which is the maximum she received from some boy)

    Thus the solution can be,

    b[1]- 1 4 b[2]- 3 2 b[3]- 1 1

    ans=12

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

Div2D: Editorial is not helpful at all.
You explained the pattern to generate the answers.
But how to come up with that kind of pattern in first place.
Please share some ideas in what direction to think for problem like that to come up with patterns like that. Stating formula and why formula works is not helpful at all.

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

    To solve this problem it's better to solve some cases, for example:

    1. k = n, it is an obvious case
    2. k = n — 2, I think it isn't hard to guess, that 0101010101 is the correct example
    3. k = n — 4. This is the hardest case. But if you will think for some time, checking some examples, you will guess, that periodic string is correct

    And after the last case, it's easy to guess the pattern. I think it is a good way to solve this problem.

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

About Div2-D, condition on the assumption of periodic a and minimum unique length k, I got

$$$ a >= (n - k + 1) / 2 $$$

doesn't it means the period not unique but have a lower bound? But I failed on program checking.

And when the parity of n and k not same, even the lower bound of a is wrong. Why is that? Really doubtful.

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

    Hi, I guess, ( n%2 = k%2 ) ensures about parity being same. Unless you are talking about the bonus question provided at the end of solution.

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

      Actually I have doubts to both problem. In the original problem I cannot justify the unique of a, else on bonus I completely have no idea... Anyway, Thanks for your reply.

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

Can someone please elaborate on the solution for 1159B (Expansion coefficient of the array)? Thanks:)

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

I binary searched the answer. Link to my answer

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

    Thank you for your solution. I understand the binary search procedure, but could you elaborate on the math logic explained in the editorial that you used in your code?

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

      Actually, even I didn't understood it. I rather used some diffrent way.

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

So, the maximum possible value of k is equal to the minimum of min(ai,aj)/|i−j| for all i<j. Let's note, that min(ai,aj)/|i−j|=min(ai/|i−j|,aj/|i−j|). So, we need to take a minimum of ai/|i−j| for all i≠j. If we will fix i the minimum value for all j is equal to ai/max(i−1,n−i) and it is reached at the maximum denominator value, because ai≥0.

Can someone please explain the last line of the paragraph? It seems to me that we need to look up the minimum value of input and then divide it by some index. I'm not getting the formula like, why we need to take max(i−1,n−i) as the denominator.

EDIT: It's for problem B. Expansion coefficient of the array.

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

In problem C, I think I solved it quite similar way as written above, but I keep getting wrong answer on testcase #7. Can somebody help me to find why? Code is written in Python.

code: n, m = map(int,input().split())

b = sorted(list(map(int,input().split())),reverse=True) g = sorted(list(map(int,input().split())),reverse=True)

if g[-1] < b[0]: print(-1) exit(0)

total = sum(b) *m

g_idx = 0 b_idx = 0 while g_idx < m: temp = 0 while g_idx < m and temp < m-1: if g[g_idx] == b[b_idx]: g_idx+=1 continue total += (g[g_idx] — b[b_idx]) g_idx+=1 temp+=1 b_idx +=1

print(total)