awoo's blog

By awoo, history, 16 months ago, translation, In English

2104A - Three Decks

Idea: fcspartakm

Tutorial
Solution (awoo)

2104B - Move to the End

Idea: BledDest

Tutorial
Solution (BledDest)

2104C - Card Game

Idea: BledDest

Tutorial
Solution (BledDest)

2104D - Array and GCD

Idea: BledDest

Tutorial
Solution (Neon)

2104E - Unpleasant Strings

Idea: adedalic

Tutorial
Solution (adedalic)

2104F - Numbers and Strings

Idea: BledDest

Tutorial
Solution (BledDest)

2104G - Modulo 3

Idea: BledDest

Tutorial
Solution (Neon)
  • Vote: I like it
  • +83
  • Vote: I do not like it

| Write comment?
»
16 months ago, hide # |
Rev. 2  
Vote: I like it +10 Vote: I do not like it

My Submission

can some one tell me why my solution give tle on E? i have used binary search instead of next array for next element

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

Why my submissions give TLE on D problem? Submission 1 Submission 2

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

    The line: void solve(vi P) creates a new vector P.You should instead use & to reference the vector in the solve function. like:void solve(vi& P)

    In the solve function, you should use a reference pass instead of a value pass, which will create a new vector P in the local part of the function. Similar to the comments mentioned earlier, the user TeletubiGaim33 mentioned。

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

Is there a dp solution for F?

  • »
    »
    16 months ago, hide # ^ |
    Rev. 5  
    Vote: I like it +66 Vote: I do not like it

    Consider which $$$x$$$ there does not exist any $$$y \lt x$$$ such that $$$S(x) = S(y)$$$. Excluding the obvious cases (for example, $$$y = 12349$$$ comes before $$$x = 32149$$$ because you can shuffle its prefix), $$$x$$$ is also not allowed to end with two or more $$$9$$$ (for example, for $$$x = 12399$$$, construct $$$y = 10293$$$ because you can remove two $$$9$$$ and insert a $$$0$$$ and a $$$9$$$ in the front), except for special cases such as $$$x = 1999\ldots9$$$, $$$x = 2999\ldots9$$$, ..., $$$x = 9999\ldots9$$$, and therefore, you also need to specifically consider numbers like $$$x = 900009991$$$, because even though they meet the conditions above, $$$y = 199999999$$$ paradoxically comes before it. Then you can write a digit DP to solve even $$$n \le 10^{10^6}$$$ (my submission).

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

    another dp solution that's similar to the one described by the furry above me, but MUCH uglier: 336744397

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

F is very good

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

Can someone explain this part in the G tutorial?

Let's try to understand how to conveniently count the parity of the number of SCCs for a functional graph. Vertices that are not on cycles represent separate components, and each cycle is a separate component. If a cycle has even length, it changes the parity of the number of SCCs, while if it has odd length, it leaves it unchanged. Therefore, we are actually interested in the number of cycles of even length in the functional graph.

How do even-length SSCs contribute to the answer while the odd ones don't?

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

    This is a problem reduction,let c=o+e c is the number of cycle,and o is the number of cycle with odd length and e is the number of cycle with even length,then obviously c mod 2=(o+e) mod 2

    Nows we know o is either odd or even,if o is even then (o+e)mod2=e mod 2,if o is odd then (o+e)mod 2 = (e+1)mod 2,and it's obviously to see that no matter o is odd/even there is only a parameter which is e,so c is dependant on e,similarly you also can say eliminate e and say that c is dependant on o,just depent on which ways you are convenient to implement,its does not affect the result

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

reason for tle on problem e? my time complexity is O(n*k), it should work.

Link

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

    Time complexity is O(q * n * k) i think that is the problem. In test 9 q = 7058, n = 1e6 and k = 25 that is something equivalent to O(1e10) that n * k is happening for every query that is too much so precomputation needed instead of checking inside the query loop you should precompute it before going to the query.

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

Wow,the idea of F is great.This is a beautiful brute force.I've summarized the idea

First I need to think of a condition,count of numbers which follow this condition are not too more.And just search. Second I need to filter again after search.Search once for all answers is too hard.So I can set a wide condition and search,then filter.This idea is great

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

Educational Rounds are curse for me, while Div 1 + 2 are blessing.

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

Actually, you can directly use LCT to maintain the unicyclic graph and solve Problem G in $$$ O(q \log n) $$$ time.

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

Got FST in E. I don't know why I thought $$$\sum n \le 10^6$$$ over all queries, but there was only one $$$n$$$.

Since my solution was $$$O(nq)$$$, it got TLE. Why did this problem have so weak pretests?

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

317833875 My submission .

Can anyone tell why it's giving TLE , have used greedy + binary search , it should be n*k which should be fine , isn't it ?

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

Can anyone pls explain why it is happening in problem D that if the sum of first K max element sum is atleast first K primes sum then we can make the array of size K beautiful?

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

    Based on the description, we can decrease the element anytime we want. So for any array with element sum $$$S_0$$$, we can build another different array with $$$S \lt S_0 $$$. So we can change the first K max element to first K prime if the sum of first K max element sum is at least first K primes sum.

    For example: [4,5,5] can change to [2,3,5].

    Obviously, for any prime pair (x,y), gcd(x,y)=1

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

      yeah! i have solved it before u have written it!

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

317853132

