Messages posted by: petarsor

Dear all,

JOI Open Contest 2019 is an IOI-like open competition for students at
schools for secondary education. The main purpose of this contest is
to give Japanese delegations and candidates of delegations an
opportunity for training and practice. But the contest itself is open to everybody.
Everybody is welcome to attend JOI Open Contest 2019!

This year, the contest will be held on 14 July 2019.
There will be 3 tasks. Each submitted source program must be written
in C++ (C++14). Problem statements will be provided both in Japanese
and English.

The duration of the contest is 5 hours. The same contests will be held
twice (Round 1 and Round 2). Contestants can participate in one of
Round 1 or Round 2 according to their time zone. After Round 2 finishes,
we will open the judging server for one day. Interested contestants can
improve and resubmit their solutions by themselves.

After the contest finishes, we will fix the standings.
No prizes will be given to the contestants.

Contest website:
https://contests.ioi-jp.org/open-2019/index.html

Contest duration: 5 hours
The number of tasks: 3 tasks
Language: English, Japanese
Programming Language: C++ (C++14)
Details will be announced on the contest website.

Date & Time:
Round 1
Sunday, July 14, 2019
13:00-18:00 +0900 (JST)
04:00-09:00 (UTC/GMT)

Round 2 (tasks for Round 1 and Round 2 are the same)
Sunday, July 14, 2019
19:00-24:00 +0900 (JST)
10:00-15:00 (UTC/GMT)

Judging Server is open until
Monday, July 15, 2019
23:00 +0900 (JST)
14:00 (UTC/GMT)

======
Executive director of the Japanese Committee for the IOI
Seiichi Tani

Chairperson of the Scientific Committee of JCIOI

MODDI wrote:Кодов ми работи на 14/20 тест примери на останатите ми дава надминат временски лимит, дали може задачава да се реши на ваков начин или треба да барам побрз.

Види го решението дадено на почеток, бидејќи и тоа паѓа на 5-6 примери како твоето. (И коментарите дадени под него).

Така да, треба да смислиш нешто попаметно/побрзо. Ако не ти текнува, еве еден начин:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<pair<int,int> >ID;
int main()
{
    int dancers, inrow;
    std::ios::sync_with_stdio(false);

unordered_map<int, int> pos;
    cin>>dancers>>inrow;
    for(int i=0;i<dancers;i++)
    {
        int a;
        cin>>a;
        if(i==0) {
            ID.push_back(make_pair(a,1));
            pos[a] = 0;
        }
        else
        {
            bool seen=false;
            if (pos.count(a) > 0) {
                int where = pos[a];
                ID[where].second++;
                seen=true;
            }

if(seen==false) {
                int where = ID.size();
                pos[a] = where;
                ID.push_back(make_pair(a,1));
            }
        }
    }

for(int i = 0; i < ID.size(); i++)
    {
        pair<int,int> at=ID[i];
        if(at.second%inrow==0)
            continue;
        else
        {
            cout<<at.first<<endl;
            return 0;
        }
    }
    return 0;
}

MODDI wrote:Задачата Rectangles од делот интернационални е повторно дп, ми работи на 2/10 малку хелп.

Ова е друга задача, не би требало да е во оваа тема.
Во секој случај, пробај направи си свои примери (или симни ги тие од МЕНДО) и види каде ти е грешката.

Еве, ти ја поправив задачата (код долу), ама најдобро е да не го гледаш тоа и да пробаш сам.

MODDI wrote:Задачава неможев да ја сфатам, поточно на врските немозам да го сфатам начинот на кој тие се добиваат, сликата што е дадена во текстот на задачата повеќе ме збунува мене отколку ми појаснова, ако може некој барем псевдо код да даде или base-cases од dpto и да ми ја појасни задачава.

Сликата одговара на примерот даден во текстот на задачата. Незнам што те збунува, имаш почетни врски (тоа се врски помеѓу соседните букви од почетниот стринг) и плус има 14 дополнителни врски (тоа се сите нацртани врски кои не се од почетниот стринг). Единствено може да те збуни ако броиш 13 такви врски, а излезот е 14 - тоа е веројатно бидејќи не ја гледаш врската што е помеѓу U и A (веднаш над почетокот). Какви дополнителни врски се можни е дадено во текстот на задачата - цитат: "Тоа значи дека се возможни врските A – U, U - A, C – G, G – C, G – U и U – G.".

Ако дадам повеќе информации за динамичкото, исто е како да сум го дал целото решение, така да еве:

BATIR wrote:Spored mene , ovaa zadaa se resava so dp, samo ako nekoj znae moze da mi dae hint kako kje ide dinamickoto...
Fala odnapred

