ACGN's blog

By ACGN, history, 4 weeks ago, In English
A little backstory about the round (ACGN)

2031A - Penchick and Modern Monument

Idea: pwned
Preparation: HappyPacMan

Hint 1
Hint 2
Solution
Feedback

2031B - Penchick and Satay Sticks

Idea: ACGN
Preparation: HappyPacMan

Hint 1
Hint 2
Solution
Feedback

2031C - Penchick and BBQ Buns

Idea & preparation: ACGN

Hint 1
Hint 2
Solution
Feedback

2031D - Penchick and Desert Rabbit

Idea: AverageDiv1Enjoyer
Preparation: HappyPacMan

Hint 1
Hint 2
Solution
Feedback

2031E - Penchick and Chloe's Trees

Idea & preparation: ACGN

Hint 1
Hint 2
Solution
About Problem E
Feedback

2031F - Penchick and Even Medians

Idea: trunkty
Solution & preparation: maomao90

Hint 1
Hint 2
Solution 1
Solution 2
Solution 3
Challenge
Feedback

Round statistics

Fastest submission among all participants, and among rated participants:
A: tourist at 00:00:43, priyanshu.p at 00:00:56
B: tourist at 00:01:57, arnabmanna at 00:02:10
C: arvindf232 at 00:06:22, boboquack at 00:11:42
D: _Duck_Dot_Dot_Happy at 00:10:50
E: fzx at 00:11:27, Jack.YT at 00:20:38
F: peti1234 at 00:34:01, waiting_for_the_sunset at 00:54:34

More round statistics to be updated!

That's it for this round, and we hope you had fun with all the problems!

A few serious words from ACGN - about problemsetting, MathForces, and more
and from my own heart...

  • Vote: I like it
  • +277
  • Vote: I do not like it

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

wow,the tutorial comes so fast!

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

hint 1 for D is missing

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

great contest c is quite interesting

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

Why the hints of D starts from Hint 2? By the way, good C&D.

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

    numbering issue, sorry and has been fixed

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

why my code for C got wrong answer?

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

    the $$$1$$$s at indices $$$1$$$ and $$$9$$$ are separated by a distance of $$$8$$$, which isn't a square.

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

    dist b/w first 1 and last 1 is not a perfect square

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

superfast editorial

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

C was great. The Pythagorean triples idea is so elegant.

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

    thanks, it was my favorite problem!

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

Nice trick on C. Instead of creating this array

1 3 3 4 4 5 5 6 6 1 2 7 7 8 8 9 9 10 10 11 11 12 12 13 13 1 2

I create this