Question E It's a bit lengthy code, but it shouldn't get TLE, can someone help me to decrease its Time complexity.

  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    while(1){
                    // vector<int> vals;
                    int val(-INFLL);
                    fo(i, k){
                        if(v[i].size() == 0){
                            found = true; break;
                        }
                        auto it = lower_bound(all(v[i]), cnt);
                        if(it == v[i].end()){
                            found = true; break;
                        }
                        val = max(val, *it);
                    }
                    if(found) break;
                    cnt = val + 1;
                    ans++;
                }
    

    this is the issue, worst case complexity is O(n)

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

I think my solution for E is a bit easier :)

I am calculating how many times all letters appear from i to n

and then for each query I am getting the first index where the subsequence will be found then use the precomputation I made above to find from this index to the end (how many times all letters appear) and then add one to it

    idxes = defaultdict(list)
    cnts = [0]
    ss = set()
    cur = 0
    for i in range(n - 1, -1, -1):
        ss.add(s[i])
        if len(ss) == k:
            cur += 1
            ss = set()
        
        cnts.append(cur)
 
    cnts = cnts[::-1]
    for i in range(n):
        idxes[s[i]].append(i)
 
 
    q = read_int()
    for _ in range(q):
        t = read_str()
 
        lowest = -1
        nooo = False
        for j in range(len(t)):
            if not idxes[t[j]] or idxes[t[j]][-1] <= lowest:
                nooo = True
                break
 
            lowest = idxes[t[j]][bisect_right(idxes[t[j]], lowest)]
 
        
        if nooo:
            print(0)
            continue
 
        ans = cnts[lowest + 1] + 1
        print(ans)
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You need 4⋅10^5 primes, so you have to use the sieve up to something like 6⋅10^6.

In Problem D, how to analyse that to get 4⋅10^5 primes, you have to go till 6⋅10^6 ?

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

    According to the Prime Number Theorem, the number of primes $$$p \le n$$$ for some $$$n$$$ is $$$\approx n/\mathrm{ln} \; n=4\cdot 10^5$$$. Solving this, we get $$$n \approx 6 \cdot 10^6$$$.

    Alternatively, you could just run a sieve locally till about $$$10^7$$$, and check how big an $$$n$$$ it takes to reach $$$4 \cdot 10^5$$$ primes.

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

      Yes, I did the second one and I was like binary searching around it (joking not actually bs) coz I was too afraid as I am using Python and this idea was a bit new for me. Also, thanks for sharing the first way I always forget about it

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

Is it possible to do G without offline dynamic connectivity?

Seems like what would be required is to maintain the cycles + ordering, but I'm not sure if that's at all possible. If you ignore the rewiring of the graph, the code pretty straightforward

My attempt: https://codeforces.me/contest/2104/submission/319962878

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

    Yes, it can be solved with online queries in O((n+q)log(n)): https://codeforces.me/contest/2104/submission/324625656 But the constant factor is very high, so it still takes over half the time limit...

    Here is a brief hand-wavy explanation of my approach:

    Think of each component in the graph as a tree + 1 extra edge to form a cycle. The root of this tree should be a node in the cycle. For all other nodes, g_i is the parent of node i. The extra edge that forms the cycle is stored in the root as a "lazy link" (this will become important later).

    These trees are stored in a treap, where we make sure that the nodes of each tree are contiguous and in pre-order with respect to some dfs-traversal. This ensures that each subtree is stored in a contiguous range of the treap. We use this treap to store, for each node, the root of the tree it belongs to, and the distance to that root.

    To re-assign some g_i, we first detach the subtree of node i from its tree. This is done by moving a contiguous range of the treap, and doing range updates to update the root and distance information. We then check if the "lazy link" in the old tree bridges the two new trees. If it does, we merge them back together by linking the root of the old tree to the node it should be connected to. This can be done in the same way, by moving a contiguous range and doing some range updates. Finally, we add the new edge, which either involves adding a "lazy link" if it is within the same tree, or linking the tree to some node in another tree in the same way as before.

    The number of even cycles can be maintained by checking the parity of distances to the root every time a "lazy link" is added or removed.

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

This will be the first Div. 2 — D I've ever solved

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

C can be done in an even better way than brute force, for Alice to win you only need to check if she has (N and N-1) or (N and 1) or she needs to have N-1 cards. In any other case, Bob wins because he can see what card Alice chose and will have a better card.

My submission: 322895289

Further Explanation: (You are Alice) - If you have N and N-1, you can beat any of the Bob's card by choosing N-1 - If you have N and 1, you can beat any of the Bob's card by choosing N - If you have N-1 number of cards, whatever card Bob has, you win: — if Bob has 1, you have N-1 — if Bob has N, you have 1 — if Bob has any other card, you have N - In any other case, Bob will have a card to beat you.

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

In G editorial "If a cycle has even length, it changes the parity of the number of SCCs"
I don't get it...

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

my first div 2 d ever in practise i love whoever made this contest .. many many thanks

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

In problem F you can just directly store all $$$568725$$$ numbers in your code (while code limit size is $$$65536$$$ characters) by computing their difference array, applying LZW transform to it and then encoding the result into base $$$92$$$ instead of base $$$10$$$.

Resulting string is only ~$$$26000$$$ characters long, all what remained to do is to decode it by doing all the described steps in reverse to recover the initial array of $$$568725$$$ numbers.

Here is my implementation with ~$$$35000$$$ characters: 366723031

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

Can we solve problem E by binary search on answer??