1. Точно е, може да се реши со динамичко програмирање.
2. Не треба никакви дополнителни структури (дрва, незнам што), само динамичко програмирање (5-6 редови код)
3. Состојбата можеш да ја чуваш со две димензии dp[x][y].

Толку би помогнал јас

MODDI wrote:Со кодов ми поминува на 27/37 тест примери на останатите ми паѓа на време, дали со неколку модификации на кодов може да се реши задачава или ќе треба да го земам фактот дека 1≤N≤100 000, а дека задачава работи О(N na kvadrat)

Треба да го земеш во предвид тоа што 1≤N≤100 000. Твоето решение е пребавно.
Размисли, дали можеш да искористиш некоја структура како map, hash (unordered_map), итн, за да го знаеш бројот на елементи со одредена вредност?

(Види решение подолу)

David1223 wrote:mi prikazuva runtime error

Во однос на "runtime error"-от (мада има твојата програма и други грешки):
хинт 1) види ја низата "niza", и на кои елементи пристапуваш
хинт 2) види го првиот дел од ова предавање "Големина на низа": http://mendo.mk/Lecture.do?id=21

Вака накратко, ќе ископирам еден дел од предавањето "На пример, со "int arr[10]", се креира низа од 10 елементи - arr[0] до arr[9]. Едноставно, недозволено е да се пристапува до елементот arr[10]."

Krenkov wrote:Дали би можела задачата да се реши рекурзивно?

Не на овој начин. Имаш премногу состојби за разгледување.

Но, многу алгоритми може да се реализираат со помош на рекурзија - на пример, динамичко програмирање (со мемоизација).
Инаку, ако бараш решение на задачава, може да провериш тука: http://mendo.mk/jforum/posts/list/565.page

Ако добро те разбрав (функцијата да не врати веќе внесена буква), вака отприлика би можел да ти изгледа кодот:

Имаше доста грешки во твојот код, али највеќе е тоа што не разбираш добро што ти чува променливата "a" (а промашен е и типот - ја дефинираш од тип bool, а потоа правиш а++, што најчесто се користи со цели броеви за зголемување на вредноста за 1).
Следниот пат кликни на копчето (Code) кога додаваш код, инаку не може ништо да се разбере од него.

Nj1234 wrote:da probav isti rezultat dobivam na dvata nacini dva pati samo vrti loopot ednas dicrementirat broj megu 1 i 7 dtugiot pat e negativen broj

Јас сум убеден дека немаш проверено тоа што јас го напишав (ако си проверил, прати ни некое видео како работи твојата програма). Во твојот код се намалува повеќе пати (оти намалуваш во for-от), а во кодот што го пратив јас треба да е тоа средено.
Работи кај мене на компјутер тоа што викаш дека е грешка, а работи и на ideone: https://ideone.com/Lu0NEh (ова е истиот твој код, само со направена промената што е спомената во мојот прв коментар)

Така да, или јас не те разбирам, или немаш проверено тоа што е напишано погоре.

Nj1234 wrote:vo funkcija playGame switch case 1
problem so int mistake -ne se dekrimentirat ubo
idejata bese preku funkcijava chek_for_letter da se namaluvat i da ima kontrola na while loopod podolu vaka odprilika
kompaljirat ama ne rabotit pravilno

mislam deka pram greska so ampersanive ama nesum bas najsiguren

А проба да разгледаш што напишав јас погоре, и тие промени да ги направиш/ископираш?

Па, веќе има дадено решение во другата тема (што ја спомнуваш):
http://mendo.mk/jforum/posts/list/671.page

Кликни само на линкот таму, па "sample solutions" кај првата задача. Има и решение и објаснување.

Можеш да ни кажеш што е проблемот, за да не погодуваме со што ти треба помош?

Вака, моја претпоставка, дека треба да ја смениш малку оваа функција (јас веќе почнав, како што е дадено подолу):

floreloriz123 wrote:http://mendo.mk/Task.do?id=851

Test primer 6:

input: abxabababababababasaadsadsdsds

expected output: 24

my output: 25

Eve kako mojot kod go kompresira stringot: abxMabababRabasaMadsRMdsR

Probuvam, no ne znam kako treba da izgleda kompresiraniot string so dolzina 24. Znae li nekoj kako tocno se kompresira ovoj string?

Ако не згрешив нешто во брзање, вака: abxaMbaRbaRbasaMadsRdsds

Hristijandinisev wrote:Ако може помош за задачава немам друга идеја како да ја решам а на медно го надминува временскиот лимит на некои тест случаи. Благодарам
http://mendo.mk/Task.do?id=799

Хинт: Прочитај го првиот дел од ова предавање, и размисли како да ја решиш со таа идеја (да одиш до квадратен корен на некој број, наместо до тој број).
http://mendo.mk/Lecture.do?id=34