1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 11 11 12 13 13 1 12

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

    That's the construction some of the testers used; there are many ways to construct a suitable array.

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

    Same as mine, but to figure out that odd number still exists a way, that literally took me a while.

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

      Exactly, I think that most of the people whose first solution got WA have submitted that for odd N, answer is -1 and after getting it wrong started to think about odd N.

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

    another way $$$x=1e6$$$

    x 1 2 3 4 5 6 7 8 x 12 11 11 13 13 14 14 1 2 3 4 5 6 7 8 x 12

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

    I used a different array from both: 1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,10,10,11,11,12,12,13,13,2

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

      i used 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 10 11 11 12 13 13 1 12 ..

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

    Considering how many ways you could place the last odd value (having a distance of $$$9$$$ or $$$4$$$ or $$$16$$$, there are $$$2 \times (21 + 16 + 11)$$$ unique patterns. (neglecting the values of the individual element).

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

    Instead of writing any hard-code, we can just write like this : 291682216

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

1,12,13,13,11,12,10,9,11,8,10,7,9,8,6,7,1,5,6,4,3,5,2,4,3,1,2 can this be a sequence for first 27 element in question c?

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

the fastest tutorial ever!

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

[1, 2, 3, 3, 1, 2, 4, 4, 1] is sollution for 9 which is less then 25 for problem C

distance is 1 for 3, 4 and 4 for 1, 2

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

    this is wrong, the first and last 1 have a distance of 8.

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

    distance between 1s at indices 1 and 9 is 8 which is not perfect square

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

    No , 9 — 1 is 8 which is not a perfect square

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

A caught me off guard wtf

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

I find I always make problem more complex, like this div.2 D. I spent 30mins to solve ABC, but can't wock out D. What should I do to avoid??

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

    What algorithm you think it should be applied in D?

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

      I preprocessed out the position of the largest number and sorted it by numerical size and position. Then use a monotonic stack to maintain a suffixed minimum value from back to front. When I want to compute the answer, find the position of this minimum and find the answer before it. The time complexity is $$$O(n\log{n})$$$ because I need to make a binary search inside the stack to find this rearmost minimum.

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

        At first, I thought the same thing however I notice that I can create mountains (*mountain is an decreasing array), so a mountain will have a peak (the largest value) and a down (the smallest value).

        For example: 2 4 1 6 3 8 5 7 -> (2), (4, 1), (6, 3), (8, 5), (7)

        And then I save the largest and smallest of each mountain

        (2), (4, 1), (6, 3), (8, 5), (7) -> (2, 2), (4, 1), (6, 3), (8, 5), (7, 7)

        Here's another example 2 5 3 1 6 2 10 9 8 -> (2), (5, 3, 1), (6, 2), (10, 9, 8)

        Then (2), (5, 3, 1), (6, 2), (10, 9, 8) -> (2, 2), (5, 1), (6, 2), (10, 8)

        And I notice that if there exist 2 mountains i and j so that i.peak > j.down then the rabbit can jump from mountain i to mountain j. I sort these mountains with the peak decreasing and I find out that the problem now looks like a graph (more like DSU).

        Here's my solution 291628412

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

        I use this algorithm too!

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

Can D be solved with dsu?

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

    Yep. For each point, merge it with the point to the left of this point and with the highest height, and also merge it with the point to the right that is farthest away from it and with a height smaller than it. It can be shown that this merging is optimal.

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

      How do you keep track of highest height to the left and the points which are farthest away with a height smaller than it?

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

so why my code for D is wrong?

#include <bits/stdc++.h>
#define for1(i,a,b) for( int (i)=(a); (i)<=(b); ++(i))
#define for2(i,a,b) for( int (i)=(a); (i)>=(b); --(i))
#define madd(a,b) (a)=((a)+(b)+mod)%mod
#define fi first
#define se second
#define p_f push_front
#define p_b push_back
#define o_f pop_front
#define o_b pop_back
#define int long long
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
typedef unsigned long long ULL;
const int mod = 10007;
const int N = 105;
const int M = 105;
const int IINF = 0x3f3f3f3f;
const LL LINF = 1e18;
int T;
int n;
int a[500005];
int b[500005];
int Log[500005];
int f[500005][30];
int ans[500005];
int fm(int l,int r){
	int d=r-l+1;
	int x=Log[d];
	return max(f[l][x],f[r-(1<<x)+1][x]);
}
signed main(){
	time_t start=clock();
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	Log[1]=0;
	for(int i=2;i<=500000;i++)
		Log[i]=Log[(i>>1)]+1;
	cin>>T;
	while(T--){
		cin>>n;
		for1(i,1,n) ans[i]=b[i]=0;
		for1(i,1,n){
			cin>>a[i];
			ans[i]=a[i];
			b[a[i]+1]=i;
			f[i][0]=a[i];
		}
		for1(i,1,n) b[i]=max(b[i],b[i-1]);
		for(int len=1;len<=Log[n];len++)
			for(int i=1;i<=n;i++){
				int j=i+(1<<len)-1;
				if(j>n) break;
				f[i][len]=max(f[i][len-1],f[i+(1<<len-1)][len-1]);
			}
		ans[n]=max(ans[n],fm(1,n));
		for2(i,n-1,1)
			ans[i]=max(ans[i],max(ans[max(fm(1,i),fm(1,b[a[i]]))],max(fm(1,i),fm(1,b[a[i]]))));
		for1(i,1,n) cout<<max(a[i],ans[i])<<" ";
		cout<<"\n";
	}
	time_t duration=clock()-start;
	cerr<<"\ntime="<<duration;
    return 0;
}
»
4 weeks ago, # |
  Vote: I like it +87 Vote: I do not like it

Lmaooooo I already knew that tons would vote "Bad Problem" in the feedback for C. This community can be so predictable at times.

C is an EXCELLENT problem, yall are just haters

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

    Yes, many of them don't think about the odd amount of elements can have a solution

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

    So true bestie

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

    What is the purpose of samples in such problems? They always must have funny non generalizable construction.

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

      Well of course it has to be non-generalizable, otherwise it would spoil the problem haha

      Regardless, it does still serve the following purposes:

      • Showcases the output format
      • Allows you to verify ("sanity check") that your understanding of the problem is correct, since you can verify the given definition on a concrete example.

      For example in this problem, what does |i — j| = a perfect square mean? Should it be the 1st and 9th buns that match, or the 1st and 10th? We know it should be 1 and 10, but it's a reasonable misunderstanding to make, especially in the heat of a contest.

      But the answer is easily, totally unambiguous because you can very easily just check the sample output to see which interpretation is correct.

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

Typo: In Problem F Solution 1 Part 1 line 2: and the other is strictly larger than $$$\frac n2$$$ -> larger than $$$\frac n2 +1$$$.

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

if you know Pythagoras theorem,you can solve C easily

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

Penguins! A very nice contest :D

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

Though I stuck on C for nearly an hour(because of my poor math), I still think C is a beautiful problem conbined maths and constructive algorithms excellently. This is the best problem in this type I've ever met.

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

Can someone point out the mistake —

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin>>n;
        int count=0;
        vector<int>arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        for(int i=0;i<n-1;i++){
            if(arr[i]>arr[i+1]) count++;
        }
        cout<<count<<endl;
    }
    return 0;
}
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I couldn't solve A and B. My penchick is getting skinny Edit: Yay! I am now newbie!

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

