Pyqe's blog

By Pyqe, history, 3 months ago, In English

1725A. Accumulation of Dominoes

Author: Pyqe
Developer: nandonathaniel
Editorialist: Pyqe

Tutorial

1725B. Basketball Together

Author: FerdiHS
Developer: muhammadhasan01
Editorialist: Pyqe

Tutorial

1725C. Circular Mirror

Author: Pyqe
Developer: steven.novaryo
Editorialist: steven.novaryo

Tutorial

1725D. Deducing Sortability

Author: Pyqe
Developer: TakeMe, Pyqe
Editorialist: Pyqe

Tutorial

1725E. Electrical Efficiency

Author: steven.novaryo
Developer: steven.novaryo
Editorialist: rama_pang

Tutorial

1725F. Field Photography

Author: Pyqe
Developer: Pyqe
Editorialist: Pyqe

Tutorial

1725G. Garage

Author: Nyse
Developer: Nyse
Editorialist: Pyqe

Tutorial

1725H. Hot Black Hot White

Author: Pyqe
Developer: steven.novaryo
Editorialist: steven.novaryo

Tutorial

1725I. Imitating the Key Tree

Author: Pyqe
Developer: Pyqe
Editorialist: Pyqe

Tutorial

1725J. Journey

Author: gansus
Developer: gansus, steven.novaryo
Editorialist: rama_pang

Tutorial

1725K. Kingdom of Criticism

Author: Pyqe
Developer: Pyqe
Editorialist: rama_pang

Tutorial

1725L. Lemper Cooking Competition

Author: Pyqe
Developer: steven.novaryo
Editorialist: rama_pang

Tutorial

1725M. Moving Both Hands

Author: Pyqe
Developer: Pyqe
Editorialist: rama_pang

Tutorial
 
 
 
 
  • Vote: I like it
  • +143
  • Vote: I do not like it

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

Fast tutorial. Thanks. Btw there is two pointers solution in B. Adding two pointers tag would be great I guess.

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

How can you get 4 + (n * 4 — 3) / 3 just by 4 + 4a?

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

