A few weeks ago, I decided to participate in every contest👨🏻‍💻. The first contest was the Educational Codeforces Round 150 (Rated for Div. 2), held on the 12th of June. The next contest was on the 18th of June, but I was at a function. Therefore I couldn't participate. Now comes this contest for Div 3. In the evening, I suddenly remembered about the contest. For a warm-up, I tried solving problems from the last Div 3 contest but couldn’t solve even the second problem in time. This led me to rethink participating. But thinking about my earlier decision and ignoring the fear of possible rating decrement, I decided to participate🎯.

Problems

A. Sasha and Array Coloring

In this problem, I first sorted the given array and then calculated the sum of all the differences of edge elements from both sides.

sort(a, a + n);
int sum = 0, left = 0, right = n - 1;
while (left < right)
{
    sum += a[right] - a[left];
    left++;
    right--;
}
cout << sum << endl;

B. Long Long

Though this problem states that the answer is the maximum possible sum of numbers in the array and the minimum number of operations to get this sum. But I couldn’t find the minimum number of operations to be useful looking at the examples.

long long sum = 0, count = 0, flag = 0;
for (int i = 0; i < n; i++)
{
    if (a[i] < 0 && flag == 0)
    {
        count++;
        flag = 1;
        sum += -a[i];
    }
    else if (a[i] < 0 && flag == 1)
    {
        sum += -a[i];
    }
    else if (a[i] > 0)
    {
        flag = 0;
        sum += a[i];
    }
}
cout << sum << " " << count << endl;

C. Sum in Binary Tree

Binary Tree! I don’t know much about it. I don’t know how to implement it. But I tried reading the problem statement just out of curiosity. The sum of the vertex numbers on the path from the vertex with number 1 to the vertex with number n was to be calculated. I tried observing the pattern. It came out to be pretty simple. Keep dividing n by 2 and adding it until it becomes 1.

long long sum = 0;
while (n > 0)
{
    sum += n;
    n /= 2;
}
cout << sum << endl;

Before reading the problem, I was not confident enough that I could solve this problem. I just read it lazily. I could have solved it much faster. But after getting the Accepted verdict, the confidence to try the next problem increased. This was the highlight of today’s contest.

D. Apple Tree

I didn’t have any idea how to solve this problem. I first read the problem statement carefully, noting down what was happening without worrying about the implementation. Soon I figured out the way I could try out to get the desired output. I dry-ran the approach on paper, and it worked. I found that I had to find the product of the leaf nodes, which were descendants of two given nodes, x, and y. The next challenge was the implementation. For this, I struggled a lot. As I didn’t know much about implementing and using the tree data structure, I tried to take help from the internet to learn about it. I roughly went through some articles and tried ChatGPT to understand and implement my approach. Sometimes ChatGPT gave very wrong answers. I got segmentation fault errors and sometimes wrong answers for the sample test case. I tried simplifying prompts and finally got the correct answer for the given sample test cases. But!!! after submitting it, I got the wrong answer on test 4 verdict🤯. Around 15 minutes were remaining; I was staring at the screen. The 15 minutes passed, switching between the browser and VS Code. I knew there was nothing more I could do. I slept😴💤.

struct TreeNode
{
    int data;
    vector<TreeNode *> children;

    TreeNode(int val) : data(val) {}
};
int countLeafNodes(TreeNode *node)
{
    if (node == nullptr)
        return 0;

    if (node->children.empty())
        return 1;

    int leafCount = 0;
    for (TreeNode *child : node->children)
    {
        leafCount += countLeafNodes(child);
    }

    return leafCount;
}
// ... main function
vector<TreeNode *> nodes(n + 1, nullptr);
for (int i = 1; i <= n; i++)
{
    nodes[i] = new TreeNode(i);
}
for (int i = 1; i < n; i++)
{
    int x, y;
    cin >> x >> y;
    int parent = min(x, y), child = max(x, y);
    nodes[parent]->children.push_back(nodes[child]);
}
int q;
cin >> q;
for (int i = 0; i < q; i++)
{
    int x, y;
    cin >> x >> y;
    int leafNodesofx = countLeafNodes(nodes[x]);
    int leafNodesofy = countLeafNodes(nodes[y]);
    cout << leafNodesofx * leafNodesofy << endl;
}
for (TreeNode *node : nodes)
{
    delete node;
}

I enjoyed those 1½ hours. I was very happy. I got the wrong answer. It took me a lot of time to solve the first three problems, though I could easily solve them faster. But I was satisfied. I tried💯.