For C, isn't [1, 2, 2, 4, 4, 5, 5, 3, 6, 1, 7, 7, 6, 1, 9, 9, 3] for 17?

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

    No, the first 1 and the last 1's distance is not a perfect square (13).

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

    the $$$1$$$s at indices $$$1$$$ and $$$14$$$ differ by $$$13$$$, which is not a square.

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

    dist between first 1 and last 1 is 13

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

Thanks for the fast editorial. Elegant problemsetting for C, now I learn.

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

What's wrong with this case for n=27 in Problem C? 13 1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 1

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

    distance between your 2 first 1s is 8

    you werw so close though that is the idea. but it's the even length you need to pad

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

      No, I think its 9 only, 1s are on 1st and 10th index in the case you're mentioning.

      So actually, I have put 1's on index 1, 10, 26 13s on index 0 and 25 Rest I just generated.

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

        Oh yeah mb. Checked your last submit you're printing "13 1 \n" in the end arent you ? Maybe thats the issue ?

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

          Got this: wrong answer Color 1 used only once (test case 1), but don't know which test case it could be on.

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

            ans for n=1 is -1. no filings can be used a single time so n=1 has no valid answer.

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

              Ohh man...crying myself to sleep. :((....Thanks dude!!

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

                Dont ! Double checking minor mistakes is the easy part. Finding this idea for C i bet you get cyan in less than 5 contests !

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

ACGN pwned how to join the server?

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

Unfair time constraints for B, my correct solution [O(N) in PyPy] is giving tle on test 3, kindly accept this in system testing. (https://mirror.codeforces.com/contest/2031/submission/291630383) Wasted the whole contest in figuring out a logn or constant time solution for this, I didn't even try using C++ cause never do I expect a simple O(N) problem to give tle just because its python, also got like extra -200 because of trying shorter solutions for B out of frustration, so sad

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

    Python's input() is slow (at least on the judge server); always use sys.stdin.readline().rstrip() instead of input().

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

    Calling input() in Python flushes stdout. Even in C++ you easily get the same kind of TLE if you forget cin.tie(0). Repeatedly flushing stdout is very slow.

    For the future, put this into your template. Then you won't ever get this kind of TLE again.

    import sys
    input = lambda: sys.stdin.readline().rstrip()
    
    
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      omg the python god himself, thank you so much will use it from now on

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

    Hmm for some reason python3 works but not pypy 291718850

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

In Problem D first example

4

2 3 1 4

o/p --> 3 3 3 4

how can rabbit jump from 2 to 3 because question clearly states that forward jump can be made iff the next guy is smaller.

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

    2 -> 1 -> 3

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

    The rabbit jump from 2 to 1 (because 1 < 2 and 1 stand after 2)

    Then the rabbit jump from 1 to 3 (because 3 < 1 and 3 stand before 1)

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

Great problem C, good choice of samples as well, any more samples might've given away the solution.

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

E can be solved in $$$O(N)$$$

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

    how so? I'm interested

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

      Please have a look at 291664548

      Basically, we just count the leaves needed for each subtree. The # can be large so we use a binary array.

      Since the count added from each children is a power of two, by potential method the amortized time to do addition of all children is $$$O(#children)$$$.

      Then we can just choose smallest $$$k$$$ such that $$$2^k$$$ leaves is enough.

      Edit: I've just noticed the code above has a mistake: It has an unnecessary loop in dfs of O(d)

      However it can easily be fixed, as in 291671084

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

        I'm sorry, I really can't understand the code; can you explain it in more detail and pseudocode? thankss

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

          Sure, dfs(u) returns depth of perfect binary tree needed to build subtree of u in original tree.

          Let's call this value dp[u].

          To calculate dp[u], first we calculate dp[v] for every child v. The intuition is if v requires perfect binary search tree of depth dp[v], it will "consume" 2^{dp[v] - 1} leaves.

          We add the amount of leaves needed for each child node of u to get the total amount of leaves needed for u's subtree.

          But the amount can be very large, so we use something similar to bigint in base 2.

          dfs(u) {
          	d <- 0
                  vec <- {}
          
          	for all child v {
                          x <- dfs(v)
                          vec.push_back(x)
          		d = max(d, x)
          	}
           
                  let xx be bigint
                  for w in vec {
                         add 2^w to bigint
                         d = max(d, w)
                  }
          
          	if (d-th bit of xx is on and there are more than one bits turned on) {
                         /* basically, xx is more than 2^d */
                         d += 1
                  }
          		
          	return d + 1;
          }
          
          

          (There might be some off-by-one error in this comment)

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

            The complexity of bigint operations:

            The bigint is stored as array where each element can be 0 or 1

            Since the value we add to it is always power of 2.

            We can let potential of the array be count of digits with 1 in it.

            Each value we add will increase the potential by at most 1

            Hence, amortized over all children of node u, the complexity is O(count of children of u)

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

              Ohh wow, I didn't expect it to be possible to implement bigint this way; I overlooked the possibilty of implementing these bigints "on top" of each other, and thought that each bigint would need $$$O(n)$$$ space. Thanks for the insight!!

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

              Nice solution.

              I have been trying this form of dfs for 2 hours, but have failed to do so. Even using python, I get a runtime error. I will try your implementation for bigint. it is really fun

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

            One can visualize the big int as a bitset of n bits right?

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

            Nice

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

            it will "consume" 2^{dp[v] — 1} leaves. what do you mean :( can you please explain

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

ACGN i can't view the implementation of problems,can you make them public?

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

    I think the implementation are only viewable after system testing has concluded; sorry for the inconvenience.

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

if this round didnt have samples, nothing would have changed

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

I finished ABCD for the second time!

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

I can not access the implementation of problem D !!!

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

Why are there so many pretests in Problem E?

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

Thanks for creating this round!All of the problems are awesome!

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

In the solution for D Shouldn't it be:

ansi=max(a1,a2,…ai)=pi

instead of

ansi=max(a1,a2,…an)=pi

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

Damn. C was just Fire. Though couldn't finished in time

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

Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).

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

In D ansi=max(a1,a2,…an)=pi. should be ansi=max(a1,a2,…ai)=pi.

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

C was a great question. I was very close to figuring it out, but couldn't solve it in the end :(

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

in A if i assume if n == 1, the answer will always be 0, but due to this i got the wrong answer, why is that? my answer got accepted after i removed this condition

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

    Because you are not reading the input that comes after, so you are getting wrong input for the next testcase.

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

Can someone assist me in determining the first minimum element from the back of an array for each element in the array?

Thank you!

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

What an incredible journey! The blend of creativity, dedication, and unique themes makes this round truly special. Kudos to the team for bringing it to life!

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

Can someone help me figure out why 291650692 failed with RTE, while 291666454 passed? The only difference is that the priority_queue is declared local in the former and global in the latter. Is this because $$$10^6$$$ ints is too much for a stack allocated std::priority_queue?

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

good luck on your medicine journey. amazing story!

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

I think the definition of rooted tree isomorphism given in 2031-E - Penchick and Chloe's Trees is slightly wrong.

Two rooted trees, rooted at $$$r_1$$$ and $$$r_2$$$ respectively, are considered isomorphic if there exists a permutation $$$p$$$ of the vertices such that an edge $$$(u,v)$$$ exists in the first tree if and only if the edge $$$(p_u,p_v)$$$ exists in the second tree, and $$$r_1=p_{r_2}$$$.

Here $$$u$$$ and $$$v$$$ are in the first tree, and $$$p_u$$$ and $$$p_v$$$ are nodes in the second tree. But then $$$r_1=p_{r_2}$$$ makes no sense since $$$p:$$$ first tree $$$\rightarrow$$$ second tree. The correct statement is $$$p_{r_1}=r_2$$$

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

    Yep got me confused for a while.

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

    i still dont understand this till now , i thought the definition of isomorphism is that there exists a root in the second tree where choosing it results in the first tree appearing but that doesnt seem the case in this problem for example take this tree

    1 — 2 — 3 — 4 — 5 — 6 — 7

    a binary tree of dep 3 aka 2 ^ 3 has a diameter of length 7 but for some reason the answer for the tree above is 6 ?

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

      Both the trees have fixed roots. The problem used rooted isomorphism and not normal isomorphism. You should read statements correctly.

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

        i didnt blame the problem author i legit didn't know what rooted isomorphism even meant so chill down , aside from that yes the definition was poorly written

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

          I didnt say you blamed the author either....fyi, I (and I guess most participants) also did not know the definition of rooted isomorphism before solving the problem

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

            no worries could have been better but atleast didnt get it in a rated contest

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

    My bad. I'll fix it. Thanks for the catch!

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

I solved F with a solution with success rate of around $$$0.998$$$.

Denote $$$A$$$ as the set of candidates for $$$\frac{n}{2}$$$ (initially $$$ {1, 2, \dots, n}$$$). Similarly denote $$$B$$$ as the set of candidates for $$$\frac{n}{2} + 1$$$. We also maintain the third set $$$C$$$ of candidates for both $$$\frac{n}{2}$$$ and $$$\frac{n}{2} + 1$$$ (we will update it a bit differently, so it won't be just $$$A \cup B$$$).

Query a random subset $$$S$$$ of $$$C$$$ of size $$$10$$$. Let $$$x$$$ and $$$y$$$ be the result. If $$$x = \frac{n}{2}$$$ or $$$y = \frac{n}{2}$$$, there is $$$\frac{n}{2}$$$ in $$$S$$$, so we can set $$$A = A \cap S$$$. Similarly do for $$$B$$$. If $$$x = \frac{n}{2}$$$ and $$$y = \frac{n}{2} + 1$$$, then we can set $$$A = A \cap S \cap (A \cup B)$$$ and $$$B = B \cap S \cap (A \cup B)$$$ (actually, that does nothing).

We don't wanna keep $$$C$$$ too big, but also don't want to make it too small to have a higher chance to reduce the sizes of $$$A$$$ and $$$B$$$. What I do is: if $$$x < \frac{n}{2}$$$, $$$\frac{n}{2} + 1 < y$$$ and $$$|C| - |S| \ge 12$$$, set $$$C = C \setminus S$$$. Otherwise, do nothing.

Terminate the search when $$$|A \cup B| = 2$$$.

Out of $$$10000$$$ random tests with $$$n = 100$$$, it manages to solve around $$$9980$$$. Submission: 291665018

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

Is the implementaion of D visible?

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

Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).

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

why my code for C got wrong answer?

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

    You were adding too many pairs of "i i" at the end of your loop in the odd case; replacing the last i++ by i+=2 gives AC. 291678666

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

How is it that suddenly 2000+ people solved C problem in the last 20-30 mins? Hope the cheaters are found and removed!!

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

for me, problem E much more easy then D))

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

C was so beautiful, was not able to solve it in the contest but the solution is elegant!

W problem @ACGN, keep it up!

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

I think D is easier than everything

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

Note that we don't need to dfs in Problem E since 1..n is a topo seq of the tree

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

    I supposed the extra overhead of the unnecessary dfs would fail given the large tree, but it doesn't.

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

      It's a bit of an implementation detail: the idea is still somewhat DFS, but I did implement it directly on the array, treating it as regular DP. The TL should? be generous enough to allow DFS as well.

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

The best C I've ever done 有生之年做过最好的C题

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

Problem B also can be solved by brute force, because one number can never be swapped more than twice, so we just need to check the array two times and swap two numbers if we can, time complexity $O(n)$。

code:

void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int t=1;t<=2;t++)
    {
        for(int j=1;j<n;j++)
        {
            if(a[j]==a[j+1]+1)swap(a[j],a[j+1]);
        }
    }
    writeln(is_sorted(notall(a))?"YES":"NO");
}
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem A, what if all the elements are unequal and already organised but the first, does that mean we'll have to count all the "equal" numbers ?

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