i did'nt got solution for problem m anyone pls help

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

    Run shortest path algorithm.

    Change the direction of all edges.

    Run shortest path algorithm.

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

      more detailed? pls

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

        You wanna find a point x that has min minway(1, x) + minway(p, x). Also, we change the direction of all edges, so now, minway(1, x) + minway(p, x) = minway(1, x) + minway(x, p'), where p' is a new point for p, that shows, that p' is p in graph with reversed edges. We can see, that every point on the shortest way from 1 to p' has min sum of that 2 ways.

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

          I don't know where my code is wrong. Can you help me find out the details? thank you 171057638

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

For E, what's the intended way to build the auxiliary tree? We used small to large merging but that was O(n*log(n)*log(A)*map) which seems sus

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

    It is actually possible to build all sparse trees simultaneously using small-to-large, but the time complexity is worse. The intended solution uses an algorithm that runs in $$$O(|S| \log N)$$$ for each set $$$S$$$. The algorithm is as follows:

    1. Sort the vertices in $$$S$$$ based on their euler tour traversal order.
    2. All extra vertices in the sparse tree can found as the $$$\text{LCA}$$$ of every pair of vertices in $$$S$$$ that are adjacent in the sorted order.
    3. Once all required vertices are found, we can find the edges by iterating the vertices (including the extra ones) in euler tour traversal order and maintaining a stack.

    You can optimise it further to make the total time complexity $$$O(N(\log N + \log \max(A)))$$$. But the time limit is not that tight that even the small-to-large solution is able to pass.

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

      Ah thanks, that's really cool. Haven't really seen many problems with this "auxiliary tree" idea, so its nice to learn good techniques for it.

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

On the third task O() calculates in wrong way, min(Cntpair, m) = O(n), so O(n logn), or wthether we check case, where min(CntPair, m) = m, so in that way it'll be better if we say that it's O((n + min(n, m)) * logN) or something like that

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

L had weak testcases, we submitted L very late and only realized after the contest we forgot to check whether every element of the prefix sum was non negative and it passed

the submission 170883681

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

how M?

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

Problem: 1725B - Basketball Together

Solution: 170864702

In this block of code:

int Temp = a[i];
while(Temp <= D)
{
    Temp += a[i];
}

when I set n = 1, D = 10^9, and a[i] = 1; in theory it should run in 10^9 steps, which will give a TLE verdict. But when I use "Custom Invocation" to test it, I found that it only ran in 500ms, which is way below the time limit. Why did it happen? Is it because of the codeforces judging machines, or is there something that I'm missing?

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

    It probably just runs that fast. The hot path only includes an add, a compare, and a conditional jump, which is < 3 cycles with branch prediction. Computers run at a few GHZ, so 500ms sounds right.

    The $$$10^8$$$ things/second heuristic is just a heuristic for usualish groups of operations, you can do better if u have a fast loop body (especially if the compiler avx-ifies, which might be happening here).

    To see exactly what is happening u can try putting it in https://godbolt.org/ with the correct compiler version/flags.

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

Our team enjoy solving this problemset. Especially for Problem L. We didn't think it could be done using prefix sum. Very nice problem

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

why 1 and 4 cannot be expressed as $$$(b^2−a^2)$$$

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

    we can write (b^2-a^2) as(b-a)*(b+a) // proof for 1 can not be expressed in terms of b^2-a^2 so the min positive value of a we can take is 1 and for b its 2 as (b>a) as stated in the problem so, (b-a)=1; (b+a)=3; and their multiplication would give us 3 as the min value which can be expressed in terms of b^2-a^2; and one more conclusion can be drawn is that after three all odd numbers can be expressed in the form of b^2-a^2 (because we can express every odd number (lets say a)as 1*a; and a can always be represented as a sum of 2 consecutive numbers which are always odd **** lest take a=4 ,b=5; b-a=1; b+a=9; 9*1=9; that is odd)

    // proof for 4 cannot be expressed in terms of b^2-a^2 to make equation even we have to make (b-a) even first so in order to make that even min value of a we can take is 1 and for b is 3 so, (b-a)=2; (b+a)=4; and their multiplication will give us 8 that is the minimum even value we can achieve and from here we can draw one more conclusion that all the even values will be multiples of 4 as no matter what we take values of a and b whenever (b-a) is even (b+a) would also be even (because to make the diffrence of 2 numbers even their parity should be same and if we add same parity numbers then result is even) so that would make the result divisble by 4

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

Problem M solution tight for Java. WOrks in C++ but gives TLE in java. https://codeforces.com/contest/1725/submission/170984982

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

    NO Java AC solution for M. Please test the solutions for Java, Python as well before the round to know if the same solution passess the time limit. This is not fair that although both the solutions has the time complexity, it gives TLE in Java and AC in C++

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

For those curious about the $$$O(1)$$$ formula for problem G (Garage):

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

    noob

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

    I could come up with this result by building a sequence,

    I added the difference between b^2 and a^2 in the sequence as follows:

    4 — 1, 9 — 4, 16 — 9, 9 — 1, 25 — 16 ..

    by listing the "difference between squares" in nondecreasing order,

    I got the sequence:

    3, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, ,27, 28, 29, 31..

    I noticed that the first number "3" doesn't follow the pattern, so I assumed it was a special case,

    but the remaining numbers follow a consistent pattern that I came to figure out as:

    "3 + 4 * (N // 3) + N % 3"

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

Isn't F's TL too tight?

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

I think problem J has insufficient tests. In particular, I found solutions (including mine) that get AC, but give an incorrect answer to the following simple test:

8
1 2 1
2 3 50
2 4 50
1 5 1
5 6 1000
6 7 1
6 8 1

As far as I understand, the correct answer here should be 106.

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

Could problem C be somehow solved by subtracting the configs with three same colours in the right angled triangle from $$$m^n$$$ rather than summing over bin. coefficients?

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

Can anyone tell me whats wrong with my code for Problem C? ~~~~~ def nCr(n, r):

return (fact(n) / (fact(r)
            * fact(n - r)))

def fact(n): if n == 0: return 1 res = 1

for i in range(2, n+1):
    res = res * i

return res

n,m=map(int,input().split()) d=list(map(int,input().split())) cf=sum(d) t=0 ptr1,ptr2=0,0 val=d[ptr1] while True: if val*2==cf: t+=1 ptr2+=1 if ptr2>=len(d)-1: break val+=d[ptr2] elif val*2<cf: ptr2+=1 if ptr2>=len(d)-1: break val+=d[ptr2] else: val-=d[ptr1] ptr1+=1

if t==0: print(m**n) else: c=n-(2*t) count=0 x=min(t,m) for i in range(x): count+=(nCr(t,i)*nCr(m,i)*fact(i)*((m-i)**(t-i+c))*((m-i-1)**(t-i))) print(int(count)%998244353) ~~~~~

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

173417871 Can anyone tell me what is wrong with my code for problem C?

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

I try to solve this problem M. Moving Both Hands ,but it always gives me WA , please anyone help me, i'am stuck in this problem about 2 weeks and can't figure out why my code is wrong?

Here is mycode,I used dijkstra twice for each direction of the graph.

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

    You need to make sure que is a heap before running dijkstra for the second time. 173757547

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

      great thanks to you, I really ashamed from myself to stuck in this problem for long time becasue of this trivial coding line heapify(que)

      • »
        »
        »
        »
        12 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you please explain your approach?

        • »
          »
          »
          »
          »
          8 hours ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it
          1. Run a dijkstra algorithm to get the shortest path from node 1 to every node to calculate the distances from the first hand.
          2. Reverse the direction of every edge in the graph to make the graph ready for the other hand.
          3. Run dijkstra again but this time store the calculated distances in the queue .
          4. finally loop over every node except 1 to get the min distance.
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont why im getting WA in test case 24 in second problem. Didnt used binary search(cant making idea), simply itrated it by sorting in ascending order and multiplying by the number of its previous element and if the opponent player strength become less, then reset the number of elemnt to 1, initially number of element is 1. please give me some hints, im stuck here for so long. and if anyone solve via binary search please make me clear about the approch. submission link: https://codeforces.com/contest/1725/submission/174080208