D is a cute problem. Thanks.

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

why i am the only one who solve b with segment tree :(

https://mirror.codeforces.com/contest/2031/submission/291825632

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

Can any body explain why my code is wrong ?

Problem D : 291848242

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

    I didn't undertand your code even after converting into cpp, also it's not compiling but i can give you 2 good test cases :

    8

    6 7 3 6 8 8 9 10

    ans : 7 7 7 7 8 8 9 10

    10

    6 7 3 6 8 8 9 4 10 11

    ans : 9 9 9 9 9 9 9 9 10 11

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

Please someone help me with this,why my 291854656 is WA ? Below code seems to be correct to me. Please provide a testcase where it fails . Thanks

#include<bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define LL long long 
#define mod 998244353 
#define FOR(i, j, k) for (int i=j ; i<k ; i++)
#define ROF(i, j, k) for (int i=j ; i>=k ; i--) 
 
const long long INF = 1e18;
const long long MAX = 1e5+10;

int main(){
    fastio;
    int t; cin>>t;
    while(t--){
        int n;cin>>n;
        int a[n+1];
        bool ok=true;
        FOR(i,1,n+1) cin>>a[i];

        FOR(i,1,n){
            if(a[i]==i)
                continue;
   
            if(i==a[i+1]){
                 swap(a[i],a[i+1]);
            }
            else{
                ok=false;
            }
        }
        cout<<(ok?"yes":"no")<<"\n";
    }
}


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

what would be the rating of C and D?

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

The last method given by the answer to question A if the test case is 1 5 4 4 1 4 shouldn't the output be 2? Why is its code output 3

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

    Not sure about what input format you're using, but in any case this does not seem like a valid input. The input array must be non-increasing.

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

There is something wrong with the LaTex of problem E claim 1's proof. Please fix it. Thank you!

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

Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).

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

Perhaps there is something wrong with the first way to slove E in your tutorial. After reading your code, maybe we should replace $$$a$$$ by $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil + 1$$$ but not $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil$$$

In Simplified Chinese: 楼主你E题第一种解法好像有个地方写的有问题。我看了你的代码之后,觉得有个地方教程里写的和你代码写的不符:我们应该把 $$$a$$$ 改成 $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil + 1$$$ ,而不是 $$$\lceil \frac {a}{2^{d_{c_i}-b}}\rceil$$$

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

Good problem C.

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

what is wrong in this logic for problem B. Getting WA on 2nd test case.

292214260,2031B - Penchick and Satay Sticks

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

Auto comment: topic has been updated by ACGN (previous revision, new revision, compare).

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

can anyone explain for me the dsu approach in D please?

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

We can you simple rangeMax segtree to solve problem D,

we just have to simulate , first go to max element in the left , then for every possible value from 1 to maxelement , take the value from previously element we have jumped

link: link

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

C was harder than D, but both were very easy compared to standard div2c's and d's

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone give me a small test where my code for E fails? Thanks in advance

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

    A tree with 9 leaves:

    1
    10
    1 1 1 1 1 1 1 1 1
    

    Your solution gives $$$3$$$, while the answer is $$$4$$$. Making one small change makes your code correct: 293581182